AtCoder Beginner Contest 126 A~F問題メモ

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--?--?  ?--?  1枚目を指定して直接知る
↓
1--2--2  ?--?  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, \ldots, a^{2^{M+1}}\}$ を、存在するならば1つ構築せよ
    • 0 以上 $2^M$ 未満の整数を、それぞれちょうど2つずつ含む
    • 同じ数字同士を $a_i, a_j$ とすると、その間(両端含む)の全ての排他的論理和 $a_i \oplus a_{i+1} \oplus \ldots \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

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

programming_algorithm/contest_history/atcoder/2019/0519_abc126.txt · 最終更新: 2019/05/22 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0