AGC028

README

AGC028過去問感想

• A問題は300点だったが難しく感じられて2WA47分だったため、当時のパフォーマンスを調べると1150ぐらいで悲しいことになった。
  • 構成できる場合には長さはLCMにはなりそうだとは思ったが、確証を得ないままその仮定を置いてお絵かきすることで最終的な答えにたどり着いた。
  • まず、最初から 0-based で考えて理解を高速化すべきだった。
    • 衝突する文字のインデックスは単なる整数倍で考えることができるので楽になる。
  • 倍数の衝突とか、こういうのはなにかしら名前があるのだろうか？
  • 紙で考察をやり直したときの知見。
    • 数式で一般化しながら整理するフェーズと、具体的なサンプルを用いて定数を当てはめた具体的なケースを考察するフェーズ、どちらも同じくらい有用だった。
    • 解説PDFは（少なくとも自分にとっては）ストレートにたどり着けない考察、非自明に思われる事柄がサッと書かれているので、あまり落ち込まないこと。
    • この問題での重要な知識: 既約分数を得る、もしくは互いに素な数同士にするには、それぞれのGCDで割れば良い。