問題リンク
Tasks - AtCoder Beginner Contest 109
はじめに
この記事では、今回の参加記録およびABC109の問題・解説が書かれています。
上にもくじがあるので、ご活用ください。
結果
全完で57位でした。
なぜかエスパーで解法が降ってきたので速く解けたのだと思います。
以下、各問題と解説です。
A - ABC333
問題
1以上3以下の整数, について、が奇数となるような1以上3以下の整数Cが存在するか判定せよ。
制約
入力は全て整数
1 ≦ , ≦ 3
解説
以前のABCでも似たような問題が出ていました。
(問題名を忘れました。申し訳ないです。)
積が奇数となるのはかけられる数が全て奇数の時なので、
A, Bが共に奇数の時に「Yes」それ以外の時に「No」を出力すれば良いですね。
提出コード
Submission #3151300 - AtCoder Beginner Contest 109
B - Shiritori
問題
N個の単語について、以下のルールを満たしている時に「Yes」を、そうでない時に「No」を出力せよ。
ルール
同じ言葉を2回以上使っていないこと。
1つ前の最後の文字と今発言する最初の文字が同じであること。
制約
2 ≦ ≦ 100
は英小文字からなる1以上10以下の長さの文字列である。
解説
制約からN2でも問題なさそうなので、ルールを守っているかを愚直に確認すれば良いですね。
提出コード
Submission #3152586 - AtCoder Beginner Contest 109
C - Skip
問題
数直線上にある個の都市があり、 番目の都市は座標にある。
あなたはある整数を設定すると以下の移動が行える。
1: 座標から座標に移動する
2: 座標から座標に移動する
ここで、あなたが座標から出発した時の全ての都市を回れるDの最大値を求めよ。
解説
この問題はごちゃごちゃしていますが、
重要なのは「座標から座標にのみ移動出来る」ということですね。
例えば、1と5という座標があったとき、
この時のの最大値は4ですね。
この例を観察すると「4」という数字について、
「5 ≡ 1 (mod 4)」すなわち「5 % 4 == 1 % 4」という性質があり、
「座標間の距離についてを法として合同(mod D)」であることが分かります。
この問題ではの最大値を求めるため、
各点との距離の最大公約数を求めれば「座標間の距離についてを法として合同(mod D)」を満たし、かつ最大のを求められますね。
したがって、各点間の距離のgcd(最大公約数)を取れば良いです。
余談ですが、RADの最大公約数って曲いいですよね。
提出コード
Submission #3153766 - AtCoder Beginner Contest 109
D - Make Them Even
問題
のマス目について、マスに枚のコインが置かれている。
以下の操作を何度でも行える時、偶数枚のコインが置かれたマスの数を最大化せよ。
操作
- 選んだことのないマスのコインを1枚選び、そのマスの上下左右のマス1つに移動する
制約
入力は全て整数
1 ≦ ≦ 500
0 ≦ ≦ 9
解説
各マスの数をmod 2で考えれば良いです。
言い換えれば、2進数の最下位の数にのみ注目すれば良いです。
なぜなら、下2桁以上はどのような数であろうと必ず偶数になるからです。
したがって、全てのマスを% 2
で置き換えて以下のように操作すれば良いでしょう。
(見たマスの枚数 % 2) が「1」である。
見たマスが右下の端である(座標が(H, W)のとき)。
- スルー。
見たマスが右端である(座標が(*, W)のとき)。
- そのマスのコインを下に移動し、下のマスの枚数を
+1
する。
- そのマスのコインを下に移動し、下のマスの枚数を
それ以外
- そのマスのコインを右に移動し、右のマスの枚数を
+1
する。
- そのマスのコインを右に移動し、右のマスの枚数を
(見たマスの枚数 % 2)が「0」である。
- スルー。
ジグザグ解いているContestantもいましたが、そちらの方が良いんでしょうかね?
提出コード
Submission #3156056 - AtCoder Beginner Contest 109
感想
今回は上手くいったので満足しています。
次回のAGCもうまいこと行くと良いな。
それと現在開催中のCRCTFですが、全完チームはやはり凄いなぁという気持ちです。