ABC307

ABDEの4完。Cを飛ばしたのは正解だった。コンテスト中の貴重な時間をあんな実装に使うことを考えたら、レーティングなんてどうでもいい。レーティングは1900を割ってしまった。Fの難しさに圧されて勘違いしていたのが響いた。気温の高さや冷房に慣れておらず、体調が悪かった(頭も悪かったと思う)。C問題は嫌いだが、実力を測るという意味では良い問題で、水パフォも妥当。

A - Weekly Records

7回入力を受け取って和を出力というのをN回。" \n"[i == n - 1] が使える構造だと気づくのに時間がかかった(最初からわかっていれば1分切りが狙えた)。

B - racecar

全探索。太字の「相異なる」に注意する。

C - Ideal Sheet

5分くらい考えて解き方は浮かんだが、あまりにもやりたくないので飛ばした。具体的な方針は、それぞれをbounding boxに縮めて4重ループでAとBの置き場所をXの内部で全探索(例えばAがXからはみ出ていたら実行されないので正しく動く)。全体で6乗になるけど100万なので大丈夫。

終了後やってみたが、等号抜けなどの細かいミスがいくつかあり25分くらいかかった。最初に考えていた方針でACできたものの、書き始める前には細部を全然イメージできておらず、ミスの検出ではサンプルにかなり助けられており、これでレーティングが下がるのはあまりにも妥当。しかし、こんな問題が出されるコンテストがratedになる実力帯にいることが情けなく本当に嫌な気持ちになる。

D - Mismatched Parentheses

スタックみたいにやるんだろうなーと思い、簡単な実装になりそうではあるが、実際に詰めていくのはけっこう難しい。一意になるって書いてあるんで使わせてもらう。'('後の最初の')'で削除が走り、削除後もなんか同じようやる。実装では'('の位置をスタックに入れたけど、実際には'('の個数としてしか使わなかった。答え用の文字列にpushしていき、'('がそこにあるなら(この判定に個数を使う)'('に当たるまでpop。やや自信なかった。

E - Distinct Adjacent

渡す整数だけ謎に0-indexed。簡単そうだが、実際に簡単。対称性から、人1が0のときの通り数のM倍が答え。人1から人NまでN-1回遷移するDPをして人Nが0以外の通り数を求める。0へは0以外から1通りずつ。0以外へは0からM-1通りと0以外からM-2通りずつ。合計でM-1通りずつになっているかで検算できる。

F - Virus 2

BFSっぽいと思った。ダイクストラ法の変形で行けそうだと思う。累積和で大小関係とるようにして、日数も持つようにして、違う日になるなら累積和の値まで切り上げてからみたいな処理を頑張って書く。サンプルが合わなくてサンプルで時間をかけて検証していると、違う問題を解いていたことに気づく。累積和をとったことで、遠い部屋も日数をかければ感染するといつの間にか思い込んでいた。切り上げの処理が本当に難しくて、混乱するのも無理はない。さて、今以降の最も早い日でX_iが辺の長さ以上になるものを探さないといけないが、これが難しくてわからない。時間もないのでGへ。

Fに時間をかけすぎた。だが、実力を上げる以外の方法でこれを回避できるかというと。

(追記)布団の中でセグ木二分探索を思いついて、起きてから考えた。かなり苦労したがAC。logを2つ付けたと思っていたが、各辺を1回ずつしか処理しないのでこのlogは掛け算ではなく足し算だ。最近、ACしても(してなくても)解説がわからないことが多い。学びが少なくてよくない。

G - Approximate Equalization

Gを読んで順位表を見ようとしたら少しの間読み込まなかった(2分とか?)。Tampermonkeyのスクリプトが悪さしてる可能性あるのかなあ(ないと思ってたけど)。拡張は全部自分で書くというのも手だが、それにはさすがに力不足かもしれない。

整数T,Kが与えられ、N-K個をTに、K個をT+1にせよ(できる)という問題。K=0なら簡単なのに。残り20分もなくて、最小費用流に飛びついたが思ったより辺が増えて爆発四散した。終了後落ち着いて考えるとDPができそうだ。これも終了後更に40分かかってるからなあ。F問題が存在しなければギリギリ通せたかなくらい。

数列の要素がN個あり、境界がN-1個ある。各境界について、最終的な左側の合計がわかればその境界を通る荷物(1)の個数もわかる。逆流が必要ないことは証明してなかったが、まあ左から順にその量だけ流せば合うからいいよねたぶん。DPは、自分のすぐ右の境界を基準にして、左側にT+1がj個あるときの、自分を含め左側の境界の流量の合計の最小。なんかjからの遷移もj-1からの遷移もabs(符号付きの差の合計 - j)で、えらく単純な形になった。ACしたけどなんもわからんな。