Codeforces Round 101 (Div2 only)

Result

466 / 830(1WA) / 1606(1WA) / - / -
2902 84位
レート変動はなし。

C. Queue

問題

列にn人が並んでいる。
それぞれの人の、「自分の前にいて、自分より身長が高い人の数」a[i]が与えられる。
元の列としてありうるものをどれか一つ出力せよ。

制約条件

n≦3000

試行錯誤

まずはCあたりから読む。
げ、苦手な感じ。でもDiv2 Cだから流石に解けるはず。
前にいる身長の高い人が少ない順にソートする。

それで……前の人数だけ身長伸ばせばいいんじゃないだろうか。
書いてみた。サンプル合った。
送信
WA.

ですよねー
もう少し考えたけどあきらめてAへ.

A. Amusing Joke

問題

文字列が3つ与えられる。
3つ目の文字列が、最初の二つの文字列をつなげて並べ替えたものになっていればYESを、そうでなければNOを出力せよ。

制約条件

文字列は英大文字のみを含む
それぞれの文字列の長さは100以下

試行錯誤

出現回数を数えればいい。
書いた。

送信。
pretest passed.

B. Hopscotch

問題

■■
 ■
■■
 ■
■■
 ■
 ■

のように1-1-2-1-2-(以下1-2繰り返し）塔をつむ。
ブロックの一辺はaで、
一番下のブロックの下側の辺はx軸であり、
縦方向の塔の中心線はy軸である。
ブロックには下、左から順に1,2,3,……と番号がついている。

(x,y)の座標には何番のブロックがあるか。
境界線上のときはブロックではないと判定する。

制約条件

a≦100
-10^6≦x,y≦10^6

試行錯誤

aで割って余りとって内部にあるか適当に判定すればいいか。
Div2 Bの割りに面倒な気がする。

サンプルあった。
確認してないけどめんどいから投げる。
WA.

今回適当すぎてダメだ。
見直す。y＜0のとき誤判定するようになってる。
あと、一箇所割り算間違ってる。

直して送信。pretest passed

C（再）

「前に背の高い人が少ない順に」ソートした後の列は、
別に必ずしも背の小さい順に並んでるわけじゃないじゃん。

てか背の小さい順ではない順に並べたほうが列が作りやすいんじゃ。

列を後ろから決めていく。
前にi人自分より高い人がいるなら、
今までで使ってない値のうち、i番目に大きいものを使えばいいだけ。

なんだ……
書いた。送信。
pretest passed.

D. Take-off Ramps

問題

長さLのスキーのコースがある。
n個のジャンプ台があり、それぞれの座標はx[i]
ジャンプ台を使うと、x[i]+d[i]に、t[i]の時間をかけて飛ぶことができる。
ただし、ジャンプ台を使うためにはx[i]-p[i]から地上を滑っている必要がある。

スキーヤーが地上をすべるスピードは1であるとき、
コースを滑り終えるのにかかる最短時間を求めよ。

コースは逆走してもよいが、ジャンプはゴール方向へとしか飛べない。
また、コースの外にはみ出てはならない。

制約条件

n≦10^5
L≦10^9

試行錯誤

うーん、解いてる人少ない。
今回の問題は難しめ？

どうやるんだろう。逆走がなければただの座標圧縮+DP.
逆走がある。
segment treeを使うのだろうか。
segment treeに、(その時点での最短時間+x座標)の最小値をもたせておく。
すると、前方で、ジャンプ台を使ったほうが得になる座標がlog nくらいで求まる？

残り45分くらい。書けるかなあ……むずくね……
書いてみよう。

書いた。
なんとかサンプルの数字だけは合った。
てか使ったジャンプ台全部出力しなくちゃいけない!!

むり！！

E. Clearing Up

問題

n頂点とm本の辺からなる無向グラフがある。
それぞれの辺にはSまたはMのラベルがついている。
グラフの全域木で、Sのラベルのついた枝とMのラベルのついた枝を等しい本数だけ使っているようなものがあるか。

あればそれを出力せよ。

試行錯誤

一応読む。

komakiが一瞬で解いてるから解けるのか。
でもどうみても典型問には見えない。
komakiが天才すぎるだけか。

ていうか今回問題むずすぎじゃない？

System Test

A,B,C通った。
komakiのE落ちてる……