ACM-ICPC World FInals 2016 in Phuket, 解答案

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チーム中)とジャッジ解のコード長(縦軸)。
f:id:natsugiri:20160625152549p:plain

取るに足りない日記

以前のWFに比べると解法を思いつくのは易しく実装が厳しい印象を受ける。2015で全完決めた反動なのか。
解法のアイディアが比較的難しいのはBとF。
復習すべきおすすめの問題を上げると

  • G: 簡単だが教育的な問題、国内予選突破を目指すレベルのチームは是非解きたい
  • B: DPがやや難しいが、地区予選では多くのチームが解くことができそう
  • F: 本問題セットで唯一、アルゴリズムを生み出すタイプの問題

地区予選進出レベルのチームでアルゴリズムを練習したいならこの3問だけやればよい。
ただし、ICPCはオンラインのプログラミングコンテストに比べ、実装重め・セグメントツリー少なめ・幾何多め・フレーバーテキスト多め、などの特徴があるのでこれらを練習したいなら(できればチームで時間を計って)多くの問題に挑戦するのも良い。

唯一解けていないH問題はICPCによくある最終防衛幾何である。私は幾何が得意ではないので挑戦したくないが、JAGの問題に比べれば解法も思いつきやすく実装も(比較的)軽いのでは無いかと踏んでいる。しかし高難度であり、どうせ本番で誰も解かない問題なので、これを解く時間で他の問題を解いたほうが有意義なのでは?