naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Beginner Contest 109

9/8(土) 21:00〜(ABC only回)
D(skip)→C→B→A→D、の順に解いて4完。

D - Make Them Even (400)

問題を読んで家事をして戻ってきて
何かネットワークとか二部グラフとか描かないといけないのかなあ
方針が思いつかなくてC-B-Aを先に読むことにした


C,B,Aを通した後に再訪。

  • 1方向にしか伝播できないってことは、変化は一筆書きにしか伝播しない?
    • いやそんなこともないけど…
  • あ、一筆書きにひっくり返していくことで解けるのでは?
  • すべてのマス目が何らかの順番で一筆書きに連なっているとして、端から見ていく。(○が偶数、●が奇数とする)
    • 〇〇: 何もせず1つ(ないし2つ)進む
    • 〇●: 何もせず1つ進む
    • ●〇: 奇数を1つ先送りにすることで 〇● に変えることができるので、〇●に変えて1つ進む。
    • ●●: 最初の奇数を次のマスに送ることで 〇〇 に変えることができるので、〇〇に変えて1つ(ないし2つ)進む。
  • 左から右、右から左、みたいに進めばいいよね(ロンゴロンゴ文字方式)
  • 末尾に1つ奇数が残ってしまう可能性はあるがそれはどうしようもない!
  • あとは操作を出力するだけ

→AC
https://beta.atcoder.jp/contests/abc109/submissions/3157444

C - Skip (300)

  • ±Dでしか動けない
    • ってことは、X±kD で表せない座標には行けない
  • すべての x_i を X±kD で表すには?
    • Dを全ての |x_i - X| の最大公約数にすればいい
  • 気をつけるべき条件は?
    • x_i == X な点があれば除外しておきたい(今回の問題には含まれない)

→AC
https://beta.atcoder.jp/contests/abc109/submissions/3155190

B - Shiritori (200)

  • 訪れた単語をsetに入れておくぐらい

→AC
https://beta.atcoder.jp/contests/abc109/submissions/3155737

A - ABC333 (100)

  • A, Bがともに奇数なら

→AC
https://beta.atcoder.jp/contests/abc109/submissions/3155971