問題 1,2,5,10,20,50,100,200のコインが無数にある。 このコインを使って、200を作る組み合わせは何通りあるか。 考え方 dp[i]:=iを作る組み合わせのかず とすると、小さいコインから順番に、コインpを使うと、 dp[i+p] += dp[i] とできる。(dp[0]=1として、…

問題 各桁を5乗した数の和が、もとの数値と同じになる数の総和を求める。 考え方 実際に試す。 9^5 * 6=354294なので、6ケタ以下のものしかないはずなので、10^7ぐらい探す。

問題 2 考え方 多倍長を実装して、文字列とかで扱って、setなどでカウント。

問題 n*nの配列があり(nは奇数)、中心かららせん状になるように1,2,3,...と数字を埋めていく。 n=1001のとき、対角線上にある数字の合計値を求める。 考え方 実際に、らせん状に数字を配置して、対角線の数値を合計する。

問題 abs(a)素数となるような最大のa,bについてa*bを返す。 考え方 素数かどうかを判定できるようにしておき(篩とかで)、 実際にシミュレーションする。

問題 d 考え方 割り算の筆算のように計算すると、小数部分の数列が得られる。 2重ループで、2点s,eを選んでsからeとeからe+(e-s)までを確認して循環節になっている部分で最小のものを見つける。 e-s+1が最大のものを見つければよい。

問題 2つの過剰数で表せない正の整数の総和を求める。 考え方 約数関数を使って、28123までの過剰数をすべて列挙する。 2重ループ回して2つの過剰数の和であらわせる数をすべて調べる。 表せなかった数値をすべて足す。

問題 3 7 4 2 4 6 8 5 9 3 のような数字のピラミッドが与えられる。 このとき、一番上からスタートし、下に向かって左右のどちらかの数値を選びながら下っていく。 一番下まで来たとき、通ったルートの合計値を最大にするようなルートの値を求める。 上の例…

問題 数字を英語に直したときの文字数を考える。(1ならoneなので3文字) 1から1000までその文字数を合計したものを答える。 考え方 http://www.ctb.ne.jp/~piyoshi/newpage144.html など参照してルールを実装する。andがつく場合や20、40などに注意する。

問題 ぴったりXの距離だけジャンプできるカエルがいる。 数直線上を原点からスタートして、距離D以上になるまでジャンプを繰り返す。 間に、L[i]からR[i]までの幅の穴がいくつか空いている。(L[i],R[i]の端点は穴に落ちない) 穴に落ちないようにする場合、最…

問題 グリッドのマスに数字が書いてあり、一番小さい数字と一番大きい数字の差が1になるようにしたい。 1回の操作で、どれかのマスの数字に1足すか1減らすことができる。 最低何回の操作で実現できるか？ 考え方 全探索する。ある数値を決め打ちし、 ・それ…

問題 N本のブロックのタワーがあり、0からN-1の番号が振られており、それぞれの高さheightsが与えられる。 このタワーを横一列に並べる。 このとき、あるタワーが倒れても横のタワーが倒れないように、2つのタワー間の距離は、その2つのタワーの高いほうの高…

問題 要素が0または1のH*Wの配列が与えられる。 配列の周りを罫線で囲んだものを考える時、左上の部分から右下の部分まで最短距離で結んだ線を引き、その線の下側になるすべての要素の0と1を反転することができる。このとき、すべての要素を0にするために必…

問題 整数値の配列aが与えられる。 配列x[0..N-1]が 1=2*x[i] を満たす場合、convexである、という。 与えられた配列aに対し、次の操作ができる。 ・iを一つ選び、そのa[i]を1引く 配列がconvexになるまでにかかる最小の操作回数を求める。 考え方 要素が10^…

問題 毎晩、毛の色を変えられるオオカミがいる。 色はN色あって、便宜上0〜N-1の番号で扱う。 colorMapという2次元配列が与えられる。 もし色iから色jに変えることができればY、そうでなければNが書かれている。 色は、変化させられる最小の番号の色に変わる…

問題 碁石ののった19路盤が与えられる。 その状態が五目並べとして正常であるか判定する。 異常な状態とは、 ・どちらかのプレイヤーが勝利条件をみたしているのに、もう片方のプレイヤーがさらに碁石をおいている ・お互いが置いた個数がありえない のどち…

問題 高橋君はLメートル先に亀を見つけた。 高橋君はva m/sで進むことができ、亀もvb m/sで高橋君の逆方向へ逃げる。 移動する前に毎回亀のいる位置を確認し、そこまで進むのを「1回」と数える。 1回の移動後、再び亀のいる位置を確認し、同様に進む。 N回繰…

問題 曜日が与えられるので、週末(土日)までの日数を返す。 考え方 各曜日について週末までの日数は一意に決まるので、それを書く。 文字列の2文字目までを確認すれば判別できる。

問題 1*1*1〜1*1*kのレゴブロックが無数にある。 土台が1*1*wのところに重ねていき、高さをhにしたい(土台は高さに含めない)。 条件として、ブロックを重ねるとき、重ねるブロックからはみ出ないようにする必要がある。 そのような重ね方の組み合わせは全部…

問題 ロボットがあり、「right X」「left X」「forward X」「backward X」の命令がいくつか与えられる。 rightとleftの時はXに角度、forwardとbackwardの時はXに距離が与えられる。backwardは向いている向きに対して(向きを変えずに)反対方向へ移動する。命…

順番に解いていくと、難しいところで詰まって進めなくなりそうな気がしたので、とりあえずSRM500までは正解率の高いものから埋めていこうと思って、調べた。 Editorialからdiv1Mediumだけ抽出。正解者数/全体の人数をOverallSuccessRateとして、それで降順ソ…

蟻本(全部の問題解く)*3周 1周目：とりあえず見てもいいから解く 2周目：できるだけ見ずに解く 3周目：何も見ずに解く(ライブラリも貼り付けなし) 過去問 Topcoder：SRM500以降のdiv1mediumを解いていく、終わったらSRM400〜 OJ AOJ：500番台を埋める SPOJ：…