AtCoder Beginner Contest 034 - アルゴリズマーの備忘録

全完だけど、時間かけすぎた…特にC問題。

テストを2回受けた。2回目の成績が良くなっているなら"Better"、悪くなっているなら"Worse"を出力せよ。

if文でも3項演算子でも何でも使ってください。

10^9人のグループが1番と2番、3番と4番、5番と6番…とペアを作っていく時、n番の人のペアの相手の番号を出力せよ。

これもAと同じで、奇数ならn+1、偶数ならn-1を出力すればOKです。

横Wx縦Hのグリッドの(1,1)から(W,H)へ、上下左右に移動して行く最短ルートは何通りか、1,000,000,007で割ったあまり求めよ。

よくあるDPだと間に合いません。

数学的に解くと、右へw-1回、上へh-1回移動します。→がw-1個、↑がh-1個ある時、→と↑の組み合わせの総数が答えの通り数となるので、(w+h-2)C(w-1)となります。あとはこれを求めればいいです。

分母の方は(w+h-2)×(w+h-3)×...×hをmodを取りながら掛け算していけばOKです。

しかし、分母は掛け算を行うときにmodを取ってしまうので、割り算がそのままでは出来ません。今回は1,000,000,007が素数なので、フェルマーの小定理を使って(w-1)!の逆元を求めます。予め(w-1)!をmodを取りながら計算しておいてください。

フェルマーの小定理はa,mが互いに素の時、a^(m-1)≡1(mod m)が成立する、というものです。これを変形し、a*a^(m-2)≡1(mod m)。

a^(m-2)は1/aと同じ役割をしています。と、こんな感じで、(w-1)!^(mod-2)を求めて、分母にかけてあげれば答えが出ます。

累乗を行う際は、繰り返し2乗法を用いてください。a^23=a*a^2*a^4*a^16というやつです。比較的理解しやすいので分からなかったら検索してください（説明下手）

N個のビーカーにpi%の食塩水がwiグラム入っている。K個のビーカーの食塩水全てを混ぜた時、得られる食塩水の濃度の最大値を求めよ。

何かヒントに2分探索と書いてありますね…さっぱり分からないです。ということで貪欲で解きました。

まず、食塩水を混ぜることがどういうことか、ということから。

食塩水iとjを混ぜるとき、得られる食塩水の濃度は $\frac{pi\cdot wi + pj\cdot wj}{wi+wj}$ です。

これは、数直線にpi、pjを取った時、pi〜pj間をwj:wiに内分した点です。

この事を考えると、1つずつ選んでは追加し、ということを繰り返してK個のビーカーを混ぜるとすると、初めの方のビーカーの影響が大きそうで、後半になるとあまり点が動かなくなりそうです（実際はあまり関係ないです）。

となると、前半に可能な限り濃度を高くしておけば低くならずに済みそうです。

ということで、各ビーカーを現時点でのものに追加したあとの濃度を求め、それが最大になるものを追加。ということをK回繰り返すと、答えが得られます。

2回以上同じものは使用できないので、1度使ったらリストから削除しておきましょう。

C問題はwとhを−1し忘れるし、D問題ではpとwを逆に扱っていたのに気づくのが遅くなるしで災難でした。

Pythonはまだ習得中なので、適当に上げたりしています。JavaはEclipse立ち上げるの面倒くさい（使用しているPCの性能があまり良くないです。）