結果
TOEFL iBTの対策をするかコンテストに参加するか迷って結局参加した。
三時間かけてレートを36溶かすことができました。
振り返り
A
普通に実装するだけだった。
B
最初は $2$ をどうにかして作ってそれで全てを割ればいいんじゃないか？と思い、どうにか $2$ を作ろうと頑張るが、色々と場合分けが発生して大変だった。最初に最大と最少を持ってきて適宜交換しながら割っていく方法を試してみたが、出来ず、毎回最大最小持ってきてそれらが同じになるまで割れば良さそうなことに気付いた。計算量が $O(tn^2)$ だから間に合わないかもしれん、と思って別の手を考えようとしたが、何も浮かばなかったので諦めて先ほどの考察を実装したら爆速で通って謎だった。出力をミスってて1WAでたが、Wrong answer on pretest 1だったのでペナがつかなかった。
今見返したら
It is guaranteed, that the sum of $n$ for all test cases does not exceed $1000$ .
って書いてあって、なるほどね、って感じがした。
C
むずすぎる。こんなん $a$ から順番に外側から並べて、文字の個数が奇数個の時はより大きい文字とペアにして、大きい方を手前、そうでない方を奥にして、余ったやつを小さいやつから前に貪欲に置いていけば終わり！と思って実装。Exampleいれて確認したら
abb
が
bba
になってた。これはどうしようかな…と思い色々考えた。奇数個存在するアルファベットがある、かつ、文字列の長さが奇数なら真ん中にそいつおいて残りで同じことすればいいんじゃね？と思ったが、実装だるそうだしbbccaで死ぬ。色々考えて奇数個存在するアルファベットがあり、それより大きいアルファベットの種類数が $1$ 個なら奇数個のやつを真ん中おいてそれ以外を大きい方のアルファベットでうめる、そうでないなら先ほどの実装をすればよさそうと考え、これを実装して提出してAC。テストケースの丁寧さに助けられた。
D1
とりえあえず \[ dp[(今の場所)][(1つ目のCPUの最後に実行したプログラム)][(1つ目のCPUの最後に実行したプログラム)] \] は計算量的にダメで、1つ手前のプログラムは必ずどちらかのCPUに使われるので次元が落せて、終わり！となり実装し始める。しかし「連続して同じプログラムを実行した場合最後の実行だけ $hot_i$ かかり、それ以外は $cold_i$ かかる」という問題だと勘違いしていたため、最後に実行したプログラムが $hot$ であったか否かを記録する次元も必要だと考え、 \[ dp[(今の場所)][(i-1を実行していないCPUの最後に実行したプログラム)][i-1はhotで実行されたか][第二引数のプログラムはhotで実行されたか] \] みたいなDPを書いた。めっちゃ大変だったが、何とか書き上げ、サンプルを入れたら全然違くて絶望した。なぜか小さくなっているサンプルもあったのでマジで謎だったが、入力を間違えてた。僕は毎行 $cold_i, hot_i$ が与えられ、それが $n$ 行続くと思っていたが、実際は一行目に $cold$, 二行目に $hot$ が与えられていた。これを書き直してACやろ！と思ったけどまだダメ。サンプルを眺めると
5 1
1 1 1 1 1
1000000000
999999999
というサンプルを見つけた。これが$4999999996$になるのわけわからん…なんで…？と思いしばらく考えたがわからなかった。問題文読み返したら誤読してて、マジで絶望した。最初の考察で終わりじゃん…となり、それ書いて通った。虚無。
D2
でかい制約で出来るんや～って気分になった。CPUの処理を飛び飛びに飛ばして行けば良さそうなんだけど最初なぜか「同じプログラムまで処理を飛ばす」ということしか考えてなくてそれを実装しようとしたんだけど、冷静になるとそんなことは無かった。処理するCPUが変わる部分だけに注目すれば適当にCPUを割り当てられるのでその方針で考える。$a_i, a_{i+1}$ で処理するCPUが違う時、$a_{i+1}$ は前のCPUと連続して実行されて～とか考えると、現在処理していないCPUの最後に実行したプログラムをセグ木におぼえておいてうまく更新していけばよさそう。まず初めに全部1つのCPUで実行したと仮定してコストを計算する。そして $i$ 番目と $i+1$ 番目が別のCPUで実行されていたと考えてコストを計算しなおした。これを書いたらWAがでて謎だった。良く眺めると更新する際に $hot$ になるとしたら $a_{i+1}$ なのになぜか $a_i$ の値を加算していた。書き直して提出したらRE。セグ木のサイズを $n+2$ で初期化していた。これを$k + 2$ に書き直したらWA。セグ木のサイズを直しただけで、アクセスするときの添え字が $n$ のままだった。これを書き直してAC。ペナが多すぎる。
E
あと1時間あるしEくらいなら通せると思ってた。 以下みたいなコの字型の配置がなければOKっぽい。
###
#.#
制約的にフローなのかなと思ってしばらくフローを考えてたけどいい物が浮かばず。あるマスが埋められてないのならそのマスから2方向は必ず空白が連続している必要があって、逆に2方向に空白が連続してるならそのマスは空白でよい、という案が浮かんだが、以下のような場合で死ぬ。
..#
...
#..
残り20分を切ったあたりで、行方向の区間をもって列方向にDPという案を思いつき、これを全力で書いたが計算量が悪かったり、考慮出来ないパターンがあったりしてダメだった。
感想
制約見てない、テストケース見てない、誤読する、というミスを全部やったのバカすぎる。Eは解ける気しなかったが、解くスピードはもうちょっと上げれたんじゃないかという気がする。Eは時間が無さ過ぎて最悪多次元DPを書き始めたけどコンテスト後に嘘解法であることが分かったので虚無になった。冷静になると最近調子悪いのに何で出たんですか？って感じだが、まあ出たかったのでしょうがない。次からは丁寧に解くようにする。とりあえずテストケースみない癖がずっと抜けてないのでテストケースを一通り確認する癖を付けるようにする。
upsolve
E
twitterで「埋められたマスに挟まれてるマスを行ごと列ごとに埋めて、都市がつながって無かったらうまく繋げる」みたいなツイートを見た。たしかにそうすればコの字型全部埋まるし無駄が無いなぁと思って感心した。列方向に走査して行方向は適宜区間をとるDPを考えて、そのときに行方向は最左と最右を含まなければいけないな～とかやってたので、それを列方向にも適用しようとすれば思いつけたかもしれんなぁと思った。あとはコの字型を潰すってところに注目するのもアリだったのかもしれない。
この操作で二つの都市が結ばれなかった場合はそれらを繋げた後にもう一度同じ操作をすればよい。先ほどの操作でつながらなかったことから、都市は対角の位置に行と列を共有しない形で位置していることが分かる。よってそれぞれの都市を含む最少の長方形を作ったのち、これらの最短距離を結べばよい。
以上のアイデアを愚直に実装したら以下のケースで死んだ。
6 5
..##.
...##
....#
#....
##...
.##..
これが以下のようになってしまう。
..##.
..###
..#.#
#.#..
###..
.##..
いろいろ試した結果、埋める操作において、行埋め→列埋めの順番で行っていたが、この列埋めの際に都市がつながった時は行埋めをやり直す必要があることが分かった。連結な成分に対する操作なら一回で良い気がする。列埋めで新しく行埋めをする必要がある場合をいろいろ描いてみたらそんな気がした。とにかく埋める操作を適宜足したものを提出してAC。解説をよんだが、確かに交互に伸ばして十分な回数埋める操作を回すのが安全だねって感じがした。TL的にも余裕あるし。
これ本番で解けたらめっちゃ気持ちよさそうな問題だな～と思った。