オンサイト参加権ゲットなるか？
【事前作戦】
問題を見ずに配点だけを見て解く順番を決めるのは好きじゃないけど、今回は配点が 2+3+5+6+8+10 と細かい＆多くて、時間が 100 分と短かったので、今の自分の実力的に解く順番を決めた方がよさそう。
ボーダーが 4 完早解きだった場合は勝ち目が薄いので、それをまくれる道を残したい。具体的には 2+3+5+6 に 3+6+8 が勝つので、その目を残したい。
いずれにせよ D が解けないと話にならないので、D を最初に見ることとする。
その後、D ができたら E, F をチェック。実力的に解ける気がしないけど、できそうなら触っても良い。だめそうなら保留し、いったん B にいく。B はさすがに解けそう。
で、もう一回 E, F をチェック (順位表も見る)。やっぱダメならおとなしく 4 完ルートへ、いけるなら上へ。
万が一 D がだめそうなら、一旦前からやって点数を確保し、D, E ,F から何か取れそうなものを取る。
こんな感じでどうか。
【実際の経過】
D 開く。グラフだが、構成ゲーなので出来そう！小さいところで実験して、$N/2$ で出来たのでとりあえず投げる → WA (15分)
たくさんのケースで WA だったので、もっと縮みそうとわかる。ここで条件を整理したら、もっと強く $\log N$ の構成が思いつく。実装して投げる → AC (28分半)
次に B へ ( EF を見るのを忘れてた(おい)、でもまあ変わらんか)
転倒数？BIT？と思ったが $N$ が小さいのでいらないか。愚直に実装して投げる...と思ったら、同じ数も OK だった(それはそう)。対応してなかったので修正して投げる → WA (35分半)
は？いやちゃんと修正できてなかったわ。ちーん。再修正して投げる → AC (41分15秒)
この時点で 2WA なので早解き競争では不利。じゃあ E か～と思ったが、この時間でもそんなに通ってなかったのと、問題もグリッドなのに $H, W, N$ が大きくてなんかむずそうだったので回避。F もこの時点で AC が 1 人だけだったので無視。
よって 4 完ルートへ。C を開くもなんにも出なかったのですぐに A でとりあえず稼ぐ。問題は、うん、まあ、はい。実装 → AC (47分)
残るは C. 具体例書き出したりして性質を探ってたら、ようやくかけ算に帰着できた。このへんで 70 分経過。そこから微妙にバグらせつつもなんとか実装。あんまり証明できてないけど投げてお祈り → AC (89分) やったぜ！
あと 10 分。EF を再確認するもなんにも分からんので、お祈りの踊りをする。終了。
【問題の詳細】
A
はい。5 分なんでまあよさそう (ほんとは 3 分やって♡)。
B
ブロックに分けて、ブロック内での転倒数と、ブロック間の転倒数を計算。
ブロック内の転倒数は今回なら $O(N^2)$ で十分。それに $K$ を掛けるとよし。
ブロック間の転倒数は、ブロックの選び方 $K (K - 1) /2$ に $2$ ブロック分の転倒数を掛けるとよい。同じ数字があるのを対処できず WA を吐いたので、冷静に。これも $O(MAX(A)^2)$ でできる。
300 にしては真面目にカウントさせられた感。まあ低配点はわからんね...
C
むずかった。最初 DP かと思ったが、無理そうだったので実験して思いついた。
置く順番は関係ないので、区間の決め方をカウントしたい。
ここで、区間がカバーする個数 (の偶奇) は、各マスが左端か右端かどうかの情報のみで決まる。正確には、各マスについて " [ " か " ] " を置いて正しい括弧列 (四角括弧列だけどめんどいので略) を作ることを考えると、最終状態と括弧列の一対一対応がつく。これは要証明だが、少し考えると互いに逆対応がすぐ作れるのでよい (下でちゃんと証明)。
よって、与えられた文字列を括弧列に変換し、括弧列に対応する区間の置き方をカウントすればよい。カウントはよくある「保留作戦」が使える。つまり、括弧列を前からみて、 " [ " だとストックし、 " ] " だとストックから一つ選ぶ。実際にはストックした " [ " の個数 $t$ について、$t = 0$ からはじめて、 " [ " なら $t$++, " ] " なら答えに $t$ を掛けて $t$-- する。
なお、正しい括弧列でない場合は答えは $0$. また、最後に $N!$ を掛けること。これで $O(N)$ でできました。
---
さっきの証明
B, W は 1, 0 に変換。" [ " を置くとそのマスの前と 0, 1 がスイッチし、 " ] " を置くとそのマスの後の 0, 1 がスイッチする。またこの効果は重複する。
なので、前から括弧列を見て、同じ記号だと 0, 1 がスイッチ、違う記号だとそのままとなる。
冷静に " [ " の効果を探り、その性質から、差分に注目すればよい。
---
この方針だと、括弧列に帰着するのが割と本質だったっぽい。それを思いつくまで凄く時間がかかったなぁ。区間を置くという挙動をちゃんと理解するのが大事だったかも (上の証明みたいなやつ)。そうすれば、括弧列を満たす区間のカウントにすぐ移行できたかもね。このへんは考察力、典型帰着力という感じか。
なお「保留作戦 (かけ算作戦)」はなんか最近見た気がする。典型の一つですかね。
D
構成ゲー。条件をちゃんと言い換えるのが大事で、「各色だけの部分グラフが奇サイクルを持たない＝二部グラフ」とわかれば、この問題が「完全グラフを、いくつかの二部グラフに分解する、その最小個数の例を構成せよ」と言い換えられる。こういう帰着を強い人はすぐにやってて、現状ここで一番差がついている。なので精進あるのみ。
さて問題に戻ると、とりあえず 1 色で $ K_{N/2, N/2} $ を作れば、残り $K_{N/2}$ が $2$ 個で、色は使いまわせるので、これで $\log N$ 色の構成ができた。$N$ が目減りしても、$2$ べきから減らせば大丈夫。
本番中はこれでそのまま通したが、本来は逆 (＝ $2^k+1$ が $k$ 色で出来ない) も示すべき。しかしこれも二部グラフなことに注目すれば、半分にするときどうしても真っ新な $K_{2^{k - 1}+1}$ が残ってしまうので、帰納的に $k+1$ 色いるのはすぐわかる。これくらいはすぐ脳内で処理したいなぁ。
今回はさすがに強そうだったので何も考えず実装。僕は DFS をしましたが、どうやら 0-indexed にして「XOR の下から最初の桁の場所」にすればいけるっぽい。なんでそんなん思いつくんや...と思ったが、符号のイメージが付くとまあ確かに感がある。辺をたどれば特定の桁の 01 がひっくり変えるので、確かに二部グラフだなぁ。これも典型なんですかね？
E
解説をちらっと見た。
「行・列を頂点としてマス目はそれを結ぶ辺」という双対変換っぽいやつは、フローとかでよく見るので思いついたけど、そっからは何も進まず。行と列なので二部グラフだが、実際には一般のグラフで辺を選ぶ問題を解くとするといいらしい。条件を捨てて見通しをよくするのもあるんだなぁ (いやまああるけど、遭遇したことがなかった)。
そっからはまだよく分からん。ひとまずマトロイド勉強します...
F
これも解説をちらっと。
結果的にこっちの方が E より解けそうだったけど、カウントの仕方がキモそう (まあ1000だし...) なのでまあしゃーないか。これもまた今後解きます。
【結果】
ABCD + 2WA, 99:01 で 265 位。日本国内だけで 185 位くらいなので、通過が確定しました！やったね！
立ち回りはそこそこ上手くいった。というかたまたま D が楽めで、上手くいくようなセットだった。どうやら ABD 早解きも通るようなので、 読みは結果的に合ってた。
というか普通に E, F が (自分の実力で) 解ける難易度をしていなかった...これは本選にいっても絶望するやつやな？精進精進...
パフォも 2070 で黄、レートもちょいアップ。目標の黄は近いが、もう少しパフォを上げないとダメそう。今回だと純粋にスピードが足りなかった。E が解けるなら別だがそうもならないので、思考スピ―ドを上げたい。
具体的には、問題の設定を「典型問題・典型的思考に帰着させる」のがまだまだ遅い (C とか、D の言いかえとか) ので、ガンガン解いて強くなりたいね。
【おまけ】
この記事から を導入したけどどうですかね。今後も主に数式らしきところは変えますか (問題番号や配点は変えない方が見やすそう)。地味に $t$++ がキモいけど、どーすんのこれ。
【おまけ2】
オンサイトが確定したら、競プロ用で PC 買いたいなぁ。なんかおススメとか注意点とかありますか？(あんまり詳しくないですがたぶん MacBook Air になりそう。でも Mac そない知らんし、もろもろの設定大丈夫かなぁ...)
