【12日目】第二回日本最強プログラマー学生選手権に参加!
タイトル通り。実は予定があって17:30までしか参加できないのでかなり迷ったのだが…。参加を決めた理由としては、まあこれが原因でRatingが下がるということはないだろう、というのと、単に一刻も早く力試しがしたかったのと。結果はご覧の通り。
短い時間で解かなくてはならなかったのは痛手だが、Atcoder Problemsで見る限りE以降は一気に難易度が跳ね上がっているようだし(解いていないので何とも言い難いが)、そう思うと時間があったとしても4完が限界だったのかもしれない。
Dまでは割と簡単めだった(茶以下)が、それ相応に解けたと思うので良かったと思う。
以下は具体的に各問題を振り返って。記載のないA,C問題については特に問題がなかったと思う。
B - Xor of Sequences
これ数列の各要素の値が小さいから、二つの数列それぞれに含まれる値の要素をbitsetの形で表現してXORとれば良いんだよね…と終わってから気づいた。馬鹿すぎる。無駄に時間がかかってしまった。B問題だからといって油断せずに、制約条件が緩くなっているところはないかよく確認しよう。
D - Nowhere P
最初DPでやろうとしてサンプルケースでTLEなった。制約条件はよく確認しよう。そこから少し考えて(N,Pが小さい場合で実際にやってみて)漸化式立てなくてもと言う式で一発で解けるね、と気がついた。いつもこうやって難しく考えすぎてしまうんだけど、問題を見たら
1に一つの立式で(要はO(1)で)解けないか検討
2に全探索でTLEならないか検討
3で初めて他の手法を考える
というのは教訓としておさえておきたい。