おはようございます。しほみんです。
競技プログラミング時間的余裕がないけど、この時間は考えられるから好きです。まあ成績は微妙ですが。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは1000程度になりました。緑中堅へ。
・C#でクラスとかつかってアプリケーションは作れます。
・pythonで自然言語処理勉強中....。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学ぶ。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在60回以上参加、2年目。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はABCD解けましたけど、Dでかなり行き詰りました。なんかよくわかってないし反省ですね。レートは1だけ上がったので921です。
Cはちょっと実装が重め、Dはちゃんと数学的に理詰めすべきでした。もったいない...
今回はA,B,C,D問題を解説します。
ここから問題です。問題は簡潔に書いています。
A問題
高橋君と青木君がゲームを行います。
高橋君がA個、青木君がB個アメを持っています。
お互い先行からアメを1個ずつ取ります。
C=0のとき高橋君が、C=1のとき青木君が先行です。
アメが取れなくなったら負けです。どっちが勝ちますか？
ちょっと複雑ですがif文で対処可能です。
・高橋君が先行のとき
高橋君が青木君よりアメが多くあれば高橋君の勝ちなので、
A>Bのとき高橋君、A<=Bのとき青木君になります。
・青木君が先行のとき
高橋君が青木君以上のアメがあれば高橋君の勝ちなので、
A>=Bのとき高橋君、A<Bのとき青木君になります。
Ａ問題としてちょっと厄介ですが、等号の処理とか結構勉強になると思います。
B問題
N種類の魔法を持っています。
それぞれAi秒詠唱にかかり、Biダメージが与えられます。
ただし、モンスターが強く、P秒以上の詠唱またはDより多いダメージでないと効果がありません。
効果がある魔法はありますか？
Nがそんなに多くないので、それぞれの条件を見ればよいです。
それぞれの魔法で、Ｐ秒未満かつ、Dより多いダメージを与えられるかどうか確認しましょう。もしどれかみたせば終わりです。
B問題最近はfor文を核問題が多い気がしますね...
C問題
1,2,...,Nの番号が付いたN個の皿と
1,2,...,Mの番号が付いたM個の条件があります。
条件iはそれぞれAiとBiの番号の皿にボールが乗っているときに満たします。
K人います。
それぞれの人はCiかDiの番号の皿にボールを置けます。
K人のおき方のうち満たす条件数が最大のときの条件数を出力してください。
まず、K人のおき方は2のK乗です。
ということで、Kは最大16乗なので、約65000通りです。
よって、ビット全探索で調べて、お皿に乗っている状態を見つけ、
このあと条件を幾つ満たすか確認します。
最後に、もし条件数が最大なら更新すればよいです。
ビット全探索問題ですが、実装事態がちょっと重めです。
メモ化でうまくお皿のボール状態を残しながら考えていきましょう。
D問題
整数からなる公差1の等差数列の和がNになるのは、何通りですか？
単純にまずNは10の12乗なので、o(√N)までは計算できます。
なので、なんとなく2つの積が分かればなんか解けるなって思えば十分です。
本当は約数の関係とかあるけど....面倒なので....。
そこで、中心の数と、項の数を考えます。
すると（中心の数）×（項の数）= Nです。
なので、（中心の数）と（項の数）の偶奇を考えます。
・（偶数）×（偶数）のとき
中心の数としては偶奇は関係ないです。
ただし、項の数として偶数とすると、中心の数は必ず奇数です。
（例えば1,2,3,4のときは項数4で、中心2.5です。）
なので、これは成り立ちません。
・（奇数）×（偶数）のとき
中心の数が奇数であれば、項の数の偶奇関係なく成り立ちます。
よって1つは必ずあります。
また、中心の数が偶数のとき、項の数が奇数個なら必ず成り立ちます。
よって、もう一つあります。
よって、この場合は2通りあり得ます。
・（奇数）×（奇数）のとき
中心の数が奇数であれば、項の数の偶奇関係なく成り立ちます。
よって1つは必ずあります。
また、中心の数が奇数のとき、2で割ると必ず〇.5になります。
そして、項の数に2をかけると項の数は偶数です。
よって、中心が（奇数）/2で、項の数が2×（奇数）の数列ができます。
これは、最初の（偶数）×（偶数）のようになりたつので1つあります。
よって、2通りです。
以上がすべてのケースでまとめると、
片一方が奇数である2つの積の個数を2倍したものが答えになります。
なので、1からSQRT(N)までで、2つの積に分かれるもののうち、
片一方が奇数なら2つ、両方奇数なら4つ、奇数の平方数なら2つみたいに足していけばよいです。
ここら辺をきちんとまとめるのに時間食いすぎた...反省。
最後に....
D問題はちょっと厄介でした。ただ、もっと等差数列の関係さえ理解していればすぐ出せたので明らかに勉強不足ですね。よく考えないとハマります。
ぼちぼち復活してきたので1000まずは取り戻します。
ではでは。
