ABC147

危惧していたことが起こりました。

難易度が以前のとおりに近くなったため、普通に4完でとどまってしまい、レートを下げることになりました。とはいえ-6なので一応耐え。

A：足して22と比較する。

B：文字列の先頭と末尾から1つずつ比較していく。

C：
正直者か不親切かを01のビット列にして、0～2^N-1までを探索する。
正直者である場合のみ発言を精査し、その回答と合致しているかを見る。
すべての発言に整合性があった場合、ビット列内の1の数をカウントする。
ここまでは簡単（Cはサンプルの出力で間違いに気が付いたので危なかった）。

D：
計算量的に、すべての組を計算することはできない。過去のXOR系問題の経験から、各桁ごとにビットの個数をカウントしていくという方針がまず思い付いた。
ここで、XORで1のビットが立つ組み合わせを考えたところ、（該当の桁が1であるAの個数）x（該当の桁が0であるAの個数）で求められることが分かった。
従って、各桁ごとに1の数をカウントし、それをxとしたとき、Σ_{k=1}^{59}(n-x)*x*2^kで表されることがわかった。
後は適当に組んで完成・・・と思いきやPyPyでTLE。
今回のパターンではPython3にしても早くなるとは思えなかったので、無理矢理C++で書き直してなんとかAC。

ここからは後日解いた分。

最初は各桁の1の個数を新しい配列に格納していたが、これが遅いと考えられたため、1-59のループの中でAiを1-nまで見る、というループに書き換え、Ai%2をxに足し、Aiを2で割るという処理を繰り返すことにした。
これによりメモリアクセスが軽減されたのか、PyPyでACできた。

E：

解説の通り、順番に見ていく。幅優先探索ではなく、全マスを順番に見ればよいため単純なh*w回のループを書けばよい。
これもPyPyでACできなかったのでC++で書き直してAC。手元の環境だとbool dp[80][80][12801];を宣言したところでSegmentation Faultが出たがコードテストだと問題なかった。原因は配列のサイズだと思われるが、なぜ違いが出たのかは調べておこう。

それとPythonでなんとかする方法も。こういうところで甘えているから伸びないんだなあと感じる。

F：

解説の意味を理解するのに時間がかかった。

まず、高橋くんがK個取る場合にありうるスコアの種類について考える。

具体的には、解説でいうところのX*K+D*Iとなり、このIのとりうる値をカウントしていけば良い。

ここで、X*KをDで割った余りについて分類するという話が出てくる。これはどういうことかというと、たとえばX=3、D=2とすると、3,5,7,9,11,13...と3以上の奇数が該当するわけだが、たとえば5,7,11,13と取った場合、36だが、9,27と取った場合でも、同じく36となる。このように、Kの値が異なるが、Sの値がおなじになるパターンが存在しており、それを排除してやる必要がある。

これを回避するために、X*K'%Dが、既出のKについてX*K%Dと同じである場合、X*K'=X*K + X*(K'-K)と変換することで、X*Kを基本とするパターンに合致させることができる。

この時、解説通りの方法で求めたIの範囲をL<I<Hとすると、L=L+X*(K'-K)/D、H=H+X*(K'-K)/Dとすることで、正しい値の範囲に変換することができる。

あとはそれらの範囲（L,H）をリストに入れてあげて、ソートした上でLの小さいものから順番に見ていけば、答えを求めることができる。

実装にはdictを利用したので、Python3で提出して無事AC。