読者です 読者をやめる 読者になる 読者になる

ACM-ICPC 2016 Asia Tsukuba Regional, 解法目次

ACM-ICPC 2016 Asia Tsukuba Regional Informal Solutions

はじめに

2016/10/16にICPC地区予選つくば大会が開催された。出題された問題に興味がある、と言うより部外者なので問題を解くしかやることがないので問題のことだけ書く。1週間経ってオンサイト参加者はすでに復習を終わらせているだろうが、来年以降の地区予選を目指すチームの手助けになれば幸いだし、ならなくても幸い。
オンサイトでは解説があったはずだが見ることができなかったので非公式解法ということで。

ID 問題 ジャンル 略解 ACチーム数 コード長 難易度
A Rearranging a Sequence ad-hoc 実装 45 391 200
B Quality of Check Digits ad-hoc 全探索 45 923 250
C Distribution Center ad-hoc 実装 45 584 200
D Hidden Anagrams 文字列 二分探索 35 1047 300
E Infallibly Crack Perplexing Cryptarithm 文字列 パーサ 24 2185 400
F Three Kingdoms of Bourdelot グラフ・データ構造 データ構造 8 2989 550
G Placing Medals on a Binary Tree 木・データ構造 FenwickTree 26 1313 550
H Animal Companion in Maze グラフ DFS 3 3287 700
I Skinny Polygon 整数幾何 不明 6 無限 無限
J Cover the Polygon with Your Disk 幾何 解ける幾何 4 5387 600~700
K Black and White Boxes 組合せゲーム 実装 1 1350 300~600

ACチーム数はオンサイト参加の45チーム中のAC数。コード長は私の実装量。難易度はAOJ-ICPC を参考に独自で付けたもの。ただAOJあんまりやってないのと他人の評価基準を聞いてないので微妙かも。
f:id:natsugiri:20161023164917p:plain
※ I問題をプロットしていない。

感想

中難度の問題が多く、とても爽快感があるセットである。全体的に昨年より易しい傾向にあり、特に幾何は国内予選のほうがよっぽど難しかった。
実装は軽いものが多いが考察は重め。オンラインジャッジで解くのには楽しいが、本番中だと緊張感ありそう。
ICPCの練習としてこのセットやるなら当然全て目を通すべきだが、オンラインのショートコンテストの練習のためならC, F, G, Hがそれっぽい内容である。
I問題はジャッジか入力データが公開されるかしたら書くかも。ただ、幾何+パズルという苦手分野のコンボなので厳しい。