2019年5月19日に行われたAtCoder Beginner Contest 126 のPython3での実装例です。
A - Changing a Character
使用テクニック: str.lower()
str.lower()
で指定された大文字を小文字に変換。Pythonは0-indexであることに注意。
B - YYMM or MMYY
使用テクニック: if-elif-else
与えられた文字列を前半2文字と後半2文字に分け、int
型として変数 a, b
に取得。 a, b
に収納された数字が0または12より大きい場合は年 (YY)、1以上12以下の場合は年 (YY) と月 (MM)のどちらもあり得ます。
C - Dice and Coin
使用テクニック: 確率計算
ダイスの値ごとに条件を満たす確率を求めて積算。
while
文で各ダイスの値が K
を超えるまで倍にする回数を求め、ダイスが特定の数字を出す確率 にかけて積算します。
D - Even Relation
使用テクニック: 木構造、幅優先探索 (BFS, Breadth First Search)
任意のノードから各ノードへの距離の偶奇が分かれば、その関係は他のどのノードを起点にしても変わりません。
そのため、ノード 1
を起点とした各ノードの距離を幅優先探索 (BFS) でリスト(dist
) にメモしておき、最後に各ノードに対して偶奇判定を行います。
E - 1 or 2
使用テクニック: Union-Find
入力として与えられる は、
の値に関わらず、
のどちらかの数字が分かればもう一方の数字も導けます。
が偶数なら、
が奇数なら、
ここで、入力で与えられた の間にエッジを持つ
頂点のグラフを考えます。エッジで結ばれた頂点は、そのうちの1つの数字が分かれば他の頂点の数字も導くことが出来ます。よって、このグラフの連結成分の数が求める答えとなります。
F - XOR Matching
使用テクニック: (排他的論理和)
(排他的論理和)には以下の特徴があります。
- 同じ整数同士の
は
になる:
- 任意の整数
と
の
は
になる:
が2以上のとき、
から
までの累積
は
になる:
よって、整数 を除いた
から
までを昇順に並べた数列
と降順に並べた数列
で整数
を挟んだ数列では、
以外の整数を選んだ際には
以外の数字が打ち消しあい、
かつ
を満たす任意の
について、
から
までの累積
は
となります。
この時、
また、上記の数列の最後にも を追加することで、
の場合でも、
から
までの累積
は
となります。
この時、はじめの から 最後の
までの累積
は、
となり、 の場合
の特徴3からこれは
となります。
以上より、数列 は、
を満たす任意の
について、
から
までの累積
は
となる。ただし、以下のコーナーケースが存在します。
コーナーケース
のとき、
以下の整数をどのようにしても
を作れないためは条件を満たす数列は存在しません。
の場合、
の特徴3が成立しないため、上記の数列では条件を満たさない。そのため、個別に処理する必要があります。
の場合、
のみが許容され数列
が答えとなります。
の場合、入力例 1 が答えとなります。
の場合、入力例 2 の通り条件を満たす数列は存在しません。