−目次

AtCoder Beginner Contest 126 A～F問題メモ
- A - Changing a Character
  - 問題
  - 解法
- B - YYMM or MMYY
  - 問題
  - 解法
- C - Dice and Coin
  - 問題
  - 解法
- D - Even Relation
  - 問題
  - 解法
- E - 1 or 2
  - 問題
  - 解法
- F - XOR Matching
  - 問題
  - 解法

AtCoder Beginner Contest 126 A～F問題メモ

AtCoder Beginner Contest 126

AtCoder Beginner Contest 126 解説放送

今回の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

これを並べれば、答えとなる。