2016-10-23

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

2016-10-23

ACM-ICPC 2016 Asia Tsukuba Regional, F 解法

F: Three Kingdoms of Bourdelot

問題

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

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

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

2016-10-23

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以下。

2016-10-23

ACM-ICPC 2016 Asia Tsukuba Regional, D 解法

D: Hidden Anagrams

問題

2つの同じ長さの文字列が、各アルファベットの出現数が同じであるとき、互いにアナグラムであると言う（多分同じ文字列もアナグラムという）。
2つの文字列が与えられる。それぞれから部分文字列を取り出して、それらがアナグラムであるようなとき、その部分文字列の長さの最大値を求めよ。
アルファベットはa~z、文字列の長さはそれぞれ4000以下。10sec。

2016-10-23

ACM-ICPC 2016 Asia Tsukuba Regional, C 解法

C: Distribution Center

問題

n本のコンベアラインが平行に並んでいる。各ラインiの左から製品iが右に向かって流れる。またm台のロボットが配置されてある。ロボットjは左からxjの位置にあり、ラインyj, yj+1の製品をそれぞれ反対のラインに移す事ができる。xjは互いに異なる。
ロボットを好きなタイミングで動かしたり止めたりして良いとき、各ラインには何種類の製品を流すことができるか。