Codeforces Round #43 - simezi

不調回

Result

00:11 / 00:22 / 00:30(1WA) / 02:47(4WA) / 02:43(9WA) / - / -
5AC Penalty 673

148位
1803->1761

A. Ball Game

問題

n人が輪になって以下のようなゲームを行う。
はじめ1番目の人がボールを持っている。
次に隣の人にボールを渡す。
次に2つ隣の人にボールを渡す。
次に3つ隣の人にボールを渡す。
……
この操作をn-1回繰り返す。
それぞれの操作において、ボールを渡される人の番号を出力せよ。

試行錯誤

サンプルおかしくない？
……

10分くらい問題を読み直して必死に考える。
サンプルが間違ってたらしいorz.送信、AC

B. T-shirts from Sponsor

問題

サイズがS,M,L,XL,XLLのシャツがそれぞれNS,NM,NL,NXL,NXXL枚ある。
n人の人がTシャツを受け取る。
n人にはそれぞれ自分のサイズがある。
自分のサイズがあるときそのシャツを、
ないときは1つ違うサイズのシャツを、それも不可能なときは2つ違うサイズのシャツを……
と取るとき、各人の取るシャツのサイズを出力せよ。

ただし、シャツの取り方が一意に定まらないときは大きいほうのサイズのシャツを取るものとする。

試行錯誤

ちょっと読解に手間取る。実装ゲー。書いて送信、AC.

C. Hamsters and Tigers

問題

ハムスターとトラの並びがH,Tの文字によって与えられる。
ハムスターとトラは輪になっていて、文字列の右端と左端の動物は隣り合っている。

これらの動物を、ハムスターとトラが隣り合う数を最小になるよう並べ替えたい。
並べ替えは任意の二つの動物を入れ替える操作を繰り返すことで行う。
このとき、必要な最小の入れかえの操作の回数を求めよ。

試行錯誤

動物の数は最大1000なのでO(n^2)で間に合う。
結果の文字列をn通り全て試す（ハムスターの開始位置をn通り試す）のはどうか。
結果の文字列と異なる文字の数を数えて、その数/2が答えのはず。

書いた。送信。AC.

D. Parking Lot

問題

長さLの道路の右端が駐車帯になっている。
車は前方fメートルにも、後方bメートルにも車がない場所で、なおかつ駐車帯の開始位置から最も近い場所に駐車する。

やってくる車のサイズおよび出車する車の番号が与えられるとき、
車が停車する位置を駐車帯の開始位置からの距離で答えよ。

L,f,bは整数で、L≦100000,1≦f,b≦100を満たす。
処理する車の数は100以下、車の長さは1000以下である。

試行錯誤

座標は全て整数なので長さ100000の配列でそこに車があるかを持っておけばよい。
車の位置の探索は、100000通りをナイーブに試すと、
10万x1000x100で100億でTLEになりそう。

が、長さがf+l+bのスペースがあるかを探せば同じスペースを２度見なくて済むので、
10万x100=1000万で間に合う。
実装。ちょっと手間取る。
サンプル合わない。あ、駐車帯の最初に止まる場合はf+lのスペースでいいんじゃん。

訂正。サンプル通った。送信WA.
あれー……

駐車帯より長い車が来たとき0を返すようにしよう（←本当は-1を返す。これで1時間以上はまった）
駐車帯の後方に車がないときもおｋ.送信WA.
ループの更新間違ってる？訂正して送信WA.

もしかして問題読み間違ってる？
最初に止まってる車の後方bメートルにも入っちゃいけないのかな？
そうすると間隔はmax(f,b)にしないとだめなのかな。
送信WA.

泥沼になってきたので次の問題に。
Eを9WAの後ACした後で最初のバグに気づいてAC.酷い。

E. Comb

問題

nxmマスに区切られた長方形の部屋がある。
それぞれのマスには数字が書かれている。
1行目の先頭からc1個のマスを、2行目のc2個の先頭からc2個のマスを…
n行目の先頭からcn個のマスを選ぶ。
その後それぞれのマスに書かれている数の合計だけコインがもらえる。

ただし、ciはそれぞれ自然数であり、c1＞c2＜c3＞c4…という不等式が成り立たなければならない。
このとき、もらえるコインの枚数の最大枚数を求めよ。

n,m≦1500かつ、それぞれのマスに書かれた数の絶対値は1万以下である。

試行錯誤

えーと、n^3のDPで間に合う？
10億くらいだから、各ケースごとに2秒もあるし間に合うような気もする。

書いてみる。TLE.
あら。1500^3なので30億以上。これは間に合わない。

n^2のDPにする必要が。
（以下追記予定）