0x19fの日報

なるべく毎日書きます

7/4 ソフトウェア制作...

AOJ-ICPC(A〜Cぐらいの問題を巡回することにした.)

  • Kakezan | Aizu Online Judge [解答]

  • Let's Solve Geometric Problems | Aizu Online Judge [解答]
    結構苦戦した.

  • Koto Distance | Aizu Online Judge [解答]
    X方向/Y方向を別々にチェックすればOK. O(W + H)で計算できる. チェックはimos法使ってある座標を含むクエリの数を数えて, その最小値が0でなければOKという感じ. X/Yどっちかで全範囲カバーされていればYes, そうでなければNo.

  • Fast Division | Aizu Online Judge [解答]
    こういうタイプの問題苦手. n >= 3の時に0を出力すればいいことを示せば終わり. どう考えても具体的な値は求められないから, あるところから答えが一定になるんじゃないかなぁとは思ったけれど. 証明にはフェルマーの小定理(aとpが互いに素ならa^(p-1) ≡ 1 (mod p))を使う. 思い返すと高校生の頃からこういうの苦手でしたね.

  • ABC Gene | Aizu Online Judge [解答]
    問題勘違いし続けてひたすら時間を溶かした. 本番だったら死にたいレベル.  "ABC"を見つけて'A', 'B', 'C'のいずれかに置換するって手順をdfsしながら見てく. 最終的に"ABC"に一致すればOK. 気をつけないといけないのが, 'A', 'B', 'C'のいずれかを選んで「「「全て」」」"ABC"に置換すると言うところ. 全て置換するので, dfsする時に置換先の文字が他に含まれていたらカットしないといけない.

 

ソフトウェア制作やらないといけないんだけど, 気分が乗らない......