今週も AtCoder のプログラミングコンテストに参加しました。
ABC-only 回ですが、今回からシステムが変わって、レート変動の対象がレート 1999以下 (青コーダー以下) まで拡大しました。私も対象です。 追記: Unrated になりました。
AtCoder Beginner Contest 126
- この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 問題の詳細は問題一覧を参照してください。
A - Changing a Character
問題概要: A, B, C のいずれかの文字からなる長さ N の文字列 S と、1 以上 N 以下の整数 K が与えられる。S の K 番目の文字を小文字に置き換えた文字列を出力せよ。
考察:
Rust では、標準ライブラリに char::make_ascii_lowercase という関数があるので、これを使えばいいです。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5456485
B - YYMM or MMYY
問題概要: 4つの数字が与えられる。これが YYMM 形式の日付としてありうるか、MMYY 形式の日付としてありうるかをそれぞれ判定せよ。
考察:
入力例を見ると、要するに MM の部分が 1 以上 12 以下であるかを判定すればいいようです。
したがって、まず4つの数字を2桁ずつの整数 a, b に分けて、次の2つの判定を行います。
- b が 1 以上 12 以下なら YYMM はありうる
- a が 1 以上 12 以下なら MMYY はありうる
そして、これらの結果の組み合わせ4通り (TT/TF/FT/FF) で場合分けして、適切な単語を出力します。スペルミスに注意しましょう。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5454681
C - Dice and Coin
問題概要: N 面サイコロを1回振って、その出目をスコアとる。表が出続ける限りコインを投げて、表が出るたびにスコアを2倍にする。最終的に、スコアが K 以上になるまで表が出続ければ勝ちである。このゲームの勝率を求めよ。
考察:
入力例を見るとほとんど解法に近い考え方が載っていますね。
- サイコロの出目を全通り試す
- 「スコアが K を超えるまでに何回連続で表を出し続けなければいけないか」の最小値 h を計算する
- このサイコロの出目における勝率は 1/2^h である
サイコロの出目ごとに排反なので、各出目における勝率の和を N で割った確率が答えとなります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5452745
D - Even Relation
問題概要: N 頂点の木が与えられる。i 番目の辺は頂点 u, v の間を距離 w で繋いでいる。以下の条件を満たすように各頂点を白または黒で塗り分ける。塗り分けは必ず存在するので、一例を示せ。
条件: どの同色の2頂点も、その間の距離の総和が偶数である
考察:
すべての辺が w = 1 のケースを考えると、2部グラフの塗り分けをすればいいことが分かります。
他のケースも同様で、根からの距離の偶奇で塗り分ければよさそうです。
試しに2頂点 u, v を考え、それらの最低共通祖先を a とします。「u-v 間の距離が偶数」と「r-a-u の距離と r-a-v の距離の偶奇が等しい」が同値であればよいです。
r (根)
|
a (共通祖先)
/ \
u v
「r-a-u の距離と r-a-v の距離の偶奇が等しい」は「a-u の距離と a-v の距離の偶奇が等しい」と同値で、これは u-v (= u-a + a-v) の距離が偶数になることと同値です。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5460076
E - 1 or 2
問題概要: N 枚のカードが伏せられている。i 番目のカードには整数 A(i) (= 1 または 2) が書かれている。以下の M 個の条件が与えられているとき、すべてのカードに書かれた整数を特定するには、最小で何枚のカードをめくればよいか。
- i 個目の条件: 整数 X(i), Y(i), Z(i) が与えられて、A(X(i)) + A(Y(i)) + Z(i) が偶数であること
考察:
カードの数字は偶奇だけ考えればよいです。条件は、2枚のカード X(i), Y(i) の偶奇が等しいか否かを表していると解釈できます。
例えば2枚のカードがあって、偶奇が等しいと分かっているとします。このとき、1枚のカードをめくれば、他方のカードの数字も分かるので、答えは1になります。
もう少し複雑な状況として、3枚のカード x, y, z の偶奇が x = y, y != z というのを考えます。このときも1枚だけめくればいいです。x → y → z と 連鎖的に偶奇が決まる からです。
結局、カードを点、カードの間の条件を辺としたグラフを考えて、その連結成分の個数が答えとなります。(Z を使わないのが妙ですね。)
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5464673
F - XOR Matching
問題概要: 非負整数 M (≤17) と非負整数 K (≤10^9) が与えられる。以下の条件を満たす長さ 2^(M+1) の数列 A が存在するか判定し、存在するなら一例を示せ。
条件:
- A は 0 以上 2^M 未満の各整数を、ちょうど2つずつ含む
- A(i) = A(j) (i < j) を満たす任意の区間につき、A(i) ^ A(i + 1) ^ .. ^ A(j) = K である
考察
いわゆる構築問題です。
例えば M=2, K=3 なら、数列の長さは 2^3 = 8 で、2^2 = 4 未満の各非負整数を2個ずつ含みます。実験してみると、以下の解が見つかりました。
0 1 2 0 3 2 1 3
^^^^^^^
2つの 0 の間の区間 (ここでは 0-0 区間と呼びます) の xor は確かに K=3 になっています。他の数について確認しても、以下の通り、区間上の xor の値は 3 になっています。
0 1 2 0 3 2 1 3
^^^^^^^^^^^
0 1 2 0 3 2 1 3
^^^^^^^
0 1 2 0 3 2 1 3
^^^^^^^
区間の両端は等しいという条件があるので、区間の内側の xor だけ見ればいいです。このことから、以下のような形の区間は xor の値が中央の値 K に一致することに気づくかもしれません……
3 2 1 K 1 2 3
やや天下り的な考察ですが、このアイディアから一般解が導けます。M > 1 かつ 0 < K < 2^M なら、以下のような数列が解の一例です。
0 K 0 2^M-1 .. 2 1 K 1 2 .. 2^M-1
^^^^^^^^^^^^ ^^^^^^^^^^^^
K以外 K以外
0-0 の区間の xor は明らかに K ですし、それ以外の値の xor は右側にある K 以外がすべてキャンセルされる形で K になります。
問題は K-K の区間です。これは 0 から 2^M - 1 までの整数の xor が 0 になることから、この区間の xor は K だと分かります。(ただし後述の通り、M=1 のときだけ 0 になる。)
エッジケース: K = 0
K = 0 のときは、入力例1にある通り、以下が解です。
0 0 1 1 2 2 .. 2^M-1 2^M-1
すべての区間が長さ 2 で、両端はキャンセルされるので、xor の値が K = 0 になっています。
エッジケース: K が巨大
K > 2^M のケースでは、K には数列上の要素にないビットが立っているので、どのような xor のとり方をしても「区間上の xor の値」が K になることはありません。区間は少なくとも1つ存在するので、解がないといえます。
エッジケース: M が小さいケース
入力例 2 の M=1, K=1 はエッジケースです。上記の方法で構築すると以下の数列になりますが、これは 1-1 区間の xor が 0 になってしまうのでダメです。
0 1 0 1
M=0 のときは K=0 か K ≥ 2^M のパターンが当てはまります。
筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5479285