Round2

また250サブミットできなかった...。

250

有向グラフが与えられるので、双方向に枝がある場所を単方向にするという処理を施して、閉路がなくせるかどうかを判定せよ、という問題。

実は双方向の枝は両方向に除去しても影響しない(うまく除去すれば必ず閉路を発生させないようにできる)ので、単方向の枝だけで閉路があるかどうかを判定すればいいらしい。後はWarshallFloydをやるだけ。

500

あるベクトルの要素を100回まで右にずらす(v[i]=v[i]-1,v[i+1]=v[i+1]+1)ことができるとき、もう一つのベクトルとの内積を最大にせよという問題。

後何回操作できるかと、いくつ前の段階でずらしたか、今何番目の要素を操作しているか、のDPをすれば良い。結果がlongになるらしいので、値が溢れないように適宜注意する必要がある。

1000

見てない...。