結果
ARC初の3完。ARC128では0完で泣きそうになっていた私ですが、ついに3完できる日が訪れました。感慨深いです。
A問題
E8さんの競プロ典型90問の「辞書順は前から」の考えに則って解きました。前から見ていき、a[i-1]>a[i]となるような部分が出てきたらa[i-1]の数字を取り除くことが決定します。a[i-1]>a[i]となる部分がない場合、"employee"より"employ"の方が辞書順が前理論に基づいて末尾の数字を取り除きます。break を書き忘れて1WAを喰らってしまいました。自分らしさ全開です。
B問題
最初は解ける気がしませんでしたが、諦めずに紙とペンを使って考察し続けました。思考を進めていくと少し前に解いたARC126のB問題と類似していることに気づきました。ARC126_Bでは接続可能な辺が与えられていましたが、今回はa[i]がb[j]の約数であればa[i]とb[j]は接続可能であるというように自分で接続可能な辺を求めることで、同じ問題のように扱うことが可能になりました。あとは、ARC126_Bの自分の回答を見ながらSegTreeを使って、辺が交差しないという条件下で、最大となるような接続する辺の数を求めて行きました。
C問題
B問題まで解けて満足していたので撤退しかけていたのですが、問題に目を通して本当に良かったです。
まず、sum(a)%kとsum(b)%kが一致しない場合、総和をkで割ったあまりが2種類あることになり意味不明なので-1を出力すべきです。次に、総和はなるべく大きい方がいいので、全てのマスにk-1を入れるのが理想です。よって、ans=(k-1)*h*wと設定し、ここから条件に当てはまるように引き算していくことにしました。
i行目に着目します。現在i行目の総和をkで割った余りは(k-1)*w%k（以下、xとする)であり、これがa[i]と一致しなければなりません。x>=a[i]の場合、x-a[i]をi行目の適当なマスから減じることで矛盾しない書き込みとなります。x-a[i]+zk(0<=z)を減じれば矛盾しませんが、マスに書き込まれている数字は大きいほどよく、減じる数は小さい方が良いのでx-a[i]を減じるとして進めます。x<a[i]の時、x+k-a[i]をi行目の適当なマスから減じることで矛盾しない書き込みとなります。
以上の操作を全行に対して行って最終的に残ったansがaに矛盾しない最大の総和です。同様にans2=(k-1)*h*wと初期設定し、行とは独立に全列に対しても上記の操作を行うと、min(ans,ans2)が答えです。
総括
C問題は正当性を確かめることなく、通ったらいいなーくらいの気持ちで解答を投げたので全くもって実力とは言えませんが、それでも青パフォを出せたことはとてつもない自信になりました。大きな大きな目標だった入水を達成できて感無量です。次の目標は水色定着です。
