ACM-ICPC World FInals 2016 in Phuket, solutions
1年前のWFを期にプログラミングコンテストの参加が激減した私。本戦参加はしていないが問題だけは確認しておく。
便利リンク
Online Judge:Problems – Kattis, ICPC World Finals
または Problems – Kattis, ICPC
(pending? ACM-ICPC Live Archive)
Scorebord: ACM-ICPC World Finals
Input/Output: Past Problems
Solutions: http://www.csc.kth.se/~austrin/icpc/finals2016solutions.pdf
偉そうに解答解説書いていくが全てAustrin先生とWojtaszczyk先生の(非公式?)解法を読んだだけ。
統計
ID | 問題 | ジャンル | 略解 | Solved | コード長 | 難易度 |
---|---|---|---|---|---|---|
A | Balanced Diet | 数論 | 貪欲 | 36 | 643 | 400 |
B | Branch Assignment | グラフ DP | 最短経路 DP | 50 | 1310 | 600 |
C | Ceiling Function | 木 データ構造 | 木の同型性判定 | 128 | 829 | 250 |
D | Clock Breaking | 実装 | 実装 | 51 | 2027 | 700 |
E | Forever Young | 数論 | 平方分割 | 92 | 826 | 400 |
F | Longest Rivers | 木 DP | クエリソート | 12 | 1220 | 900 |
G | Oil | 幾何 | 平面走査 | 96 | 1153 | 400 |
H | Polygonal Puzzle | 幾何 | 平面走査 | 0 | 5282 | 800~1000 |
I | Road Times | 数論 最適化 | 単体法 | 1 | 3775 | 800 |
J | Spin Doctor | 幾何 最適化 | 凸包 平面走査 | 2 | 3195 | 900 |
K | String Theory | 数列 | 貪欲 | 66 | 798 | 250 |
L | Swap Space | 最適化 パズル | ソート 貪欲 | 108 | 561 | 250 |
M | What Really Happened on Mars? | 実装 英語 | ReadForces | 8 | 1814 | 600~800 |
Solvedは本番128チーム中の解いたチーム数。コード長はジャッジのコードの長さ[bytes]。難易度はICPC・JAG非公式難易度表/AOJ-ICPCを参考にしたつもりだが私はあまり多くを解いていないので参考難易度程度に考えて欲しい。特にHはACを取っていない。
グラフは、本番で解いたチーム数(横軸、128チーム中)とジャッジ解のコード長(縦軸)。
各問記事
- ACM-ICPC World Finals 2016 A解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 B解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 C解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 D解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 E解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 F解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 G解法 - でも今日はSRMあるから
- Hは解かない
- ACM-ICPC World Finals 2016 I解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 J解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 K解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 L解法 - でも今日はSRMあるから
- ACM-ICPC World Finals 2016 M解法 - でも今日はSRMあるから
取るに足りない日記
以前のWFに比べると解法を思いつくのは易しく実装が厳しい印象を受ける。2015で全完決めた反動なのか。
解法のアイディアが比較的難しいのはBとF。
復習すべきおすすめの問題を上げると
- G: 簡単だが教育的な問題、国内予選突破を目指すレベルのチームは是非解きたい
- B: DPがやや難しいが、地区予選では多くのチームが解くことができそう
- F: 本問題セットで唯一、アルゴリズムを生み出すタイプの問題
地区予選進出レベルのチームでアルゴリズムを練習したいならこの3問だけやればよい。
ただし、ICPCはオンラインのプログラミングコンテストに比べ、実装重め・セグメントツリー少なめ・幾何多め・フレーバーテキスト多め、などの特徴があるのでこれらを練習したいなら(できればチームで時間を計って)多くの問題に挑戦するのも良い。
唯一解けていないH問題はICPCによくある最終防衛幾何である。私は幾何が得意ではないので挑戦したくないが、JAGの問題に比べれば解法も思いつきやすく実装も(比較的)軽いのでは無いかと踏んでいる。しかし高難度であり、どうせ本番で誰も解かない問題なので、これを解く時間で他の問題を解いたほうが有意義なのでは?