情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

AtCoder Beginner Contest 100

AtCoder Beginner Contest 100の解説です。
ABC100 旧版:
abc100.contest.atcoder.jp
ABC100 beta:
https://beta.atcoder.jp/contests/abc100/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 100
rated 1200
6/16(土) 21:00 ～ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分

方針

全完

A - Happy Birthday!

入出力例2を見れば分かるように、16切れのパイから隣合う2個を取らないような取り方では8個ずつが限界です。
逆に、それより少なく取る時は単に幾つかを取らないようにすればいいだけです。
よって、AとBが両方とも8以下ならば無事に取ることができます。
今回の出力形式はいつもと違うので、ちゃんとサンプルと照らし合わせてね

B - Ringo's Favorite Numbers

まず、N < 100の時、100で丁度D回割り切れる数はN \cdot 100^D = N \cdot 10^{2D}です。
これはNの後に0が2D個くっついた個数になります。
なお、N = 100の時はこのままだと割り切れる数が1個増えるので、答えが(N + 1) \cdot 10^{2D}になることに注意してください。

C - *3 or /2

まず、整数を3倍しても整数なので基本的には3倍していれば操作は終わりません。
ですから、操作が終わる時はどの数を2で割っても整数でなくなる時、すなわちすべてが奇数の時です。
また、ある数を3倍しても2で割れる回数が増えたりはしない(2と3は互いに素)ので、操作回数の最大は各数について2で割れる回数の総和に等しいです。
後は、各数について何回2で割れるかを計算すれば、O(\sum_{i=1}^N \log a_i)で求められますね。

D - Patisserie ABC

まず入力が-10000000000 \leq x_i, y_i, z_i \leq 10000000000なので64bit整数を使いましょう。
さて、絶対値の問題は高校数学でもやっているようにまず場合分けします。
ここでは全て正の場合について考えてみましょうか。
この時、ケーキは綺麗さ+おいしさ+人気度が高い順にM個選ぶのが最適になります。
逆に、例えば綺麗さのみ負の場合は、-綺麗さ+おいしさ+人気度が高い順にM個選ぶのが最適です。
よって、全場合分け8通りについてそれぞれ導出し、その中で最も高い値を選べば良いことが分かります。
計算量はO(N \log N + M)なので無事に求めることができました。

結果

oooo 4完(1000点) 47:13(2WA)
205位

感想

なんか最初、すっごくジャッジが詰まっていたのでWA確認ができないのがつらかったです。
今回は発想力だけで乗り切れる問題が多く、初心者向けなコンテストでしたね。
ただ、逆に罠が多い(A問題の出力形式、B問題のN=100、C問題のシミュレーション殺しと思考の誘導(コラッツの定理かと思った)、D問題のオーバーフロー)ので、初心者向けなのに競プロを始めたばかりの人をWAで苦しめるというイメージでした。
今回これらの罠に引っかかった人は、これから気をつけるようにしましょう！そこの筆者とかな！