ABC229

結果的にはノンペナ7完。よかった。

A - First Grid

黒マスは2個以上ある。(その制約がなくても)全部で16通りしかない。黒マスが3個以上あると必ず連結(全パターン思い浮かべた)。すると、黒マス非連結は市松模様の2通りのみとわかる。仕方がないのでこれで書く。受け取った文字列を連結して4文字にしてベタ書き。

まさかの、解説と同じ方法。しかも解説になぜその2通りしかないと言えるかが書いてない。

最近ABCのABが難しいのをよく思っていないのは、今回のABもそうだけどミスが入りやすい(ミスがないことを短時間で確認しづらい)タイプの問題だから。難しいだけなら自分はいいけど、こんな問題でペナの不安(あるいは確認コスト)を負うのは、特にratedコンテストではやりたくない。

B - Hard Calculation

入力部分をA問題から流用できるので、した。「繰り上がりが生じる」ってwell-definedか?まあ下から筆算するときにと解釈する。繰り上がりは連鎖することがあるが、そもそも1回以上同士は区別する必要がない問題だ。2つの文字列を末尾から短いほうの長さぶんループして和が10以上になったらHard。

解説を見て、これは自分が悪かった。実装も下手だったし、実装の選び方もダメだった。

C - Cheese

問題文を画像として見ればナップサックだが、日本語として読めば貪欲だ。あとはいつもの。

あー、minで使う量を決める実装があるのね。

D - Longest X

最終的な連続するXが占める区間を決めれば累積和で(操作が何回必要か)わかるが、区間を全探索はできない。ここで二分探索ができることに気づく。あまりやりたくないが、他の方法もパッとは出てこないし競技としてこの問題を早解きしてみよう。J個連続させることができるか判定する。範囲は1からN+1まで(0は必ず可能、N+1は必ず不可能、探索はNまでで戻り値はN+1まで)。初めて不可能になったJを求めて1を引いたものが答え。判定は累積和を使えば全探索できる。

解説を見て。あ、しゃくとりなるほどなあ。'.'をK個以下含むようにやればいいのか。二分探索ってわりと逆にする(操作回数固定で何個連続にできるか→連続にする個数固定で何回操作が必要か)けど、しゃくとり法にそういうイメージがなかったかもしれない。今の自分にとってはかなりアクロバティックな発想に感じられた。

E - Graph Destruction

逆からやればよさそう。頂点は消さないことにする(あとで消えてるぶんを引き算)。連結成分がN個の状態から始まって、頂点Nから順に、自分より番号が大きい(小さいになるコードを書いてしまいサンプル合わず)頂点への辺だけをつないでいく。

ここまで、早解きに成功。

F - Make Bipartite

頂点0を白として、他の頂点を白か黒に塗り、色が同じものをつなぐ辺のコストの和を最小化せよ。フローもちょっと考えるが、ペナルティの付き方が逆だし、そもそも制約的に無理。となると貪欲くらいだが、やはりあちらを立てればこちらが立たずで、フロー以外の解法があると思えない。FG双方を読んで少し考えたあと、順位表を見てFを片付けようと思うが、無理だったのでGへ。

Gを通して残り20分ちょい。何もわからないが、頂点1から順に決めていく(これは最初のころから考えていた)のを考えていたときに最後の色でまとめられるイメージがよぎってDPに気づいた。フローでさえ解けないものはDPだとあれほど言ったじゃないか。実装していて気づいたが、最後の頂点の色だけでなく、頂点1の色でも分ける必要があった。残り10分だったが、超スピードで書いてなんと間に合った。サンプルも一発で通りホッとした(これでダメなら直す時間がないので、嬉しいと思う余裕がない)。

G - Longest Y

既視感があったけどD問題と似ていた。XがYになってる。スワップではなくYを移動させると考える。とりあえず、連続したYを作るのに左端から順にYを使っていく場合を考える。どこに移動させるかを決めると操作回数もわかる。よくある中央値の位置にするとコストが最小になるやつに似ているが、移動先が1個ずつずれている。しかし、使うYが決まっているので、i個目のYの位置からiを引いたものを考えればその中央値でよさそうだ。これはYを左端から順に使う場合以外でも使える。ずれ方が同じ。中央値を与える位置がわかれば、累積和で移動コストがわかる(元の値が定数だけずれていても関係ない)。これも二分探索。今度は文字列の長さではなく、Yの個数を使う。Yの位置からそれが左からi番目のYならiを引いたものを求め、更にその累積和も持つ。あとは、J個連続にできるかを判定。[I - J, I) という区間を全探索。中央値の位置を求めるために2本のpriority_queueでやるやつが必要だとずっと思っていたが、単に真ん中の要素でよかった(真ん中が2つあればどちらでもいい)。サンプルがなかなか合わなかったが、添え字を大量に間違えていた。何回も直してサンプルがやっと通ってAC。やはりGが解けると嬉しい。

(追記)これもしゃくとりでできるのか。右に伸ばすとK回に収まりにくくなる。左を縮めると収まりやすくなる。単調性は確かにあるので右を固定してK回でいけるようになるまで左を縮めればいい。これも今の感覚では嗅ぎ付けられないな。単調性がわかれば書くことはできる。