目次
AtCoder Beginner Contest 126 A～F問題メモ
今回のABCから全6問になりましたが、難しいのが追加されるというより、従来のBとC、CとDの間が補完されたと感じましたね。
A - Changing a Character
問題
- 長さ $N$ の文字列 $S$ は、'A','B','C' で構成される
- $K$ 番目の文字を小文字にして出力せよ
解法
Pythonなら大文字と小文字の変換は 文字列.upper(), 文字列.lower() で可能。
でも、実務では意外と大小変換ってすることない気がする。入力が半角英字限定の保証とかないし。自然言語処理分野とかなら入力を揃えるために使うんだろうか。
n, k = map(int, input().split()) s = input() print(s[:k - 1] + s[k - 1].lower() + s[k:])
B - YYMM or MMYY
問題
- 4つの数字からなる文字列 $ABCD$ が与えられる
- 年は西暦の下2桁で表すとして、以下の1つを出力せよ
- $AB$ 年 $CD$ 月として解釈できるなら
'YYMM' - $CD$ 年 $AB$ 月として解釈できるなら
'MMYY' - どちらとも取れるなら
'AMBIGUOUS' - どちらでも取れないなら
'NA'
解法
（'50' 年とかって、1950年か2050年かという意味でAMBIGUOUSな気がする）
年は00～99のどの値でも良くて、月は01～12に限られるので、それで条件分岐する。
def solve(yy, mm):
if 1 <= yy <= 12:
if 1 <= mm <= 12:
return 'AMBIGUOUS'
else:
return 'MMYY'
else:
if 1 <= mm <= 12:
return 'YYMM'
else:
return 'NA'
s = input()
yy = int(s[:2])
mm = int(s[2:])
print(solve(yy, mm))
C - Dice and Coin
問題
- $1～N$ の目が等確率で出るサイコロと、裏表が等確率で出るコインがある
- 以下のルールでゲームをする
- まずサイコロを1回ふり、出た目の得点を得る
- 得点が $K$ 以上になるまでコインを繰り返し振る。表なら得点が2倍、裏なら0点になる
- 得点が $K$ 以上か、0になったらゲームを終了する
- 終了時点で得点が $K$ 以上である確率を求めよ
- $1 \le N \le 10^5$
- $1 \le K \le 10^5$
解法
サイコロで得た得点から $K$ 以上になるまでコインで表を出し続けなければ、$K$ 以上にはなれない。途中で1回でも裏を出すとアウト。
$N$ 通りのそれぞれの目が出たときについて、コインを何回振れば勝てるかシミュレーションする。
余談だが、こういう倍々ゲームは（終了が無く、いつでもドロップアウトできるとすると）サンクトペテルブルクのパラドックス といって、直感に反して期待値が発散する問題として知られる。
n, k = list(map(int, input().split()))
ans = 0
for i in range(1, n + 1):
tmp = 1
while i * tmp < k:
tmp *= 2
ans += 1 / tmp
print(ans / n)
D - Even Relation
問題
- $N$ 頂点の木の各頂点を白または黒で塗る
- $i$ 番目の辺は、頂点 $u_i$ と頂点 $v_i$ を距離 $w_i$ で結ぶ
- 同じ色で塗った頂点は、距離が偶数となるように塗り分けたい
- 各頂点の塗り方の一例を示せ
解法
適当な頂点 $v_0$ を白で塗ると固定すると、その頂点から距離が奇数の頂点は、黒で塗るしかない。
距離が偶数の点は、とりあえず $v_0$ だけとの関係を考えた場合はどちらに塗ってもいい。
ここで、木は2頂点間の経路が1通りしかないので、頂点同士の距離は足し算で考えられる。
つまり、3頂点 $u,v,w$ があって、$u,w$ の経路上に $v$ があるとすると $d(u,w)=d(u,v)+d(v,w)$ である。（$d$ は頂点間の距離）
$v_0$ からの距離が偶数の点 $v_1$ を黒で塗ってしまうと、距離が奇数のため黒で塗った点 $v_2$ との距離が、奇数になってしまう。
v0 偶数 v1 奇数 v2 白--------？--------黒 |<-------奇数----->|
なので、距離が偶数の点は白に塗らないといけない。
結局、適当な頂点から探索して、距離が偶数なら白、奇数なら黒で塗るという方針でよい。
唯一、全ての頂点間が偶数の場合は好きに塗っていいが、一例を示せばいいので、上記の方針通り全て白で塗っていい。サンプルケース2はいじわる。
import sys
n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
u, v, w = map(int, line.split())
u -= 1
v -= 1
links[u].add((v, w))
links[v].add((u, w))
ans = [-1] * n
q = [(0, 0, -1)]
while q:
v, d, p = q.pop()
if d % 2 == 0:
ans[v] = 0
else:
ans[v] = 1
for u, w in links[v]:
if u == p:
continue
q.append((u, d + w, v))
print('\n'.join(map(str, ans)))
E - 1 or 2
問題
- $N$ 枚のカードには、数字1か2が書かれている（どちらが書かれているかは分からない）
- ヒントが $M$ 個ある
- $i$ 番目のヒントでは $X_i,Y_i,Z_i$ が与えられる
- $(X_i枚目のカード)+(Y_i枚目のカード)+Z_i=$ 偶数である
- ここで、何枚かのカードを指定して、そのカードの数字を知ることができる
- 全てのカードの数字を特定するには、最低何枚のカードを指定すればよいか
- $1 \le N,M \le 10^5$
解法
ヒントで繋がったカード同士は、その中の1枚の偶奇がわかれば、残りの全てのカードもわかる。
1枚目+2枚目=奇数 2枚目+3枚目=偶数 4枚目+5枚目=偶数 ○--○--○ ○--○ ↓ １--？--？ ？--？ 1枚目を指定して直接知る ↓ １--２--２ ？--？ 2枚目、3枚目が連鎖的にわかる
ヒントで繋がっていないカードは、分かりようがないので、新しく指定する必要がある。
よって、Union-Find木などで繋がったカード同士を管理し、最終的に繋がっていない木がいくつあるかを数えればよい。
import sys
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
def _root(self, x):
if self.table[x] < 0:
return x
else:
self.table[x] = self._root(self.table[x])
return self.table[x]
def find(self, x, y):
return self._root(x) == self._root(y)
def union(self, x, y):
r1 = self._root(x)
r2 = self._root(y)
if r1 == r2:
return
d1 = self.table[r1]
d2 = self.table[r2]
if d1 <= d2:
self.table[r2] = r1
if d1 == d2:
self.table[r1] -= 1
else:
self.table[r1] = r2
n, m = map(int, input().split())
uft = UnionFind(n)
for line in sys.stdin:
x, y, z = map(int, line.split())
x -= 1
y -= 1
uft.union(x, y)
ans = 0
for v in uft.table:
if v < 0:
ans += 1
print(ans)
F - XOR Matching
問題
- 以下の条件を満たす、長さ $2^{M+1}$ の数列 $a = \{a_1, a_2, ..., a^{2^{M+1}}\}$ を、存在するならば1つ構築せよ
- 0 以上 $2^M$ 未満の整数を、それぞれちょうど2つずつ含む
- 同じ数字同士を $a_i, a_j$ とすると、その間（両端含む）の全ての排他的論理和 $a_i \oplus a_{i+1} \oplus ... \oplus a_j = K$ である
- 全ての同じ数字同士の組に、上記が成り立つ
- 存在しなければ-1を出力せよ
- $0 \le M \le 17$
解法
こういう構築問題で、サンプルケースにまともな成功例が載せられていない場合、見たらすぐにわかるような単純な法則で構築できる「かも」と頭の片隅にとどめる。
まず、$K \ge 2^M$ の場合は、$K$ の最上位ビットを立てるための整数が $a$ に無いので、構築不可能。
M=3 K=9
aの構成要素 000 ～ 111
K 1001
^ 4ビット目を1にするには、aに少なくとも1つは
4ビット目が1の要素がないといけないが、存在しない
以下、$K \lt 2^M$ とする。すると、$a$ には必ず $K$ と等しい要素が存在する。
ここで、xorなので同じ要素2つで打ち消し合えることを活かすと、以下のような方針が思いつく（要出典）。
- $K$ に等しい要素 $a_k$ を1つ、中央に置く
- それ以外の要素を、外側に2個ずつくっつけて、入れ子状に覆っていく
M=3 K=5 ↓ 0 1 2 3 4 6 7 5 7 6 4 3 2 1 0 (残り "5" 1個)
$a_k$ 以外のペアについては、同じ要素同士が2個ずつ打ち消し合うので中央の$a_k$のみが残り、xorの結果は $a_k = K$ となる。
問題は $a_k$ のペアについてもちゃんと $K$ になるかと言うことである。 残っている片割れの $a_k$ は既存の数字の間に入れると成立が崩れてしまうので、末尾か先頭（どっちでも同じ）にくっつけてみると、 ペアの間にあるのは $a$ の構成要素が1個ずつと、$a_k$ だけもう1個となる。
0 1 2 3 4 6 7 5 7 6 4 3 2 1 0 5
~~~~~~~~~~~~~~~~~~~~~~~~~
ここで、0以上 $2^{M}$ 未満の全ての整数のxorを考えると、$M \ge 2$ の場合は全て0になる。（$4n～4n+3$ のxorは0になるので）
この性質を使えば、$M \ge 2$ については以下が言える。
$a_k$ 同士の間にある数のxor $=$「0以上 $2^{M}$ 未満のxor」$xor \ a_k=0 \ xor \ a_k=a_k=K$
よって、$a_k$ のペアもちゃんと $K$ にできることが言えた。
$M=1$ の場合のみ個別に対処する必要があるが、$K=0$ なら 0 0 1 1、それ以上なら不可能と、簡単な場合分けで記述できる。
この例外をきちんとサンプルケースに入れてくれているあたり、優しさを感じる。
m, k = map(int, input().split())
if m == 1:
if k == 0:
print(*[0, 0, 1, 1])
else:
print(-1)
exit()
n = 2 ** m
if k >= n:
print(-1)
exit()
ans = [0] * (n * 2)
i = 1
for v in range(n):
if v == k:
ans[0] = ans[n] = v
continue
ans[i] = ans[2 * n - i] = v
i += 1
print(*ans)
今回、ジャッジが特定の時刻から詰まってしまったようですが、F問題は見落としがちな例外処理がいくつかあるので、 ジャッジでWAとすぐに判定されて見直したか、終了までわからなかったかでAC率に結構な差が生じたっぽいですね。
別解法
条件を満たす小さなブロックを作って並べる解法。
$K \lt 2^M$ かつ $M \ge 2$ の時、0以上 $2^M$ 未満の数字から、重複無く以下のようなペアが $2^M/2$ 個取れる。
- $(a,b): a \ xor \ b = K$
このペアを2つ使って以下のように組み合わせると、それぞれの間のxorが $K$ になっている。
a xor b = c xor d = K a b c d b a d c
これを並べれば、答えとなる。
