問題リンク Pi is Three 概要 実数Rが与えられる。"整数/整数"の形で、円周率πとの誤差がR以下となるような最小の分母とその分子を求めよ。条件を満たす分子が複数ある場合はより誤差の小さいものを答えよ。 0 解法 分母Dと分子Nをそれぞれ1とし、1ステップ…

問題リンク Country Road 解法 発電機を置く座標を考える必要は全くありません。その発電機によって電力が供給される家の範囲を考えます。1台のとき、1〜Nの家全てをカバーするので電線の長さはx_N-x_1です。発電機がもう1台あったとき、x_1 〜 x_k と x_k+1…

問題リンク Battle Town 解法 シミュレート問題です。コマンド毎にマップを更新していきます。 現在位置と向きを覚えて実装していきます。 ソース

問題リンク Rummy 解法 サイズが小さいので、大きさ3のグループを3つ作るやり方を全通り試します。 全てのグループについてセットの条件を満たすかを調べます。 ソース

問題リンク Perfect Number 解法 1つのNあたり、O(√N)で判定できます。 i を1〜√Nの範囲だけ回し、Nを割り切るものを見つけたらそれは約数で、同時にN/iも約数です。 同じ数を重複して加算しないように注意が必要です。 ソース

問題リンク Saizo 解法 そのまま実装するだけです。 ソース

問題リンク Rock Man 概要 N種類のアイテムを全て作りたい。アイテム i を作るにはそれぞれ、day1_iの日数がかかる。アイテム i を作るとき、ある別のアイテムを既に作っていると作業が効率的になるのでday2_iで済むようになる。 全てのアイテムを作るのにか…

問題リンク Hyper Rock-Scissors-Paper 概要 15個の手があるじゃんけんをN人でやる。その中の勝つ手を答えよ。あいこで終わる場合はDrawとせよ。 N 解法 勝敗関係の図をみると、反時計回りに番号を付け、x番の手で勝てるものはx+1〜x+7の手だとわかるのでfor…

問題リンク Ruins 概要 2つの正整数A, Bが与えられる。ここで、a1*a2=A, b1*b2=Bとなるような正整数a1, a2, b1, b2を考える。このとき、a1, a2, b1, b2を昇順にソートし、隣り合った数の差の2乗の総和Sの最小値を求めよ。 1 解法 1〜10000の約数をそれぞれ最…

問題リンク Blackjack 概要 ブラックジャックの得点を計算せよ。 ブラックジャックは手持ちのカードの点数の合計が得点になる。ただし21点を超えるようなものはbustと呼び、失格となる。 カードの数字は2〜9, T, J, Q, K, Aと表す。 2〜9はそれぞれ2〜9点。T…

問題リンク Princess, a Cryptanalyst 解法 2段階を踏んで解きました。 最初は、SSSの長さを求める部分。最後にSSSの文字列を求める部分です。 SSSの長さは dp[S][last]: 採用した文字列の集合S,最後がlastのときの最小の長さ のDPで求めることができます。A…

問題リンク Princess in Danger 解法 基本的には(都市、血液の残り時間)をノードにしたダイクストラです。が、このままだとTLEになります。 工夫1. 評価関数を導入します。「(都市、時間)の値」+「(都市-ゴール)間の最短距離」が小さい順に頂点を訪問します…

問題リンク Princess's Japanese 解法 自分は、色んな定義が組み合わさってごっちゃになる実装問題は、多少コードが長くなっても、行っている意味をはっきりさせるタイプの人です。 入力文字列を拍に分解します(decomp())。 分解したら、[無声子音]+'a'|'o'…

問題リンク Princess's Marriage 解法 襲われる可能性が高い順に道をソートし、お金の許す限り護衛してもらえば全体の襲われる回数の期待値を下げることができます。 ソース

問題リンク Princess's Gamble 解法 (100*投票券の全体枚数)*控除率/当選投票券の枚数 が答えです。当選した券がないときは0となります。 ソース

問題リンク Square Route 解法 道路の数は各方向それぞれ1500、そして幅の最大は1000なので、最大の正方形でも1辺の長さは高々1500000です。 それぞれの方向に対して、作ることができる1辺の長さとその個数をカウントします。 カウントし終えたら、同じ長さ…

問題リンク Surrounding Area 解法 杭の打たれていないマス(i, j)について、そのマスからWに辿りつけるか、Bに辿りつけるかを調べます。Wに辿りつけるが、Bには辿りつけない場合、そのマスは白の領域です。黒についても同様です。これを全ての空きマスに対し…

問題リンク Space Coconut Grab 解法 Z[x]: xが3乗の値かどうか z[x]: v^3 = xとなるような値 v の配列を作っておきます。 後は、xとyを共に0〜1000000まで回してx+y^2+z^3 = eとなるかを調べます。 表向きは(10^6)^2の計算量となりますが、実際には枝刈りが…

問題リンク Gather the Maps! 解法 DPです。 dp[i][j]: i番目の人の手にj日目までに集めることができる地図の最大の集合 とします。地図には0〜n-1番号がついているものとし、集合はその番号の桁のbitを立てることで、整数で表すものとします。 dp[i][j]の漸…

問題リンク The Last Door 解法 e[i][j]: 三角形iを光らせたときの光が三角形jに当たるか否か という表を作ってから、最小何回で全体を光らせるかの処理に入ります。 e[i][j]を作るところから説明します。 3点の中で、三角形の頂点となる点を調べます。これ…

問題リンク Sergeant Rian 解法 DPチックに解きました。が、例によって解いてから時間が経っているので詳細まで覚えておりませぬ・・・。 1の島を根とする木を作ります。木のノードに、「そこから出発し、その木より下の橋を全て爆破してなお且つ戻ってくる…

問題リンク Aizu Buried Treasure 解法 DP+メモ化探索です。 mem[i][j][k]: 段Hにおいて訪れたマスの集合i, 残りの酸素kという状態でマスjに訪れたときの最小コスト というDPを最下層の段から作って行きます。 H段目のmemを埋めるには1つしたのH+1段目のmem…

問題リンク Book Arrangement 解法 マイナス10進数を下の桁から順に求める方針で解きます。 残念なことに、これを解いたのは結構前でソースが何をしてるんだかあまり思い出せません、なので記憶の片隅にあるアイデアだけ述べさせてください。 ある桁kで作る…

問題リンク Life Game 解法 DPです。 dp[i][j]: 所持金 i を持ってマス j へ到着する確率 という表をjが小さい方から埋めることで解けます。これは、ゲーム中、後ろのマスへ下がることがないから可能です。 初期値はdp[初期所持金][0] = 1.0となります。 ま…

問題リンク Dangerous Bridge 解法 イベント処理で解きました。体重wの人物が「橋に乗る」「橋からいなくなる」というイベントを時間でソートしてシミュレートします。同時刻のものがあったら、「橋からいなくなる」イベントが先に来るように順序をつけます…

問題リンク Ninja Climbing 解法 忍者の位置による幅優先探索です。コストは移動距離ではなく、ジャンプした回数です。 ビルの状態によって色々場合分けが必要なので、注意深く実装する必要がある厄介な問題だと思います。 ソース

問題リンク Big Hit ! 解法 揃った絵柄とボーナスの通りにメダルの枚数を計算するだけです。 ソース

問題リンク Seven Segments 解法 0〜9を"0""1"で表現しておきます。ある数xからyへ変更するには、それらの間で0と1が反転しているビットの所に1を立てればいいです。 ソース

問題リンク Thanksgiving 解法 野菜を値段でソートします。合計額をなるべく小さくしたいので、値段の高い野菜を割引の対象にしたいことになります。これは、袋に値段の高い順に貪欲に突っ込んでいくことで、高い野菜を割引対象にすることができます。 ソース

問題リンク Hit and Blow 解法 数えるだけです。 ソース