Codeforces Round #57 - simezi

大分久しぶりな感じのするCodeforces.

480 / 736(2WA) / 1018(1WA) / - / -
108位

1801->1841

一辺がnの正方形があり、それぞれの頂点の座標は(0,0),(0,n),(n,0),(n,n).
今正方形の辺上に2点A,Bがある。
辺上のみを動いてAからBまで移動するときの最短の移動距離を求めよ。

最初正方形の辺上を通らなくてもいいと誤読。サンプル合わなくておかしい。
マンハッタン距離？いやいやそれでもサンプル合わない。

辺上を移動するらしい。
え、Aなのにいきなり結構面倒な問題。。。どうしよう。
4頂点とA,Bで隣接行列作ってグラフにしてワーシャルフロイドしようｗ

書けた。送信。プレテスト通過。

問題文がめちゃくちゃ長い。しかも意味不明。ということで先にCを解いた。

直方体の石で階段をm個作る。
それぞれの階段は始点a[i],終点b[i]で最初の高さがc[i].高さは一段ずつ高くなっていく。
もし同じ場所に複数の階段が作られる場合、階段の石の数は和になる。

求めたいk個の場所の石の数の和を求めよ。

日本語にしても意味不明。
なんだか、公差1の等差数列をいっぱい作って足せみたいなことを言ってる？
そのようだ。

全部シミュレートすると間に合わないけど、クエリのある場所の石の数は（等差数列の途中の項なので）簡単に計算できる。
書けばいいんじゃない。

書いた。プレテストWA.えー？
long long？送信してみる。WA.

あ、これってクエリ毎に石の数を求めるんじゃなくて、クエリの場所の石の数の合計を出力せよという問題だった。なんじゃそりゃ。

修正。送信。プレテスト通過。

こっちが読みやすかったのでこっちから。

それぞれの項が1以上n以下の整数で、単調非減少または単調非増加の数列はいくつあるか、mod10億7で求めよ。
nは10万以下。

えーと、なんかDPっぽくて……？

漸化式を書いているうちに項数50以下で各要素10万以下みたいなことに問題がすり替わる。これは酷い。
O(nm^2)のDPだとTLEでO(nm)にすればいいのかな？
えーと、dp[i][j]にはdp[i][j-1]の値が利用可能で、そうするとオーダーが落ちる。

後は2倍して対称な部分（全部aの数列）は2回数えてるのでそこを引く。
書けた。値も合ってるっぽい。送信。

（Bへ。Bを解いているときにHacked!というメッセージを受ける）
ソースを読み直して50とかいう意味不明な数字を見て絶望する。

んーと、だから、O(n^2)だと時間間に合わなくて……
ああもう数列検索しよう。一般項C(2n,n)-nらしい。
二項係数だから普通に掛け算で求めればいいか。

書いた。送信。テスト通過。

nxmのグリッドの各マスは.またはXである。
グリッドの中から任意の.の2マス（異なるとは限らない）が等しい確率で選ばれる。
このとき、Xのマスを通らずに始点から終点まで行くようなパスの長さの期待値を求めよ。

n,m≦1000であり、
Xのマスは各行、列に最大1つ。なおかつX同士が斜めに接触することもない。

Xがまったく無い場合は2ΣΣabs(i-j)/nmみたいなことに。
Xがあると、その両脇のマスが選ばれたとき、Xを迂回するためにステップが2増える。
んで、Xがいっぱいあると？？

.....
C..X.
AX..B

これAからBは迂回が必要でCからBとかは不要。。。
どうなんだ。

30分くらい考えてわからないので就寝。