CS Academy

CS Academy Round #14 Subarrays Xor Sum

問題 https://csacademy.com/contest/round-14/task/subarrays-xor-sum/ 解法 eha くんに解説をしてもらってようやく理解した。各ビットごとに独立なので、ビットごとに分ける。0と1のみの数列の長さ k 以下の数列の xor の合計値をとりたい。 i 番目の数を…

CS Academy Round #29: Root Change

問題 https://csacademy.com/contest/round-29/task/root-change/ツリーの各頂点 i について、 i を根とした時に切断してもツリーの高さが変化しない辺の数を出力してください。 解法 editorial のコード通りです。いわゆる全方位木dpと呼ばれる手法です。 …

CS Academy Round #12 Prefix Suffix Counting

問題 https://csacademy.com/contest/round-12/#task/prefix-suffix-counting/巨大な整数 N と M が与えられる。M は K 桁である。この時、1 以上 N 以下の範囲で、上 K 桁と下 K 桁がともに M と一致する整数は何通りあるか。 解法 整数 N の桁数を L とす…

CS Academy Round #11 A Single One

問題 https://csacademy.com/contest/archive/#task/a-single-one/N 個の整数からなる数列があり、S 番目だけ 1 で残りの数字は 0 である。この数列に対して「K 個の連続する区間を選択し、左右反転させる」という操作を行うことができる。またM個の位置が与…