この記事は立命合宿の 3 日目に行われた北大セットのまとめ的記事です。勝手にまとめてしまいました。
※ 随時更新します
問題
実際にコンテストで使われたバージョン
A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題
正式掲載
A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題
解説
A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題
テスターやった人並みの一言
解法詳細はスライドを見てください。
- A は (奇数個ある種類数) / 2。誤読しやすいのは正直申し訳ないし誤読する人が出るだろうなあという予想はしていたけど、問題をちゃんと読むという注意力を問うた部分もある (たとえ誤読していてもサンプル 3 で気づくと思ったんですけどね・・・)
- B は 「x 点上げるときに 8 位以上になれるか？」で二分探索できる (全探索でも可)。同率の扱いや、得点を上げた時の順位変動に注意。
- C はパスグラフとしてみるとよくて、端を特定したあとは端と任意の頂点について質問攻め。順列のサイズが 1 のときに注意。
- D はパラメータが増えたダイクストラで、距離をキーにして
priority_queueを使えばよい。N を通過したか否かのフラグを持つと楽に書ける。速度をキーにしてもそこそこうまくいくけど 1 ケースだけ落ちます (後述) - E は区間を set に突っ込むときの set のサイズがそのまま答えになる (更新は頑張らなければいけない)
- F は根つき木の同型性判定を応用して、木の中心を根として同型性判定を行う
- G は パターン順列の run の数に応じて解法を変えていく。run の数 が 4 以上なら確実に No
- run の数 = 1 なら LIS
- run の数 = 2 なら 山 → 谷 のパターンに合うように点を貪欲にとる
- run の数 = 3 なら 山 → 谷 → 山 のパターンに合うように貪欲に
コード例 (tsutajiro 解)
A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題
ちょっとした裏話
- 作問班唯一の学部生・・・ (若人がいない)
- 情報系学生の底辺なので作問するまで Git の使い方が分からなかった (爆笑)
- B は最初二分探索が想定解であったため、チーム数が
まで、得点上限が
まで、といった感じだったが、 B にしては難しすぎるため全探索可能な範囲に落ちた
- D で始めの自分の解では距離比較でなく速度比較でダイクストラをやっていて、それで一旦全ケース通ってた
- → のちに Darsein さんがチャレンジケースを生成して見事に落とされる
- → 理由は最悪計算量がベルマンフォードと同じになり間に合わないため (しかし通常のベルマンフォードよりは速い模様)
- → tsukasa_diary さんが SPFA を実装したところ爆速で通る (が、最悪ケースを作るのが難しいためこれは許容する流れに)
- 先輩方はみんなプロ (それはそう) (精進します)
以上です。
