AtCoder Beginner Contest 100に参加してみた
初リアルタイム参加。言語はPython3。
「ABCって二週間おきにあるのかな？次は6/23か」とのほほんとしていたら
今日は記念すべき100回目のBeginner Contest、AtCoder Beginner Contest 100なので、ぜひぜひ参加してみてくださいな！
— chokudai(高橋 直大) (@chokudai) 2018年6月16日
Hello Worldが出力出来れば参加してみておっけーなレベルだよ！！！https://t.co/bCiCjMD2hT
こんなツイートが出ていて地味に驚く。
あと一週間あることを前提に過去問を最近のやつから順に解いていたのだが、最近出題されたものばっかり見てたということでなんとなく不利な気がしてしまう。（最近出題した問題と類似したものはすぐには出しにくいのでは？という考えから）
まあ仕方ないから当たって砕けろ、で初参加。
とりあえず３０分弱でミスなし全完で順位は86位。実力からすると完全にできすぎでビギナーズラック以外の何物でもない・・・
めでたく初回ランク上昇上限の400点をもらい茶色コーダーに。
第１問
ケーキを１６等分に切って、同じ人が隣り合わせのピースを取れないとして、二人が申告した数のピースを食べられるかどうかを判定する。
16等分と偶数で、ケーキをとる人数も２なので非常に楽。隣り合わせのピースはとれないのだから一人当たり最大で８しかとれず、お互いにとった数は干渉し合わない。
a, b = map(int, input().split()) print('Yay!' if a < 9 and b < 9 else ':(')
第２問
100でd={0, 1, 2}回割り切れる、小さい順でn個目の正の数字を出力する。
順位表見ているとけっこうつまづきポイントだったようだ。
from itertools import count, islice d, n = map(int, input().split()) gen = (i * (100**d) for i in count(1) if i % 100 != 0) print(next(islice(gen, n-1, n)))
このif i % 100 != 0の部分を見落とす人が多かったのだろうか。
next(islice(gen, n-1, n))はnth(gen, n)的なイディオム。ちょっとごちゃついていて好みではないが・・・
第３問
黒板に書いてある数字を全部「3するか/2するかのどちらかで、すべてを3することはできず、/2の結果は整数でなければいけない」という処理を何回行えるか。
n = int(input()) xs = [int(x) for x in input().split()] def div2(x): while x % 2 == 0: x /= 2 yield 1 print(sum(sum(div2(x)) for x in xs))
停止条件は2で割る数字がなくなった時。2と3が互いに素なので、*3の処理は無視できる。
なので各数字が何回2で割り切れるか、の和。
div2関数はもうちょっときれいに書けそう。
第４問
N個のケーキからM個選ぶ問題。各ケーキには三つの指標があって、各指標ごとの合計の絶対値の和を最大化させたい。
各指標の絶対値の合計でも、和の絶対値でもないのがポイント。
from itertools import product n, m = map(int, input().split()) xyzs = [[int(x) for x in input().split()] for _ in range(n)] multipliers = product((-1, 1), repeat=3) def max_sum(multiplier): sums = (sum(a*mul for a, mul in zip(xyz, multiplier)) for xyz in xyzs) top_m = sorted(sums, reverse=True)[:m] return sum(top_m) print(max(max_sum(multiplier) for multiplier in multipliers))
ただの合計の最大値を求める問題ならO(n log n)でn<=1000なので余裕で間に合う。
絶対値をとろうとする代わりに、各指標に+1か-1を掛け合わせて足したものの合計の最大値を8通り計算してその最大値をとればいい。
感想
AとB問題をやってるときが一番緊張した。初回は結果が良くてもレートに反映されにくいし、AとBさえノーミスだったらCとDはゆっくりでいいや、と考えていたせいだろう。なのでけっこういい精神状態でCとDに取り組めてラッキーだったように思う。
処理時間はCが最大で100ms弱、あとは20~30msくらい。やはりPythonでもABCだったらアルゴリズムが正しければ余裕で通る。そして標準ライブラリやiteratorプロトコルをうまく組み合わせるとけっこうきれいに、宣言的に記述できるように思う。
すごく楽しかった。次回もまた参加したい。
