ACM-ICPC 2016 Asia Tsukuba Regional Informal Solutions はじめに 2016/10/16にICPC地区予選つくば大会が開催された。出題された問題に興味がある、と言うより部外者なので問題を解くしかやることがないので問題のことだけ書く。1週間経ってオンサイト参加…

K: Black and White Boxes 問題 アリスとボブがゲームをする。 箱が縦に一列に積み上げられており、各箱の色は白か黒である。この一列を山と呼び、山が複数ある。二人で交互に箱を取り除く。 アリスは黒箱を1つ選んで、その箱とその上に積んであるすべての箱…

J: Cover the Polygon with Your Disk 問題 円と凸多角形が与えられる。凸多角形の頂点は10個以下。それぞれ自由に平行移動・回転移動させて、共通部分の面積の最大値を出力せよ。 入力は整数で座標は0~100、円の半径は1~100。

H: Animal Companion in Maze 問題 グラフが与えられる。辺は有向のものと無向（双方向）のものがある。長さは全て1。 無向辺を通ったときにすぐ同じ辺を引き返してはならないとき、最長歩道の長さを出力せよ。 歩道とは頂点・辺の重複を許したパスのこと。 …

G: Placing Medals on a Binary Tree 問題 深さ10^9の完全二分木がある。根の深さは0、葉の深さは10^9。n個のメダルを順番に頂点に置いていく。このとき、部分木にメダルがある頂点には置くことができない。また頂点の深さはメダルに書かれている数と等しく…

F: Three Kingdoms of Bourdelot 問題 複数のドキュメントがある。各ドキュメントには家系図の情報が複数行書かれている。ドキュメントは正と負の2種類あり、各行はペア(x, y)であり、 ドキュメントが正の場合：xはyの祖先である ドキュメントが負の場合：x…

E: Infallibly Crack Perplexing Cryptarithm 問題 虫食い等式が与えられる。数式は2進数で数を表記し、BNFは次のように与えられる。 Q ::= E'='E E ::= T | E'+'T | E'-'T T ::= F | T'*'F F ::= N | '-'F | '('E')' N ::= '0' | '1'B B ::= empty | '0'B |…

D: Hidden Anagrams 問題 2つの同じ長さの文字列が、各アルファベットの出現数が同じであるとき、互いにアナグラムであると言う（多分同じ文字列もアナグラムという）。 2つの文字列が与えられる。それぞれから部分文字列を取り出して、それらがアナグラムで…

C: Distribution Center 問題 n本のコンベアラインが平行に並んでいる。各ラインiの左から製品iが右に向かって流れる。またm台のロボットが配置されてある。ロボットjは左からxjの位置にあり、ラインyj, yj+1の製品をそれぞれ反対のラインに移す事ができる。…

B: Quality of Check Digits 問題 一桁の数同士のX演算の定義テーブルが与えられる。iXi = 0が保証されている（i = 0 .. 9）。ある4桁の数 abcd (leading zerosを許す) に対して、e = (((0Xa)Xb)Xc)XdをCheckDigitとして5桁のabcdeについて、書き間違えを判…

A: Rearranging a Sequence 問題 始めに数列1 … n がある。「数e_iを先頭に移動させる」と言う操作をm回行う（1