AtCoder Regular Contest 105 参加ログ・感想

普段は、AtCoder Beginner Contestにでているが、とりあえず挑戦という事で、Bまで解ければ良いと思ってAtCoder Regular Contestに初参加してみた。

---

内容

• Python3でやっている。
• 参加ログ。
• 所感。
• コンテスト中に何を考えたか。
• コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
• 問題の詳細で細かく書こうと思うものは別記事とする。

---

結果

A完。Bは愚直解しか思い付かず、TLE連発（そもそもあってるのかも謎。）Bの問題文を読んで最大公約数って言うところに気づけず悶絶し続け終了。

---

どう考えたか + α

A - Fourtune Cookies

問題タイプ：全探索

１つ以上をお菓子を選ぶ必要があるので、A, B, C, Dから * 1つ選ぶパターン → 残り3つと比較 * 2つ選ぶパターン → 残り2つと比較 の場合を考えれば良いだろうと考えた。これらが満たされるなら、矢印が逆の場合は考える必要がないので。

1. A, B, C, Dを別々に持たず、リストでもつ。
2. A, B, C, Dの合計を計算する（abcd_sum）。
3. まずは、１つ選ぶパターンの探索をする。
   1. abcd_sumから1つ選んだものを引いてそれと1つ選んだものが一致するかを見る。
4. 上記で一致しなければ、２つ選ぶパターンの探索をする。
   1. abcd_sumから１つ選んで引く。(i)
   2. さらにindexを進めながら引く。 (j:i以降のindex全部)
   3. abcd_sumから２つ選んだもの引いてそれと２つ選んだ合計が一致するかを見る。
5. ここまでで一致がなければ'No'である。

今書いてて、もう少し効率よくできそうな気もする。

abcd = [int(x) for x in input().split()]
abcd_sum = sum(abcd)
for i in range(4):
    if abcd_sum - abcd[i] == abcd[i]:
        print('Yes')
        exit()
for i in range(4):
    for j in range(i, 4):
        if abcd_sum - abcd[i] - abcd[j] == abcd[i] + abcd[j]:
            print('Yes')
            exit()
print('No')

---

B -

問題タイプ：最大公約数を使う問題

正直、問題を見て愚直にしか考えられず、優先度付きキューかなと思ってやってみたがTLE。最大値 - 最小の値を戻すっていうのを繰り返すが、この処理がどのくらいの処理数になるのかを見積もれなかったのが失敗。今考えるとからくらいはありそう。 なんとなくだけど（全てが、最小値になる状態なので、）

で、結局これは全部の最大公約数と一致するって言うのが答えで、gcd(x, y) = gcd(x, y - x)と言うのが理由だから。これは今回の手続きと同じである。（自分で証明はしてない）

def gcd(a, b):
    if b == 0:
       return a
    else:
        return gcd(b, a%b)
n = int(input())
A = [int(x) for x in input().split()]
ans = A[0]
for i in range(1, n):
    ans = gcd(ans, A[i])
print(ans)

---

おわりに

Aはできたが、Bは数学の感覚が悪すぎた。制約が気持ち少なければそこまで悪くないと思ったんだけど。 ARCはBまでを早く解けるように続けてみる。

---

参考になる書籍

• 問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)