競プロ日記

順位: 785

パフォーマンス: 1446

新レーティング: 1050

差分: +73

4完
ご飯を食べながらちょっとゆっくり参加。
Cが難しいというかややこしかった。
Eは途中で頭おかしくならなかったらかなりワンチャンあった。

かんたん。
bustってブラックジャックで普通に使うのかな？

反転した文字列用意したら分かりやすくなるというテクニック。
別にいらなかったね・・・。

ややこC。
制約がbit全探索だけど貪欲的にも解けそう・・・？
でもbit全探索の方が確実だからそっちで。
C問題でbit全探索なんか使うか？とかなり訝しんだが、bit全探索なら解けるという絶対的な自信があった。
Cにしては相当に実装が重かったのも訝しみポイント。
直近で解いたABC112 C Pyramidを思い出した。

正直者を決めた場合、正直者が正直者と示した人のみを確認すれば良いと思ったのだが、サンプルが合わない。
そうじゃなくて、正直者が正直者と示した人がさらに正直者を示して、と繰り返す必要があった。
それを実装しようとしてキューに正直者入れるかと考えたところでbit全探索じゃなくなった。
bitが指し示す正直者を使おうということでbit全探索に戻ってきた。危ない危ない。

この実装でミスしてしまったのが、bitが立っているかどうかと正直者かどうかの一致判定。
普段bitのi桁目のビットが立っているかどうかを調べる際、if(bit & (1 << i桁目))と書くのだが、これはifの条件式が0以外をtrue(=1)にキャストすることを踏まえており、i桁目のビットが立っていた場合に取り出される値は(1 << i桁目)である。
これをそのままif(0or1 == (bit & (1 << i桁目)))としてしまったため、1桁目のビットが立っていても(1 == 2)の比較が行われてfalseになってしまう。
1にキャストされるから普段の書き方で良いというのは間違いなく頭に入っていたのだが、ふとしたところでミスる。
これからはif((bit >> i桁目) & 1)の書き方に統一します・・・。

もう1つ書きたいことが、ビットの数え方のお話。
実は競プロをやってみようかなと思い立ったきっかけがビット関連の演算。
ビットを立てたり消したりMSBとか立っているビットの数え方とかすごい鮮やかだなぁと。
別に競プロでしかビット使わないわけではないが、意識するのは組み込み系か競プロだろう。
立っているビットを数える関数は2年くらい前に作っていて、たぶんそれ以来初めて使った。
分割統治でO(log64)なのでほぼO(1)の実装。
他のビットを数える系も大体分割統治でO(log64)でできるのだが、LSBはde bruijn sequenceとかいう闇の数字を使って真にO(1)で計算できることを最近知った。
O(N)のRMQに使っている。
立っているビットを数えるのも真にO(1)でできたら良いなぁ。

ここまで50分。
相当きついと思いながらのD。
C解いてる途中に質問タブが(1)となっているのに気づき、見てみると「Xor Sum 4」の文字が。
EかFかなーうわー・・・、と思っていたのにD問題開いたらまさかの。

見た感じ桁毎に分けられそうだしXor Sumだし、ということで桁ごとに分けて考える。
どのAiも使われるのはN-1個なので、Aiを固定した際の合計を計算できれば良し。
Aiのd桁目が1なら他のAi以外のd桁目が0のときにその桁が1、逆も然りと、普通にカウントしたら良いのでは？
Xor Sumにしては簡単だけどなぁと思いながら実装するも普通にサンプル通ってAC。
Cの遅れを少し取り戻せた。

ここまで63分。
単純そうで難しそうだという第一印象。
色々考察して、80×80のサイズと、ABも80までなのでその差も80までというのが鍵っぽい。
差が80以内を使うということは、差の合計を0にするように足していく場合、差の合計の最大値は80×2くらいまでに収まることが保証できたりする？
とりあえずDP使って解けそうだなぁ。

ここまでかなり良い感じの考察だったのに、ここで頭がおかしくなる。
こういう右か上かしか行けないABC145 D Knightでやったなぁ。
確か全通りは、と思い出すより早いと解説PDFを見に行く。
[右と上を選ぶ回数の合計]C[右を選ぶ回数]の簡単な組み合わせだ！
つまり160C80 = 160*159/2 = 12720だ！

？
ちょっと頭に思い浮かべたのが3×3のマスで4C2 = 4*3/(1*2)となり、なぜかそのノリのまま計算してしまった。
そこから全通り調べて最小値調べれば良いかなぁと。
この時点で頭おかしくなってるので次もおかしい。
最大80だし(?)、通った|Ai-Bi|を大きい順にソートして、合計が正ならマイナス、負ならプラスで合計して行けば必ず最小値になるのでは！？
そんなわけない、貴様ナップサック問題知らずか。
で実装して間に合わなくて、コンテスト終了20分後くらいにそのままの方針でTLE出して終わり。
5,5,4,3,3とかの場合、5+5-4-4-3=0にできるが、上から順にプラスマイナスの方針だと5-5+4-3-3=-2になってしまう。
ということで色々だめ。

良さそうな解法は、最初の考察を進めて、差は80以内になるなら全部プラスで計算しても80*160=12800になるので、DP[x座標][y座標][現在までで作れる合計値]でDPしていく。
80*80*12800=81920000 < 10^8でたぶん間に合う。
あんまり解説読んでないけどたぶんこれで行けると思うので、後で改めて解いてみる。
実際全部プラスなんてことはないので、間に合わなければ少し節約できそうか？

Eと一緒に問題を眺めて、シンプルな問題で解けそうな解け無さそうなわからなかったので、順位表見たら圧倒的に難しそうだったのでパス。
シンプルな問題は簡単かやべーか二択だな。

まとめ

Cで時間溶かしたのは反省だが、間違いなく今回のCは難しかった。
Eは解けても良かった。
今までの解けても良かったよりかなり強めの解けても良かった。
全通り調べても良いなんて意味分からないことを考えなければ、次に進めるのは最初の考察の続きなので、80*160しても制限に収まると気づく可能性は十分あっただろう。

レートは順調に伸びてるものの、次も4完なら水色は厳しそう。
年内はAGCが1回予定としてあるが、ABCはもうないのかな。
AGCも参加する予定だが、できれば後1回ABCで余裕持たせてほしい。