A, B, C, D に挑戦、A, B, D が Pretests を通り、DがSystem Testで落ちた。。

獲得点数は 1202: A=488 (00:06), B=714 (00:34), C=(-2), D=(-2).

A と B はそこそこ読解ゲーだった。

A. I_love_%username%

http://www.codeforces.com/contest/155/problem/A

はじめの読解ゲーがこれ。

まあストーリーな部分から本題を探すのにかなり時間が。

Output を見るに "Amazing performances" の数を出すべきで、 コンテストへの出場履歴の中からそれを数えるみたいな感じらしい。

で、Inputとそのサンプルをみると、１行目がスコアの数 (= コンテスト参加数), 2行目にそのスコアがスペース区切りでくるとある。

そしてまあなにが amazing かというと "amazing in two situations:" という文に続き amazing の条件がかいてある。"more" と "less" が太字になっている。スコアの上下から判断するとみて、とりあえずちゃんと読まずに以下のように解釈した。

• 前回から成績が下がった
• 前回から成績が上がった
• ただし１回目は絶対に amazing ではない。

サンプルをみるにこれだと明らかにおかしいのでちゃんと英文を読むと、 "he earned on each past contest" とあるので、ハイスコアと最低スコアを更新 した時が amazing のようだ。ということで:

• ハイスコアの更新
• 最低スコアの更新
• ただし１回目は絶対に amazing ではない。

これで実装すると sample と正しい動きをするので提出。所要時間６分。

解答: https://github.com/sorah/sorah-codeforces/blob/master/155/a.rb

B. Combination

http://www.codeforces.com/contest/155/problem/B

A は本題を見つけるのが面倒な読解ゲーであったがこちらは 本題がかなりの読解ゲーであった。何が "More formally:" だって感じ。

本題というかやるべき事は 2 段落目に書いてある。3 段落目の More formally らしい文章から先によむと混乱を招いた。

• プレイヤーはカードを持っている
• カードの裏表それぞれには 0 を含む正の整数が書いてある
• カードは使用する事ができ、また同じカードは1度しか使用できない。
• プレイヤーはまず1枚カードを使用する。
• カードの表の数値 (a_i) はカードを使用したときにプレイヤーが得られるポイントが書いてある。
• カードの裏の数値 (b_i) に書いてある分だけ、プレイヤーは追加でカードを引くことができる。

とある。3 段落目をこれを理解したあとによむと「はじめにカウンターが１つで、カードを使用するとカウンターが１つへって、カードの裏面の数値がカウンターに加算され、カードの表の数値がプレイヤーのポイントとなる」みたいな事が書いてあることがわかる。

で、Output はこのルールと指定されたカードだと最大でプレイヤーが取得できるポイントらしい。

解き方としては貪欲法(?)というのか、よくわからんが以下の方法で解いた

1. カードをまず裏面を優先してソート、裏が等しければ表を利用して昇順ソートする。
2. 一番最後（一番裏の数値が大きい、または裏の数値が大きくその中でも取得できるポイントが高い）カードを使用する。
3. カウンターが1以上でかつカードがまだ残っていれば 1 に戻って繰り返す

解答: https://github.com/sorah/sorah-codeforces/blob/master/155/b.rb

C. Hometask

http://www.codeforces.com/contest/155/problem/C

結局解けなかったので解説もうまくできない。 要するに指定された文字列から指定された禁止の二文字を取り除かなければいけない、 文字列からすべての禁止パターンを取り除くには最低で何文字取り除けばいいか、という問題。

ちなみに Ruby でこういうの解くときはなるべく正規表現を使うと高速で素晴らしいです。

D. Colliders

http://www.codeforces.com/contest/155/problem/D

2312 年, n つの加速器が〜、らしいけど飛ばす。

最後の方にある箇条書き、Input などから見ていくと、

• n つの加速器がある
• 加速器には1以上n以下の番号がふられている
• 加速器のオン・オフ命令が Input されてくる
• オン命令は "+ 番号", オフ命令は "- 番号"
• オン命令の時、すでに指定された加速器がオンならば "Already on" を出力
• オン命令の時、 すでにオンになっている加速器の番号と指定された加速器の番号が互いに素 であるときは "Conflist with 指定された加速器の番号" を出力。
• オフ命令の時、"すでに指定された加速器がオフならば "Already off" を出力
• オン、オフ命令ともに上記の条件にマッチしない場合は (プログラム内部のオン・オフのフラグを切り替えて) "Success" を出力。

互いに素っていうのが面倒くさい。C++ でもよかったんだけれど Ruby で溶いてしまった。

毎回最大公約数を求めてるのでSystem TestでTLE食らった。仕方ないね...

(問題 C に執着せず、問題 D を C++ で再実装すればよかった。後悔。)

解答: https://github.com/sorah/sorah-codeforces/blob/master/155/d.rb