問題リンク 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]の漸…

問題リンク Poor Mail Forwarding 解法 シミュレーション問題です。 郵便局iから宛先jの手紙を出すときの転送先の郵便局は常に同じなので、前計算してしまいましょう。 e[i][j]でi->jの最短経路。ワーシャルフロイドで求めます。 adj[i][j]でi->jの直接転送…

問題リンク Dragon Fantasy 解法 全探索＋枝刈りです。訪れた状態と最後に訪れた場所の対をノードにした幅優先だと、状態数が2^N*Nになってメモリが足りません。 探索の枝刈りの条件として、未訪問の場所のうち、1つでも訪れることができなくなった場所があ…

問題リンク Make Purse Light 解法 店員がお釣りを返す部分は貪欲法で硬貨の枚数を計算できます。 硬貨の種類が4枚で各々高々20枚までしかないので、20^4通りの支払い方を試しました。 ソース

問題リンク Keitai Message 解法 文字の表を作ってしまえば勝ちです。 ソース

問題リンク Water Pipe Construction 解法 全点間の最短距離をワーシャルフロイドで求めます。 次に基地kを選び、wf[s][k]+wf[k][g1]+wf[k][g2]が最小となるkを探します。このkはs, g1, g2になっても何ら構わないです。 ソース

問題リンク Data Center on Fire 解法 エレベータのシミュレーション問題です。 まずはエレベータクラスの説明をします。 エレベータは[エレベータの識別ID, 容量, 停止時間, 現在のデバイス量, *状態*, 目標階, 現在位置の高さ, 速さ]のメンバを持ちます。 …

問題リンク Railroad Conflict 解法 新路線と既存路線の交点を全て求め、新路線のどちらか片側の端点に近くなる順番でソートします。新路線のその端点から、交点を辿っていって出口の数をカウントします。端点は地上と地下どちらでもよいので、一番最初の交…

問題リンク X-Ray Screening System 解法 r[i][4]: i番目の品物が出現した座標の範囲 を作りました。以降、品物iが長方形の形をしているかどうかの判定はこの範囲内のみを調べればよいことになります。 品物は最大で7個、なので品物の上下関係を7!通り試しま…

問題リンク Amida, the City of Miracle 解法 あみだくじのシミュレーションです。 r[h][p]: 縦棒pにいるときに高さhに差し掛かった時の移動先の棒 というデータ構造を作り、hを上から下まで動かしました。 ソース

問題リンク Misterious Gems 解法 20*20の座標をロボットを1歩ずつ動かしてシミュレーションします。 得られた宝石の数を調べてYES, NOの判定をします。 ソース