AGC018

README

AGC018過去問感想

Last Change: 2020-02-19 23:32:20.

• A問題は最大公約数に関する問題。なんとなくは分かるが証明を短時間で行うことができなかったので、一考する価値はある。
  • ABC118のC問題と併せて復習しよう。
  • 2つのボールだけの操作に絞って、それらの間で生まれる新しいボールも含めて再帰的に考えると、ユークリッドの互除法の形が見えてくる。
    • 似た形の問題では、操作対象を2つに絞ってみる、というのは大事な知見かもしれない。
  • この問題では、最終的には最大公約数の書かれたボールを箱に入れることができる、というところまで到達できると正しさを確信できそう。
    • 最大値Mから最大公約数Gを任意回引いた数も、やはりGの倍数であるため、箱の中に入りうる数がすべて列挙できる。
      • Mの倍数からより小さいMの倍数を引いて得られた数も、やはりMの倍数である。
  • また、最初からそのボールが入っていても条件を満たすということに注意（1敗）

B問題（@2020-02-19）

全くわからなかったため早々とPDFを読んだ。 問題の解釈を間違えていた。。

問題を解釈し直したら「それはそう」になってしまった。。

PDFがの通り再帰関数で書いてみた。