はい。
A
(0, 0), (1e9, 1), (a,b) を頂点とする三角形の面積の 2 倍は 1e9+b-a なので、適切に a, b を決めるとよい。これは算数と言っていいと思う。
結果的にこれを 8 分で通したおかげで青ぱふぉだったが、それはコンテストとしてどうなん？という気もする (まあ下の人たちは考慮されなくていいんだけど...)。
B
愚直シミュレーションは deque で O(NK) でできるが時間が足りない。
K が大きいので周期になりそう。ある場所からはじめて空になるのは、最初の数字がもう一回現れるとき。なので、数字ごとに添え字をリストで管理し、空になった次の添え字を調べていく。再び 0 になるまでチェックすればよい。その際、その添え字スタートになるのが何週目かもカウントしておく。
これで周期も計算できるので、K周やる直前に空になる状態を再現し、そこから最後までシミュレーションするとよい。これで O(N) でできる。
本番はいろいろバグを埋め込み、キレて集中力も続かず解き切れませんでした...メンタルトレーニングが大事っぽいな？
C
まずありうる数列の必要十分条件を考えると
・和が 3M
・どの項も 2M 以下
・奇数の項が M 個以下
となる。必要性は明らか。十分性は、M についての帰納法で示せる。
あとはこの数列の個数をカウントするとよい。これは和が 3M の数列全体から余事象で求めるとよい。具体的には、2M+1 以上の項がある数列の個数と、奇数が M+1 個以上の数列の個数を出すとよい。なおこれらは排反。前者はでかい項の場所を、後者は奇数の場所を fix すれば簡単に計算できる。どちらもひとつひとつは O(1) で計算できるため、全部で O(N+M) でできる。
これは解くべきだったなぁ......
D 以上はまた今度。
