Codeforces Beta Round #42 (Div. 2) 参加記

総合2位(･∀･)！

A. Football

試合に勝ったチーム名が渡され、一番勝った回数が多いチームが優勝。優勝したチームを求める問題。

やるだけ。
00:04 492 Accepted.

B. Letter

新聞紙の文字を切り抜いて、脅迫文みたいな手紙を作る。
1行目が新聞紙の文字列、2行目が作りたい手紙。手紙が作れるか判定する問題。

各文字の出現回数を数えておいて、手紙の文字を引いていくだけ。
00:09 964 Accepted.

C. Lucky Tickets

3の倍数になる数字が書かれている紙を、2つに破られた。
2つの切れ端をくっつけることで、これを復元したい。
復元したものが3の倍数になっていれば、とりあえずよしとする。
復元できる枚数の最大値を求める問題。

各桁の合計が3の倍数になっていれば、その数自体は3の倍数になっているので、
渡された切れ端の各桁の合計を3で割ったあまりごとの枚数を保持しておいて、以下のように復元する。
・余り0→余り0の切れ端をくっつける
・余り1→余り2の切れ端をくっつける
余り0の切れ端は、単に余り0の枚数を2で割ればよく、
余り1や余り2の切れ端は、どちらか少ない方の枚数だけ復元できる。
00:16 1404 Accepted.

D. Journey

n×m のマップあがって、左上にお城がある。お城を出発して、全てのマスを巡り、
再びお城に帰りたい。ただし、1つのマスは1回しか巡らない。
このとき、お城に帰れないパターンが存在するので、その場合はテレポートマスを
作ることができる。
必要なテレポートマスの数、テレポートマスがどこからどこへテレポートするのか、
そして巡る座標を順番に求める問題。

撃墜祭りでした。
1x1、1x2、2x1、1xN、Mx1に関しては、特に注意が必要で、別個に処理を書いてもいいと思います。
後のケースについては、どちらかが偶数であればテレポートマスは必要なく、
両方とも奇数のときは、右下の座標から左上のお城に向かうテレポートマスを1つ用意して、
後はうねうねと走査するだけです。
00:54 Accepted.
01:15 Hacked.

E. Race

レースのお話。走る車の数と、コースの距離が与えられる。
更に、それぞれの車が走る速度と、その速度で走る時間が k 個与えられる。
ある車が別の車を追い越す、といった場面が何回現れるか求める問題。

各時間における各車の位置を求めておいて、
後は i 番目の車が j 番目の車に対して、追い越す回数＋追い越される回数を計算するだけ。
単純に実装すると、100*100/2*100000=500000000となり、かなり実行時間に不安を覚えるけど、
なんとかTLEせずに間に合ったみたい。
01:19 Accepted.

After System Test

oooxo +12/-1 5720
2位　1486 -> 1668
いきなり黄色になってしまった。(次回で青に落ちるんだけど。)