うっかりには気をつけよう

どうしてこうなった…

ちなみに下から古い順番です。ちなみに正解じゃなかった原因は、

• 下から2つあるREが回答する問題の選択ミス
• いちばん下にあるWAと、他3つくらいはデバッグ用のputsの消し忘れ
• 最後のREとWAは構文エラー+バグが復活
• そして何よりも問題をちゃんと見ていなかった

ふえぇ…気をつけよう。
ちなみに今回のARCはこんなかんじでした。

A問題の内容

1列に並んだたこ焼きの色を交互に変えられるという無駄な能力を発揮させ、大量のたこ焼きの色を変えたとき、その列のいちばん端にあるたこ焼きの色を答える問題です。
奇数と偶数の判定ができて、条件をちゃんと読んでいればワンライナーで書ける言語がいくつかあります。

B問題の内容

2人でしりとりをしていって、どちらが勝ちか、あるいは引き分けかを判定する問題です。
順番に見ていったときに、ある文字列の最後の文字とその次に見る文字列の最初の文字が初めて違った場所と、同じ文字列が2回出てきた場所を覚えておきます。
最後にこの2つを比較して小さいほうを選ぶか、「どちらでもない」かの結果を出します。このへんはまだ愚直にやっても大丈夫。もう少しスマートに解きたかった。

C問題の内容

3色のボールを、ある順番で同じ色のボールが２つっつくと消えてしまう両端が開いた筒の中に入れていったとき、筒の中に最終的に何個のボールが残っているかを問う問題です。
実は計画的に筒の中にボールを入れていけば、筒の中に4個以上のボールがあることはありません*1。ここに気づけばあとは簡単です。

D問題の内容

grepでヒットした行とオプションの-xと-yに設定する値がいくつか与えられるので、それぞれについて検索結果で表示される行の数を数える問題です。
糸口が見つかった時点で時間切れを喰らいました。そして居残りでそれを提出したらTLE(訳:君のプログラム遅すぎ(ﾌﾟｹﾞﾗ)を喰らいました。
D問題は毎回100行くらいのコードを書く必要がある感じなのですが、今回は20行くらいで正答しているPythonのコードがありました。以下に引用します。コメントは私が入れたものです。

import bisect
#入力を受け付ける
all_, N, M = map(int, raw_input().split())
L = [int(raw_input()) for i in xrange(N)]
xy = [map(int, raw_input().split()) for i in xrange(M)]

#検索にヒットした行の差分をとる
diff = []
for i in xrange(len(L) - 1):
    diff.append(L[i + 1] - L[i])
diff.sort()

#差分を足しこんだものを得る
accumulated = [0]
sum_ = 0
for i in xrange(len(diff)):
    sum_ += diff[i]
    accumulated.append(sum_)

#オプションの入力によって表示される行数を得る
for x, y in xy:
    #xとyの和より小さい差分の数を求める
    i = bisect.bisect(diff, x + y)
    #かぶりがない部分の表示行数を求める
    lines = accumulated[i] + (len(diff) - i) * (x + y + 1)
    #かぶりがある部分の表示行数を求める
    lines += min(L[0] - 1, x)
    lines += min(all_ - L[-1], y)
    #補正して出力
    print lines + 1

bisectを使うことでかぶりがないヒット行数を素早く検索しているようです。(見落としているだけかもしれませんが、)残念ながらRubyの標準ライブラリにそれっぽいものが見当たらなかったので同じように書いてもやっぱりTLEを喰らいました。うーん…

*1:すこし思考実験してみればわかるが、4個目のボールを筒の中に入れるとどれかの色が必ず消える。ちなみに4色以上あるとそうはいかないときがある