ACM-ICPC 2016 Asia Tsukuba Regional, 解法目次 - でも今日はSRMあるから

ACM-ICPC 2016 Asia Tsukuba Regional Informal Solutions

はじめに

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

リンク

オンラインジャッジ: AIZU ONLINE JUDGE
公式: アジアつくば大会 2016 | ACM-ICPC 2016 Asia Tsukuba Regional
順位表: ACM-ICPC 2016 Tsukuba

表

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問題はジャッジか入力データが公開されるかしたら書くかも。ただ、幾何+パズルという苦手分野のコンボなので厳しい。