ARC149

ぷよぷよ最強リーグ終了に全てを持っていかれた。3完で結果は普通。ARCは（問題は良いものであってもゲームとしては）クソゲーといういつもの。

A - Repdigit Number

怖い見た目だがよく見ると1つめの条件を満たす数はN*9通りしかないしmod Mで順番に生成すればMの倍数か判定できる。

B - Two LIS Sum

この問題にLISを求める能力があるのか考えたがわからない。ABのペアを自由に配置できるからLISより簡単な可能性もある。わからないので飛ばした。

Cを通して順位表を見るとハチャメチャに通されている。あんま関係ないけど順列であることを見落としていたことに気づいた。まあAが昇順になるようにソートしてBのLISを求めるよね。サンプルは通る。こんなに難しそうな問題なのにこれだけ通されていてペナ率も低いとなると、これが答えである可能性もある。反例を探してみるが作れない。提出してみてAC。本当にゴミみたいなゲームだ。解説は素晴らしい。

C - Avoid Prime Sum

とりあえず偶数と奇数をそれぞれ固めて配置したい。Nが奇数のときは少し複雑そうなので偶数のときを考える。mod 2でやっても偶数と奇数が隣り合う部分ができてしまう。そこで、mod 6で考えてみると、1と2、3と0、4と5、というペアが全部和が3の倍数になる。偶数同士の和は偶数だし、奇数同士の和は偶数だし、偶数と奇数が隣り合う部分は3の倍数にできる。和は最小で3なので偶数ならば素数でない。Nが大きいときについては解けた。実際に出力させてみると、これで解けている。提出してWA。

なんとサンプルすら通っていない。全部WAだ。3は素数だった。いやー、目視でわかりやすいように小さい数を境界に配置してたんだよね。そこを直すと、今度はN=3がダメ。手でしばらく修正を試みるが、できない。今やってるのABCのCだっけ～？という感じでnext_permutationを使い全探索した。今度はAC。これ速解きするの不可能だろ。

実装は、使う整数をmod 6で分けてvectorに突っ込み、さっきの3種類のペアを境界に配置していく。Nが奇数のときは真ん中から左右へ1と2のペア（他のペアより個数が少なくない）から順に。残ったものを奇数と偶数にまとめて空いてる場所へ置く。コードに落とすのが相当しんどい処理だったが、自分としては実装でいいパフォーマンスが出せたと思う。時間はかなりかかった。

D - Simultaneous Sugoroku

めちゃくちゃ簡単そうに見えるが、よく考えると状態数が多すぎて不可能に見える。

（追記）解説を見るとなるほど解けそうだ。しかしそれは自分が解けるという意味ではなく、解ける問題ではありそうというだけ。この問題を解けるような人との断絶を感じて絶望した。それでも、頑張って正しい答えを吐くコードを実装していく。脳が限界になったので提出してWA（いつもならある程度正しさを確認してから提出している）。それっぽいところを変えてもWAが増えるだけで、よく考えたらそりゃそうみたいな。ここから1週間放置した。本当にやりたくない。問題が嫌いとかではなく、むしろいい問題だと思ってるけど、難しすぎてやりたくない。実装がそこそこシンプルにできそうな問題だとわかっているのに難しすぎて自分にはできない。

今日改めて考えた。0を含まない閉区間の中の整数について最初その座標に置かれていたコマの移動先を考える。最初は1から100万まで。区間の両端と、負の方向へどれだけ移動したかと、区間を反転したかを保持する。1回移動した結果座標が正の側に多く残ったら、負の側のコマへ反対側のコマから有向辺を張る。0へ移動したものは何回目か記録する。0以下に行ったコマは区間から削除。負の側が多かったときも同様だが、常にコマが正の側にいるものとして考えたいので、同様の処理をしたあとに区間を反転させる。例えば、移動量が8でスタート地点が1から7のコマが負の側に残っていたら、移動量が-8（正の方向へ8移動という意味）で-7から-1のコマが正の側にあるという状況を代わりにつくる。0に到達したのがいつかというのは反転しても変わらないので、-7のコマが0に行ったら7のコマと同じ場所に記録する（グラフの頂点番号も単に絶対値で）。全部のコマが0に行くかM回の移動が終わったら、残ったコマについてどこにいるかを記録する。反転している場合は戻す（これをしていなくて（単に位置の反転だけしてて負の添え字使って）WAだった）。あとはグラフ（森）を辿って、0に行ったものは何回目か全部同じなので伝えて、0でない場所で終わったものは辺を辿る毎に符号反転して伝える。