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

競プロが絶不調の中、「下手すると全完出来ないかも」と思いながらやってました。（コンテスト中は寝ていたので、終了後から解き始め、無事に1時間で全完出来ましたが）今回はA〜CをPython2、DをC++で解いてます。

現在時刻とコンテスト開始までの時間が与えられます（ただし両方共「時」のみで「分」はなし）。
コンテスト開始は何時か求めなさい。

基本は足すだけ。24時間表記なので、24で割ったあまりを出力しましょう。

生徒N人の座標とチェックポイントM個の座標が与えられます。各生徒について、一番近い（マンハッタン距離）チェックポイントを求めて下さい。

N,M≦50と小さいので、各生徒が各チェックポイントに行く際の距離を全部求めることが出来ます。各生徒について、どのチェックポイントが一番近いか、距離を全部比較すればOKです。計算量はO(NM)。

N=A×Bを満たす整数A,Bのうち、桁数の大きい方の桁数の最小値を求めよ。

N≦10^10がポイント。ということは、A≦BとするとA≦10^5である事が確定します。
Aさえ決まればB=N/Aで与えられるので、Aを1〜√Nの範囲のNの約数全てで調べ、Bの桁数の最小値(これはAが最大の時）を求めればOKです。計算量はO(√N)。

自分はAを1から増やしていきましたが、√Nから減らしていって、最初にNがAで割り切れる数にAがなったらそこでループを止めても問題ありません。

N個の商品からA個以上B個以下の商品を選び、その価値の平均値を最大化しなさい。また、その最大値を取る選び方が何通りあるか求めなさい。

N≦50という特殊そうな制限から、最初は「半列挙かな…」と思いました。

しかし、実際に半列挙でコードを書くと、「同じ個数選んだ選び方はその中で最大値以外は使わない」とすぐ気付き、DPへの解法へと移ります。

DP[i][j]:i番目までの商品を使って、j個の商品を選んだ時の価値の和の最大値

を使うと、DP[i][j]=max(DP[i-1][j],DP[i-1][j-1]+v[i-1])で更新が可能です。（ここでは貰うDPで書いていますが、自分のコードはあげるDPになっています）

これを使い、今度はDP[n][i]/i（A≦i≦B）の最大値が求める最大値です。

次に何通りあるか。DPテーブルを埋める際に、もう1つ配列を使って情報を増やします。

DP2[i][j]:DP[i][j]となる選び方は何通りあるか

これはDP[i-1][j]!=DP[i-1][j-1]+v[i]なら片方からのみ値を引き継ぎ（DP2[i][j]=DP2[i-1][j]またはDP2[i-1][j-1]）、等しいならその両方の和を持ちます。ここは個人的にあげるDPにすると分かりやすいです。

DP2のテーブルもDPと同時に埋め、先ほど求めた最大値と一致する数を足していけばOKです。O(N^2)。

無事に全完出来てよかった。と言いたいところだけど、最後で400点なので、やはり余裕でないといけない。そろそろ1000点をAC出来る出来ないの境界に戻りたい…