task4233のめも

書きたいことをつらつらと

ABC109 - 参加記録

もくじ

問題リンク

Tasks - AtCoder Beginner Contest 109

はじめに

この記事では、今回の参加記録およびABC109の問題・解説が書かれています。

上にもくじがあるので、ご活用ください。

結果

全完で57位でした。

f:id:task4233:20180909115202p:plain

なぜかエスパーで解法が降ってきたので速く解けたのだと思います。

以下、各問題と解説です。

A - ABC333

問題

1以上3以下の整数A, Bについて、A \times B \times Cが奇数となるような1以上3以下の整数Cが存在するか判定せよ。

制約

  • 入力は全て整数

  • 1 ≦ A, B ≦ 3

解説

以前のABCでも似たような問題が出ていました。
(問題名を忘れました。申し訳ないです。)

積が奇数となるのはかけられる数が全て奇数の時なので、
A, Bが共に奇数の時に「Yes」それ以外の時に「No」を出力すれば良いですね。

提出コード

Submission #3151300 - AtCoder Beginner Contest 109

B - Shiritori

問題

N個の単語について、以下のルールを満たしている時に「Yes」を、そうでない時に「No」を出力せよ。

ルール

  • 同じ言葉を2回以上使っていないこと。

  • 1つ前の最後の文字と今発言する最初の文字が同じであること。

制約

  • 2 ≦ N ≦ 100

  • w_{i}は英小文字からなる1以上10以下の長さの文字列である。

解説

制約からN2でも問題なさそうなので、ルールを守っているかを愚直に確認すれば良いですね。

提出コード

Submission #3152586 - AtCoder Beginner Contest 109

C - Skip

問題

数直線上にあるN個の都市があり、 i番目の都市は座標x_{i}にある。

あなたはある整数Dを設定すると以下の移動が行える。

  • 1: 座標yから座標y + Dに移動する

  • 2: 座標yから座標y - Dに移動する

ここで、あなたが座標Xから出発した時の全ての都市を回れるDの最大値を求めよ。

解説

この問題はごちゃごちゃしていますが、
重要なのは「座標yから座標y ± Dにのみ移動出来る」ということですね。

例えば、15という座標があったとき、

この時のDの最大値は4ですね。

この例を観察すると「4」という数字について、
「5 ≡ 1 (mod 4)」すなわち「5 % 4 == 1 % 4」という性質があり、
「座標間の距離についてDを法として合同(mod D)」であることが分かります。

この問題ではDの最大値を求めるため、
各点との距離の最大公約数を求めれば「座標間の距離についてDを法として合同(mod D)」を満たし、かつ最大のDを求められますね。

したがって、各点間の距離のgcd(最大公約数)を取れば良いです。

余談ですが、RADの最大公約数って曲いいですよね。

提出コード

Submission #3153766 - AtCoder Beginner Contest 109

D - Make Them Even

問題

H \times Wのマス目について、マス(i, j)a_{i,j}枚のコインが置かれている。

以下の操作を何度でも行える時、偶数枚のコインが置かれたマスの数を最大化せよ。

操作

  • 選んだことのないマスのコインを1枚選び、そのマスの上下左右のマス1つに移動する

制約

  • 入力は全て整数

  • 1 ≦  H, W ≦ 500

  • 0 ≦ a_{i, j} ≦ 9

解説

各マスの数をmod 2で考えれば良いです。

言い換えれば、2進数の最下位の数にのみ注目すれば良いです。

なぜなら、下2桁以上はどのような数であろうと必ず偶数になるからです。

したがって、全てのマスを% 2で置き換えて以下のように操作すれば良いでしょう。

  • (見たマスの枚数 % 2) が「1」である。

    • 見たマスが右下の端である(座標が(H, W)のとき)。

      • スルー。
    • 見たマスが右端である(座標が(*, W)のとき)。

      • そのマスのコインを下に移動し、下のマスの枚数を+1する。
    • それ以外

      • そのマスのコインを右に移動し、右のマスの枚数を+1する。
  • (見たマスの枚数 % 2)が「0」である。

    • スルー。

ジグザグ解いているContestantもいましたが、そちらの方が良いんでしょうかね?

提出コード

Submission #3156056 - AtCoder Beginner Contest 109

感想

今回は上手くいったので満足しています。

次回のAGCもうまいこと行くと良いな。

それと現在開催中のCRCTFですが、全完チームはやはり凄いなぁという気持ちです。

ハリネズミ本を買おうかどうか悩んでいるのですが、毎回Amazonカードを買うのを忘れて帰宅してしまうんですよね。