ABC326

6完。

A - 2UP3DOWN

難しいので言われたとおりに実装する。解説みたいにやったけど、y-xを計算しとけばよかったじゃん。

B - 326-like Numbers

3桁固定なので迷うけどまあNから1000未満まで回す。これ制約の919は326-like numberの最大値なんだろうけど、ここが900とかだったら引っかかる人出そうだよな。ということで、919以下ではなく1000未満を使った。for文で桁毎にばらして条件を書き見つかったら出力して終了。

C - Peak

簡単なしゃくとり。あまりにもスッと書けてやや警戒したが提出したらACだった。問題設定がシンプルかつ自然。

D - ABC Puzzle

各行でnext_permutationを使うとN=5で60通り。これの3乗なら通ると思い実装する。ABCの時間をこんなどうでもいい実装で浪費させられるの本当に嫌い。こういう実力を測りつつ俺にとって不快感も少ないような出題ってできないもんかねえ。できなさそう。サンプルを手元で実行してみると、2秒で終わらない。最初無限ループと思ったけど、これは3乗じゃなくてN乗だ(当たり前)。通る可能性がないではないが、まあ高速化は必要だ。各行の最も左の文字を都度チェックするようにして、これでだいぶ速くなった。3倍ではと一瞬思ってしまったが、3^N倍速くなっている。もっと枝刈りできるけどこれで速さは十分なので提出。

E - Revenge of "The Salary of AtCoder Inc."

後ろからDPできそう。計算量は2乗になるかもしれないが、とりあえずそれを書けば高速化もすぐ見えそう。最初に出た目がiだったときの期待値を求めていく。その期待値の、後ろからそこまでの和がわかれば、そこの期待値もわかる。ということで、DPテーブルは要らない。Nの逆数だけ前計算しておいて、期待値を求めて和の変数に足していくだけ。N個の期待値の和がわかったら、最初にどの目が出るかは等確率なのでNで割れば答え。

F - Robot Rotation

xyどっちに進むかは交互。なんか「Robot Arms」みたいのを覚悟したけど、考え進めると単にナップサックみたいな話だった。しかし値が大きくてナップサックはできない。xyそれぞれ40ずつなので半分全列挙できるね。復元が必要になるので、それができることを頭の中でなんとなく確認してから進める。ループでやったけど、配列の添え字を間違えるリスクがあるので関数にしたほうがよかったかもしれない。半分全列挙とその復元の重実装が終わったら、それをLRに変換する。前回の向きと今の値をどっちの符号で使うかはxorでよさそう。xyどっちかは場合分けしようかと思っていたが、これもxorでよさそう(逆になる以外の変化がなさそう)。ということで3つxorしてLRを決める。

サンプルが合わなかったが、別解を出力してるだけかもしれないし提出してしまった。配点的に早解き回っぽいのでリスクを取って早く提出する(レーティング的な)意味があると思った(そういう理由を付けて考えることから逃げた)。サンプルがWAで、復元した和を計算すると合ってない。この計算もすぐに実装できないと思ってやらずに提出してるんだけど、WAを見てからかなり短時間で実装できている。見積もりは本当に難しい(というかできない(実際にできたことか、これだけの時間できていないということからしかわからない))。LR変換ではなくこっちが間違いというのは意外だった。見直すと、復元のためにインデックスも含めてソートしていたのにそれを使っていなかった。

G - Unlock Achievement

見た目はフローだけどわからなかった。終了後燃やす埋めると聞いてもわからない。

(追記)終了後燃やす埋めると聞いてけっこうな時間考えたら見えてきた。スキルを5個並べたところからアチーブメントへ辺を張る。スキルは、レベル5から4,3,2,1と一直線につなぐ。SからTに流すとして、Sは「使わない」、Tは「使う」、それ以外の各頂点をどちらかに塗り、「使わない」から「使う」へ張られた辺のコストの和を最小化する問題が最小カットでこれはatcoder::mf_graphで解ける。スキルでは、どこまでが「使わない」かに注目する(単調でないなら最適でない)。レベル4まで「使わない」場合、レベル3以下は「使う」ことになりそことアチーブメントを結ぶ辺のペナルティはなくなる。レベル4が必要なアチーブメントでは、そのスキルのレベル4から辺を張る(レベル4以上にしないでアチーブメントを達成するのは禁止なのでコスト∞)。レベル1は常に達成されるのでスキルの頂点は4個ずつでいい(5個あってもいいが流量0なのでなくても同じ)。

全て達成したかどうかでA_iのコストがかかるか決まると考えて、絶対5^Nとかかかるだろと思ってしまったが、一つでも達成できなかったら∞の罰金なんだね。最小カットが久しぶりすぎて勘が取り戻せなかったのもあるが、スキル部分のグラフの作り方が難しかった。わかってしまえばフローとして見ても自然だが。最大流のことは考えず機械的に最小カット問題へ帰着できればそれで解けているんだけど、どうしても考えてしまう(今回の、スキルレベルが下がるにつれ流量が絞られていくあたりは気づくと面白い)。