ABC175

5完。色々(体、頭、モチベ)調子悪かったけど、順位はけっこうよかった。たぶん得意セットだったけど、得意セットは自覚できない。この重実装でノンペナは運もよかったと思う。

A - Rainy Season

方針にかなり迷った。結局、3文字という情報は使わずにB問題的な書き方をした。この実装はそれなりに難しい。8通りのif文とか、Rの個数を数えて"RSR"だけ場合分けとか、考えたけどまあ迷ったら汎用を書く。

B - Making Triangle

長さが異なるというの読み飛ばして混乱した。条件をif文でゴリゴリ書いていく。一応、「三角不等式」でググった。ソートを思いついていたことを思い出し、実装が少し楽になった(比較が隣同士だけでよくなるし、三角不等式も1個だけでいい)。三角形について詳しいわけではないので、けっこうな負荷だった。実装の時間もかなりかかった。

C - Walking Takahashi

貪欲に原点に向かって動き続ければいい。移動回数の偶奇によって、到達できる場所が2つに分類されることに注意。絶対値の最小化なので、Xは絶対値とってしまっていい。さて、制約が10^15とかなので、K回同じ方向へ進んだときどれだけ移動できるか計算するとオーバーフローする。__int128_tを使えば行けるけどさすがに使わん(ABCのCだから使わない簡単な方法が存在してるはず)。そもそも10^15くらいしかない世界の話なのでそこまで大きな数を扱う必要はない、と考えていると、割り算すればいいと気づく。原点付近へ行くためには何回移動する必要があるか、これはX/Dでわかる。とりあえずmin(X/D, K)回は原点に向かって移動していいので移動して、あとは原点の周りを往復するだけだから、残った回数を2で割ったあまりにして残り高々1回をシミュレーション。

D - Moving Piece

なんで5000なのかなーと思ってたけど、どこから出発してもいいのね(書き上げてから気づいた)。よくあるサイクル見つけるやつ。苦労しながら実装するだけ。簡単なのはわかっているけどいつもながら本当にしんどい。最後にそのマスに来たのが何回目の移動かとそのときのスコアを記録する配列を用意する。最大値を更新しながらシミュレーションして、初めて同じマスに2回来たときにそのループが得か(スコアが前回来たときより増えているか)をチェックして、得でないならそこまでの最大値を出力して終わり、得なら限界までループを回し(残った移動回数をループのサイズで割る)、残ったぶんをシミュレーション。それを各出発地点についてやる。シミュレーションするとき、色々な判定が入るのでどのタイミングで更新するかが難しかった。

E - Picking Goods

3個までという条件が不自然で不安になる。サンプル2でその条件が使われていることを確認。典型DPに見える。メモリが足りることを確かめてから書き始める(マスは10M個以下で、3個までだから4通り、スコアは64bit整数で、320MB、ほかにvを持っても足りる)。ここで、スタート地点は上や左に移動元がないという性質があり、それをどう扱うか、実装方針を決める必要がある(大きな分岐点)。上と左があるかで4通りの場合分けを書くことにした。このムーブはあまり褒められたものではないかもしれない。経験があり頑張れば書けるとわかっているからつい選んでしまう。もう一つ、DPテーブルに入れる値を、「ちょうどl個拾ったときの最大」と「拾ったのがl個以内の最大」のどちらにするかも決断する必要がある。実装が簡単になりそうなので後者にした(そのぶん考え方が難しくなる可能性があった)。

あとはいつものDPだけど、やはり苦戦した。1行目は拾わないときのスコアが0固定だけど、2行目からはそうじゃないのをうっかりした(拾った数が1個から3個の3通りでいいと思っていた)。4通りとはいってもそれぞれ強化版みたいな関係になっているので、書けたらコピペして修正みたいにやっていける。遷移について、上からか左からかというだけでなく、拾うかどうかも必要で、それを4通りの個数について埋める必要があるので、思ったより複雑だった。サンプルが通らなかったのは、「上から遷移して拾う」というケースが抜けてたから。それが抜けてるのだいぶあやしい(他にも抜けがありそうだ)けど、サンプル通って提出したら通った。体調が悪いぶん割り切って立ち回れたのが幸いした感。

F - Making Palindrome

個数も少ないし色々できそうだが、結局N!通りの全探索とかはできないわけで、そうなると工夫のしようがないなあと思った。条件を付けて探索するにしても、計算量が2^Nにも行かないようなやり方が存在する気がしなかった。