htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Beginner Contest 100

B - Ringo's Favorite Numbers

Submission #2676172 - AtCoder Beginner Contest 100

N=100のケースだけ注意。200点のくせに問題文斜め読みしてたら足引っ掛けそうな罠が。

C - *3 or /2

Submission #2677755 - AtCoder Beginner Contest 100

ある数を3倍するか2で割るかというのは、素因数分解したときに3の指数を1増やすか(あれば)2の指数を1減らすかということなので、3倍しても2で割れる回数に影響しない。で回数を最大化するためには当然1ターンあたり一つの数のみ2で割るようにすればいいので、結局全部の数に対して何回2で割れるか試せばいい。

何回2で割れるかはどうせ高々log n回のループなので工夫する必要はないんだけど、bin(n)で二進数表記を取って最初に1が現れるまでに何個0が出たかとか数えたりする手もある?逆に遅くなるか。

D - Patisserie ABC

コンテスト中にアホなことして延々とWA叩いてた……。
WA→Submission #2683278 - AtCoder Beginner Contest 100
それぞれ符号をプラスとマイナスにして8通り試せばいいってとこまではたどり着いたんだけど、ただソートして上からM個取ればいいだけなのをわざわざdp組んでしまい、さらにdpの初期値を全部0にしてdp全体のmaxを結果としたために、M個取らない合計値が採用されてWAが出てたっぽい。M個選ばなきゃならないので、dp[0]以外は-infかなんかで初期化しなきゃならないしreturnするのもdp[-1]だけだしif subtotal < 0: continueもしちゃだめ。

dpでAC→Submission #2691785 - AtCoder Beginner Contest 100
そもそもソートして上位M個取るだけでいい→Submission #2691763 - AtCoder Beginner Contest 100

うーん始めて1年以上なるのに未だに400点が解けたり解けなかったりで成長しないなあ……。結局精進が足りないのだろうけど。追い越していく人をへこたれない程度に見習いつつ地道にやっていきます。