AtCoder Beginner Contest 094の問題を解いた
第１問 Cats and Dogs
猫がA匹いることがわかっているのに加えて、追加で猫か犬かがB匹いる場合、猫がX匹いることが可能か。
不可能になるのはX < AかX > A + Bの二ケースなので、A <= X <= A+Bが成り立っているかどうかを調べる：
a, b, x = map(int, input().split()) print('YES' if (a <= x <= a+b) else 'NO')
第２問 Toll Gates
直線上に順番にならんでいる料金所を通るたびにコスト１かかるとして、地点Xからはじめて直線の左右どちらかの端に到達するのにかかる最小コストを求める。
料金所がもとからソートされているので、そのまま二分探索が使える。地点X自体には料金所がないことがわかっているのも処理を簡単にしてくれるポイント。
from bisect import bisect_left n, m, x = map(int, input().split()) axs = [int(x) for x in input().split()] i = bisect_left(axs, x) print(min(i, len(axs) - i))
bisect_left(axs, x)で地点Xの左にいくつ関所があるかがわかる。
右にある料金所の数は「料金所の総数 - 左側にある料金所の数」なのでmin(i, len(axs) - i)で最小コストが求められる。
ちなみにこれ、最初に書いた解だと
print(min(len(axs[:i]), len(axs[i:])))
になっていた。iが持つ意味を直観的に捉えきれてなかったのだろうか。こういうところで何気なく無駄な処理をしてしまうかどうかがけっこうアルゴリズムでは重要な気がする。
第３問 Many Medians
与えられたリストxsのある要素が含まれていない場合の中央値を、各要素ごとに算出していく。
xsの長さが偶数であるという制約で計算が楽になる。
xsの中央値を計算する場合は、中央にある二つの数字m1とm2 (m1 <= m2)の平均をとることになる。
とりあえずxsから最小値を除いたリストzsの中央値を考えてみると、m2であることがわかる。さらに最小値でなくてもm2未満のどの数字を除いたとしてもm2が中央値になる。
そしてm2以上の場合はm1が中央値だ（最大値からはじめて全く同じロジックを考えることができる）。
なので実装はこんな感じ：
n = int(input()) xs = list(map(int, input().split())) ys = list(sorted(xs)) m1 = ys[n//2 - 1] m2 = ys[n//2] medians = [m2 if x < m2 else m1 for x in xs] print('\n'.join(map(str, medians)))
実はPython3.4以降statisticsという標準ライブラリが追加され、median_lowとmedian_highという関数が用意されている。
medianはquickselectアルゴリズムを使ったりすると平均でO(N)になったりすることが知られているので、ちょっと期待して使ってみる：
from statistics import median_low, median_high n = int(input()) xs = [int(x) for x in input().split()] m1, m2 = median_low(xs), median_high(xs) medians = (str(m2 if x < m2 else m1) for x in xs) print('\n'.join(medians))
問題なくACするのだが、もとのコードが200msだったのがstatisticsを使うと300msほどになる。
CPython statisticsモジュールのソースにあたってみると、medianのなかでリストを複製ソートしていた。
元のコードで一番時間がかかるところをmedian_lowとmedian_highで二回やっているわけだからそれは遅くなるわけだ・・・
今度時間があったら自分でquickselectを実装してみたい。
第４問 Binomial Coefficients
nCrを最大化するnとrを与えられた配列xsから選択するという問題。
まず、任意のrで n1 > n2 なら n1 C r > n2 C rであることから、nはxsの最大値。
任意のnで、nCrを最大化するrはn/2に一番近いものだ。
そしてこの問題だとn > rである必要がある（nCn == nC0 == 1なのだが、この設問だと(n,0)がACの場合、(n, n)はWA）
_ = input() axs = list(map(int, input().split())) i = max(axs) j = min(axs, key=lambda j: abs((i/2) - j) + (i == j)) print('{} {}'.format(i, j))
Pythonのsort/max/minがオプションでkey関数をとるので、「xに一番近い」というのをminで表せる。ついでにi == jの時のペナルティもつけた。ペナルティが必要になるのはリストに最大要素と0しかない場合のみなので、「最大要素の場合１を足す」というペナルティだけで(n, n)になることを防げる。
感想
この回は基礎数学的な素養が試されている印象が強い。典型的なアルゴリズムやデータ構造らしきものを使うことなく、考察が済めばあとはちょっとソートしたりループしたりするだけで、一番アルゴリズムしていたのはB問題の二分探索だった。
頭の体操としては大変面白いのだが、ABC103のように一旦盲点に入ってしまうとアイデアの手がかりがあまりなく思考が空転してしまいそうな怖さがある。どうしたらこの分野を強化できるか（というか安定的に問題解決に向けて思考を重ねていけるか）、ちょっと考えないといけない。
