A | B | C | D | E | F | |
問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
自分の提出 | ■ | ■ | ■ | ■ | ■ | |
結果 | AC | AC | AC | AC | AC |
問題 F:コンテスト後 AC → https://atcoder.jp/contests/arc105/submissions/17355625
全体感想
90分、ABCED の 5 完で、44位でした。
問題 F がそこそこ速く解ける回だったのに、時間を残せなかった・F を先に考える判断ができなかったため解ききれず、悔しいところです(Problems では銅 diff 評価ですが、100 分 6 問という要求速度の速さをかなり受けていると思います)。
問題 F は、好きそうな分野だったり AC が早めに出ていたら丁寧に読むつもりでしたが、グラフだったのであまりしっかり読まず。実際には線形代数や集合包除に近く、私の苦手なグラフ要素は少なめだったので、もっとしっかり読むべきでした。
結局、あと 30 分あれば解けたかどうか。くらいっぽいです。
ABCE のあと F に着手していた場合、ちょうど境界線上。これはこれで上手くいっていた保証はないですし、まぁ結果的にレーティング期待値は近かったかもしれません。仕方ないですね。
5 完 90 分は失敗寄りだとは感じなかったんですけど、やっぱり強い人は安定して高速で、まだまだ及んでいないと思わされます。
問題B – MAX-=min
テストケースが弱くて、シミュレーションで通るという解法も通るようです。
(
同じところからの減算をまとめても、
自明に見えましたが、一応脳内で数回証明を考えてから提出しました。まぁいいでしょう。
(ABC 以外では、序盤の問題を自明と思い過ぎて、誤読して間違えるパターンが複数回あったので、反省リストに入れています)
- 操作の最後に残る数を
とします。まず、操作の過程で現れる数は、常にすべて
また、操作を逆に遡ることで、操作の過程で現れる数は、常にすべて
Euclid の互除法で最大公約数が求まる理由を理解していれば、同様に証明できると思います。
問題D – Let’s Play Nim
苦戦、勝利条件を逆にして考察してしまってタイムロスしたのも大きかったです。
結構難しかったのに、AC 人数が多かったように感じてびっくりしていました。(すべては証明していないという提出も、一定数あるかもしれません)
Nim パートは有名問題です。それを除くと、
が偶数のとき:先手から始めて偶数回、山に石を置く。全体の が になったら先手の負け。 が奇数のとき:先手から始めて奇数回、山に石を置く。全体の が になったら先手の勝ち。
さまざまな
勝てるときあるのかなあ?と考えていきます。
を考えると、 数が等しいときに後手が勝てると分かります。 のときに先手が勝てる気がしません。試しに、 つの数が 以下のときに全探索解法を実装した結果、先手は全く勝てないという予想に至りました。 のときの証明を考えます。後手は、 つの山を巨大にすることで、先手負けが確定します。
ここまでかなり発想の少ない考察だと思いますが、これで解答に必要な考察の種はすべてそろっていました。
あとは、それ以外の場合ですが、これは
問題E – Keep Graph Disconnected
「連結成分のマージで、奇成分の個数は、
完全に公式解説通りです。とりあえず、ゲームの終了状態について考えると、
あとは、常に奇成分が偶数個であることを念頭に置いて考察しました。成分が
問題F – Lights Out on Connected Graph
本番中にで解ききりたかったなー。完全にグラフ理論勉強会のおかげで思考がショートカットできたというやつ。まぁ終了後すぐに AC できて、取り組んできたことが(レートには結びついていないとはいえ)成果に現れているので、嬉しいです。今後とも、自分で考えた勉強法や練習法に自信を持っていきたい。
グラフ
と書ける辺集合です。カット全体はそれっぽい加法により
カット空間にはいくつかの記述があります(次元が簡単に記述できたり、基底が簡単に作れたりする)が、辺の生成する
今回の問題ではいかにも、
そこから答を求めるところがまた、おおよその筋道は見えても思考の整理に時間がかかるやつです。「二部グラフ」のままだと、非連結なものを考えるときに、部集合への分割が
この手の数え上げでは、「簡単に計算できるものは何かを考える」こととか、「数え上げ対象の定義を明確に記述する」を意識しています。
- グラフ
と分割 の組 であって、 辺、 辺のないものを、ラベル付き二部グラフと呼ぶことにする。(ひとつのグラフが複数の方法でラベル付き二部グラフになりうる) - 求めたいのは、頂点集合を
とする の部分ラベル付き連結二部グラフの個数の、半分である。 を、 を頂点集合する の部分ラベル付き二部グラフの個数 を、 を頂点集合する の部分ラベル付き連結二部グラフの個数
以下、計算手順です。
を数え上げるには、全ての分割 に対する和をとればよい。 の個数は全体で 通り。- 固定した
の寄与は、 辺の個数を とすると、 通りである。よって が計算できればよい。 - 両端点が集合
に属している辺の個数を とすると、 である。したがって、すべての を前計算しておくと、 の計算は 時間で行える。 の前計算は、愚直にやれば 時間で行える( にもできる)
を数えたい。 を場合分けする。 をひとつとる。 の連結成分で場合分けをする。 という式が得られる。- 特に、
と計算できる。 は 通りなので、ここも計算量 。