20200222_ABC156/

README

ABC156 感想

70分5完でパフォは1700弱だったので満足。 Fはちょっと見た目がすごくてノーチャンスに見えた。

• A問題は方程式を解いて O(1) の算数。
• B問題は基数で割った回数を答えられば良い。ちょっとWAが怖かった。
• C問題は簡単な全探索。こういうのはノータイムで全探索。
• D問題は組み合わせをMODでとったものを計算するいつものやつだと思ったが、 C(n, r) の n が 10^9 で困った。
  • が、問題の設定から O(r) で素直に求めれば良い（高校数学の手計算でやる手順）だけだとわかる。
  • 気づくのに10分かかった。
• E問題も組み合わせ・重複組合せを用いる数え上げ問題。
  • 重複なく数え上げるには、「部屋数が0のものの個数を i として、ありうるものの総和を計算する」というのが良い（と思ったのでやった）。
    • k の制約によって各 i が実現できるかがわかる。
    • 各 i については C(n, i) * H(n-i, i) で計算できるとわかる。
• F問題は全くわからなかったので、最初から解答を観てしまってもいいと思う。

おぎんぎんさんのツイート

Fが面白かった こういうの我々は10進法にoverfittingしてしまっているので、mod10を考えると途端にわかりやすいんだよな

なるほど。。