ABC380Dをjavascriptで解いた

今日の問題

↑押してください。

自分の回答(javascript)

function Main(input){
    min = 1e18
    max = -1e18
    let abc = "abcdefghijklmnopqrstuvwxyz".split("")
    let ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".split("")
    let f = 3
    if(f == 0){
      input = parseInt(input.trim())
    }
    if(f == 1){
      input = input.trim().split("\n").map((a)=>parseInt(a))
    }
    if(f == 2){
      input = input.trim().split("\n").map((a)=>a.split(" ").map((b)=>parseInt(b)))
    }
    //ここより上は定型文です。
   input= input.trim().split("\n")
   s = input.shift().split("")
   n = s.length
   S = []
   abcset = new Set(abc)
   for(let i = 0;i<n;i++){
     if(abcset.has(s[i])){
        S.push(ABC[abc.indexOf(s[i])])
     }else{
       S.push(abc[ABC.indexOf(s[i])])
     }
   }
   //console.log(S)
   q = parseInt(input.shift())
   klist = input.shift().split(" ").map((a)=>BigInt(a))
   n = BigInt(n)
   res = []
   for(let i = 0;i<q;i++){
     klist[i] = klist[i]-1n
     
     if(so(klist[i]/(n)) == 0){
       res.push(s[Number(klist[i]%(n))])
     }else{
       res.push(S[Number(klist[i]%n)])
     }
     
   }
   console.log(res.join(" "))
   
   
   function so(n){
    let a = n.toString(2)
    a = a.split("").map((a)=>parseInt(a))
    goukei = 0
    //console.log(a)
    for(let i = 0;i<a.length;i++){
      goukei += a[i]
    }
    return goukei%2
   }
  }
  
  Main(require("fs").readFileSync("/dev/stdin", "utf8"));
  

工夫した点

愚直にやるとTLEします。またjavascriptは10^15くらい以上の数はNumber型が使えないのでBigIntで管理します。規則性を見つけます。2^n+m番目は2^(n-1)+m番目と逆であることなどから地道に考えると、塊のpopcountが偶数か奇数で場合分けされて答えを出すことができます。