AtCoder Regular Contest 081
Updated:
Source codes
Solutions
C - Make a Rectangle
並べ替えて上から見ていく。
D - Coloring Dominoes
縦に並べるのを a, 横に並べるのを b とし、付け加えると何倍になるかを 4 通り検査する。
ポイント
入力の処理が少し面倒に見えるが難しくはない。
E - Don’t Be a Subsequence
まず後ろから見ていく。 a から z まで全部出てきたら、そこまでを 1 つの word として区切る。 区切れず先頭にきたら、そこまでを $w_0$ とする(空文字でも良い)。 すると以下の通りに分解する。
\[ a = w_0 w_1 \dots w_n, \]
ただし、 $w_1, \dots, w_n$ はそれぞれ a から z まで全部出てくる後ろから見て最小の区切り、$w_0$ はそうではない。
この時、$n+1$ 文字の文字列であって、 $a$ の部分文字列にならないようなものが存在する。 具体的には、 $w_0$ に含まれていない文字のうち最小の文字を $0$ 文字目とし、 $i$ 文字目は $w_i$ の先頭の文字、とすれば良い。これは絶対に作れない。
ところが、一般にはこれは答えではない。条件を充たす $(n+1)$ 文字の文字列のうち、辞書順最小のものを答えなければならない。
まず、「$w_0$ に含まれていない文字のうち最小の文字を $0$ 文字目」というのは改善しようがない。また、文字数を考慮すると、「$i$ 文字目は $w_i$ から取ってくるしかない(だから作れない)」という状況も改善しようがない。だから、先頭から逐次、解答を決定できるのも間違いなさそうである。
以下、記号が煩雑になるのを避け、具体例で述べる。今、解答の $i$ 文字目が a であったと仮定しよう。 $w_{i+1} = \mathrm{zyaabcdefg} \dots \mathrm{uvwx}$ であったとしよう。 ここで $(i+1)$ 文字目を z に指定すると作れないのは先ほど書いた通り。 y にしても同じ理屈で作れない。 では x にするとどうだろうか。これは途端に作れるようになる。 $w_1$ から $0$ 文字目、 $w_2$ から $1$ 文字目、…、 $w_i$ から $(i-1)$ 文字目をとり、 $w_{i+1}$ から ax をとれば、以降どのように指定しても必ず取れてしまう。 だからこれは答えになり得ない。 2 文字の文字列「$i$ 文字目 $(i+1)$ 文字目」を $w_{i+1}$ に部分文字列として発見されないことが、答えの文字列であることの必要十分条件である。
つまり正しいアルゴリズムは、以下の通り。
- $w_0$ に含まれていない文字のうち最小の文字を $0$ 文字目とする。
- $i$ 文字目を確定させた段階で、
- $w_{i+1}$ の先頭から $i$ 文字目と同じ文字を見つける。
- それ以降に登場しなかった文字のうち、最小の文字を $(i+1)$ 文字目と決定する。
実装には特別な手順はいらない。
ポイント
時間制限がなかったからか、いつもと違って、特に詰まることはなかった。自分はコンテストには向いてないんだろうなぁ。