ABC100 参加記録
AtCoder Beginner Contest 100 - AtCoder
記念すべき100回目のABC!おめでとうございます! 次は目指せABC200。
ということでおめでたい回なのですが、私の成績は全完37分台で144位。うーん…2WAが痛いです。
平方数賞ですね(そんなものはない)
振り返っていきます。
A - Happy Birthday!
A問題からちょっと頭を使う内容。
入力例2の図が分かりやすいですが、1人が取る個数が8個までなら1個飛ばしで取ることができます。逆に9個取ってしまうと、必ずどこかが隣り合ってしまいます。
そのため両方の個数が8以下なら Yay!
、そうでなければ :(
が答えです。
ACコード:Submission #2675152 - AtCoder Beginner Contest 100
素直に YES
NO
にしない問題が多いのは、今回のライターさん(通称「双子」さん)の特徴ですね。楽しいですが、タイプミスが少し心配になります。問題文からコピペするのが吉。
B - Ringo's Favorite Numbers
2WA出しました…ひどい:(
パッと見て問題文がよく分からなかったのですが、サンプルの記載を見るとイメージが掴めます。
- 100でちょうど「0」回割り切れる正整数:1, 2, 3, 4, ...
- 100でちょうど「1」回割り切れる正整数:100, 200, 300, 400, ...
- 100でちょうど「2」回割り切れる正整数:10000, 20000, 30000, 40000, ...
そのため、 が答えになりそうです…が、 の時は100で割り切れる回数が増えてしまうので飛ばさなくてはいけません。
これを0WAで通してる人、すごい。
ACコード:Submission #2680984 - AtCoder Beginner Contest 100
C - *3 or /2
問題文が少し回りくどく書かれていますが、「全ての に対して3倍することはできず、操作後の の値は整数でなければならない」ということは、全ての値が2で割れなくなったら終了です。
また、「3倍する」という操作は、「2で割れるかどうか」に影響しないので考慮する必要がありません。これは3が2と互いに素だから言えることです。
というわけで、問題を単純化します。
- 2で割れる数を1つ以上選び、2で割る。
- 全ての数が2で割れなくなったら終了する。
「1つ以上」と書きましたが、操作回数を最大にしたいので、1つずつ選んでいくのが最善です。ということで、与えられた の「2で割れる回数」の総和を出力すれば答えになります。
計算量は、入力 の最大値を として 。 なので通ります。
ACコード:Submission #2676571 - AtCoder Beginner Contest 100
D - Patisserie ABC
の組 個から 個選び、 のそれぞれの「総和の絶対値」の和を最大化する問題。…数式で書いたほうが誤解がなくていいですね。
さてどう考えるかですが…絶対値というのは元の数に対して、+1倍、-1倍のどちらかになります。これは当たり前のことに見えますが、「2通りしかない」というのが大きな手がかりになります。
求めたい値には絶対値が3つ含まれているので、これを8パターンに場合分けすることができます。書き下すと以下の8つです。
これを全部計算すれば答えが出ます。 全探索、「間に合う時には」シンプルで強力な解法です。
各符号を決めてしまえば、 それぞれに符号を掛けて和を取ったものを 個計算し、ソートして大きい方から足していけばいいです。
計算量は です(8も一応書きました)。 なので全く問題ありません。
ACコード:Submission #2678544 - AtCoder Beginner Contest 100
おわりに
A, Bと少しクセのある問題でした。Dはとても良い問題だったと思います。
ABCオンリーが続いていますが、来週はついにARCが予定されています!頑張りましょう!