yukicoder contest 308 あとがき
yukicoder contest 308 にご参加して頂きありがとうございました。解説は各問題の解説ページからご覧ください。
各テーマは以下の通りでした。
| 問題 | テーマ | 想定diff |
|---|---|---|
| A | 簡単枠 | 1 |
| B | DFS | 400 |
| C | ダイクストラ法 | 1000 |
| D | クラスカル法 | 1000 |
| E | Unionfind + DFS | 1200 |
| F | セグメントツリー or BIT | 1400 |
各問題の総評
A 「森」
簡単枠です。後々の問題のために聞いておきました。
想定解答時間:3分
B 「Easy Tree Query」
元ネタ ABC138D Ki
前計算で各頂点を根とした部分木の頂点数を求めておく問題でした。
想定解答時間:5分
C 「Robot Maze」
ダイクストラ法を使う問題でした。制約はひっかけです。
判定問題にしたらダイクストラ法に見えないかなと思って出しました。
想定解答時間:16分
D 「最小通信路」
クラスカル法を知っているかを問う問題でした。
UnionFindを使わずに深さ優先探索で連結判定をしてもACすることができます。
なお、PyPy3などの多倍長整数がある言語で二分探索することも一応できます ( 制約をこれ以上大きくすると入力でTLEする可能性があるためこの制約になりました ) 。
想定解答時間:16分
E 「簡単な色塗り」
構築問題でした。意外と実装が大変です。詳しくは解説を見てください。
実はmax-flow(min-cut)でも解くことが出来ます。
ちなみに、典型90の062 Paint Allを誤読して生えた問題でした。
想定解答時間:30分
F 「Tree Xor Query」
木上のRangeXorです。木を上手く変換すると解くことが出来ます。yが10ビット以下なことに注目するとビットごとに考えると簡単に解けます。また、先行順巡回するとビットごとに考えなくてもACすることができます。
Testerさんに自信満々に出したらTreeライブラリでぶん殴られましたが、Euler TourはABCのレベルを超えていると思ったので制約は変えませんでした。
想定解答時間:30分
全体を通して
Eのevilケースの制約違反はmaxflowを落とそうとした残骸でした。申し訳ありませんでした。
感想
F解くの速すぎませんか？上位陣はライブラリでぶん殴ってくるとは思いましたがここまで通されるとは思ってませんでした。ABCDは大方問題なくそれなりに通して頂いたので良かったです。 Eを出したくてこのコンテストを作ったのですが、それなりに暴れてくれてよかったです。実はDは元々☆1.5想定でCに置いていたんですが、テスターさんの助言によりDになりました。かなり助かりました。
さいごに
最後に、テスターを引き受けてくださった、serpentさん、milkcoffeenさん、sakさん、koboshiさん、platinumさん、Kazunさん、まぐすたさん、ありがとうございました。
また、コンテストを開かせていただいたyukiさんありがとうございました。
