AtCoder Regular Contest 079

参加しました。

C問題　Cat Snake and a Voyage

N個の島にM種類の定期船があって1とNをつなぐ定期船がないとき、2種類の定期船を使って1からNへ行けるか判定する問題。

1と直接つながっているかとNと直接つながっているかを調べて、どっちともつながっていたらPOSSIBLE。そうでなければIMPOSSIBLE。

D問題　Decrease (Contestant ver.)

長さNの非負性数列{a_i}に対し、数列の最大値がN-1以下になるまで以下の操作を繰り返し行う。

・数列の最大の要素を1つ選んで、この要素を-N。それ以外を+1。

ちょうどK回で操作が終わるようなNと数列{a_i}の組を一つ求めよ。という問題。

Kの値がむちゃくちゃでかいので構成は簡単にできるんだろうなと思った。

とりあえず1回につき全体の和は-1されていくのでその方針で考えていくことに。

m,m,...,mに対してN回操作を行うと、m-1,m-1,...,m-1になるので、この方針で考えた。

全ての操作後、n-1,n-1,...,n-1に成るような数列を考える。n=50とする。

まずn-1+k/n,n-1+k/n...,n-1+k/nにして残った回数k%n回について逆操作を順にやっていけば出来上がり。(制約条件に引っかかって1WA)

E問題　Decrease (Judge ver.)

D問題の逆で、数列が与えられた時に操作回数Kを求める問題。

a_iについて他の項は考えず何回Nを引けばN-1以下になるかv_iを計算。その和をSとする。

そのような操作を全部やると、

a_i = a_i - v_i*N + (S-v_i)

これをS=0になるまで繰り返した。

F問題はまあグラフの操作ができないマンでした。

順位 84位　パフォーマンス 2486 レート 1976(+77)

黄色チャンスですね！（m期ぶりn回目）