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

ACM-ICPC 2016 Asia Tsukuba Regional Informal Solutions

はじめに

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

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, K 解法

K: Black and White Boxes

問題

アリスとボブがゲームをする。
箱が縦に一列に積み上げられており、各箱の色は白か黒である。この一列を山と呼び、山が複数ある。二人で交互に箱を取り除く。

  • アリスは黒箱を1つ選んで、その箱とその上に積んであるすべての箱を取り除く。
  • ボブは白箱を1つ選んで、その箱とその上に積んであるすべての箱を取り除く。
  • 自分の手番で取り除くことができなくなったら負け。
  • 二人は勝つために最適な行動をする。

先手のプレイヤーを任意にした場合、アリスにもボブにも勝つ可能性があるようなゲームはfairであるという。

n個の山が与えられるのでその中から0個以上選択してfairなゲームを見つけ、fairなゲームの初期状態の箱の数の最大値を求めよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, J 解法

J: Cover the Polygon with Your Disk

問題

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

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, H 解法

H: Animal Companion in Maze

問題

グラフが与えられる。辺は有向のものと無向(双方向)のものがある。長さは全て1。
無向辺を通ったときにすぐ同じ辺を引き返してはならないとき、最長歩道の長さを出力せよ。
歩道とは頂点・辺の重複を許したパスのこと。
答えを無限に大きくできる場合はInfiniteと出力せよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, G 解法

G: Placing Medals on a Binary Tree

問題

深さ10^9の完全二分木がある。根の深さは0、葉の深さは10^9。n個のメダルを順番に頂点に置いていく。このとき、部分木にメダルがある頂点には置くことができない。また頂点の深さはメダルに書かれている数と等しくなければならない。すでに置いてあるメダルを深さを変えずに他の頂点に移してもよい。
メダルを順番に置けるなら置いていく。それぞれ、置いたらYes。そうでないならNoを出力せよ。
n <= 5 * 10^5

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, F 解法

F: Three Kingdoms of Bourdelot

問題

複数のドキュメントがある。各ドキュメントには家系図の情報が複数行書かれている。ドキュメントは正と負の2種類あり、各行はペア(x, y)であり、

  • ドキュメントが正の場合:xはyの祖先である
  • ドキュメントが負の場合:xはyの祖先ではない

を意味する。
各ドキュメントはそれぞれについて、正か負わからない。n個のドキュメントと二人の人p, qが与えられたとき、pがqの祖先であるような無矛盾なドキュメントの正負の割当があるかどうか判定せよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional, E 解法

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 | '1'B

演算子の優先順位はBNFと同じ。
虫食いは大文字小文字を区別するアルファベット全て。同じアルファベットは同じ記号に、異なるアルファベットは異なる記号に割り当てなければならない。ただし、虫喰いされていない記号をアルファベットに割り当ててもよい。
正しい等式は何通りあるか答えよ。
長さは31以下。

続きを読む