perogram

「別のクラスの人と3人組を作ってきてください」

動機

  • codeforcesでこの問題が解けなかった
  • https://codeforces.com/contest/1201/problem/B
  • 内容:数列Anからどれか2つを選んで-1することを繰り返し、数列を全ゼロにできるか
    • i != j
  • 解答は、max x 2 > sum のときNo, それ以外でYes
  • maxが飛び抜けちゃうとダメということ

f:id:peroon:20190805081441j:plain

一般化

  • これを一般化したのが下のmisteerの記事 & 熨斗袋さんの証明
  • 絵で描くとこういうことだろう

f:id:peroon:20190805082225j:plain

参考

https://misteer.hatenablog.com/entry/stone-cleaner