AtCoder diverta 2019 Programming Contest 2

A, Cの2完。終了5分前でぎりぎり通したので、それまでは生きた心地がしなかったです・・・。

各問題

A - Ball Distribution

K - 1人に1個配って、最後の一人に残り全部を配るのが最適です。なのでN - Kが答え、ですが、K == 1のときは一人に全部配る以外の選択肢がないので、そもそも差が存在しないので場合分けしなければなりません。

サンプルにその例がなかったら1WA出してたと思います。怖い・・・。

B - Picking Up

N <= 50 なので、全探索でいけることはわかりましたが、肝心の探索方法がわからずじまい・・・。

editorial にあるような「(xi −xj , yi −yj )で最も多いものが何個あるか」という解法はうっすら浮かんだのですが、実装できずじまいでした。とほほ。

そんなわけで、Bを諦めた時点でCまたはDを通さないと凍死確定ということに。さあ、Toyさんの運命やいかに。

C - Successive Subtraction

自分が最終的にたどり着いた解法がこちら。（ちなみに、ここに至るまでにものすごく試行錯誤しています・・・。）

• N == 2 のとき
  • 大きい方から小さい方を引く
• N > 3 のとき
  • 非負の数と負の数がどちらもある場合
    • 非負が多い場合
      • 非負と負を相殺して非負にする（非負から負を引いて非負を新しく作っていく）、このとき負を一つだけ残す
        • 一つだけ残った負から、余った非負および先の作業で作った非負を一つを残して引いていく（一つだけ残った負の絶対値が増えていく）
          • 一つ残した非負から、一つ前の作業のでできた負の数を引く
    • 負が多い場合
      • 非負と負を相殺して非負にする（負から非負を引いて負を新しく作っていく）、このとき非負を一つだけ残す
        • 一つだけ残った非負から、余った負および先の作業で作った負をすべて引いていく
  • 非負の数しかない場合
    • 最小値から最大値を引いて負数を一つ作る
      • あとは非負の数と負の数がどちらもある場合に帰結する
  • 負の数しかない場合
    • 最大値から最小値を引いて非負数を一つ作る
      • あとは非負の数と負の数がどちらもある場合に帰結する

と、まあ、場合分けを頑張って実装でねじ伏せてやりましたよ、ええ。（あかん） とはいえ、前述の通りこれを嘘でも何でも通さないといけない状況に陥ってしまったので、やりきったといえばいえるかも。

editorialや公式YouTubeのような考察は、残念ながら私の頭からは出てきませんでした。

D - Squirrel Merchant

Bが解けなかった時点でCとの二択だなと思ってちらっと見たのですが、その瞬間DPであることを察し、600点のDPはまだ無理だろうということで華麗にスルーしました。

EとF

このような状況だったので、当然問題を開いてもいません。

まとめ

善悪は別として、これぞまさに火事場のクソ力。

レートが下がることも覚悟していたのですが、ギリギリ水パフォで踏みとどまれました。