2011-11-20から1日間の記事一覧
問題リンク The Squares 解法 シミュレーションです。1ステップにつき、人がどう動くかは一意に決まるのでステップごとに適切にマップを書き変えていく方針で解けると思います。 これを解いたのが昔過ぎてソースを見ても何をしてるのかよくわからn(ry ソース
問題リンク Scene in a Picture 解法 M*Mの画像を回転させて4つのパターンを求めておき、N*Nの中で一致する個所があるかを探します。 M*M*N*N*4の計算量オーダとなりますが、どうやら間に合ってしまうようです。 ソース
問題リンク Room Numbers of a Hospital 解法 4と6が使えないので新部屋番号は[0, 1, 2, 3, 4, 5, 6, 7]を[0, 1, 2, 3, 5, 7, 8, 9]のように表す8進数として考えることができます。 与えられたnが15のとき、1*8^1 + 7*8^0となるので、8進数だと17となります…
問題リンク Block 解法 幅優先探索です。 スタートの色と同じ色のみを辿ってゴール地点にたどり着けるかを調べます。 ただし、与えられるスタート地点にブロックが無い場合があるようなので注意です。 ソース
問題リンク Next Trip 解法 やるだけ問題だと思います。 ソース
問題リンク Rock, Paper, Scissors 解法 やるだけ問題です。 出ている手の種類が1か3なら必ずあいことなります。 2種類なら、どちらの手を出しているかで勝ち負けが判定できます。 ソース
問題リンク UFO Shooting Down Operation 解法 幾何+シミュレーション問題です。 まず、準備立てとして次のものを求めておきます。 1. ufoの位置(x, y) 2. 1分毎のufoの移動量ベクトル 3. 原点からの距離 自分のソースの場合、1はufo[i][0]とufo[i][1]にそれ…
問題リンク A New Plan of Aizu Ski Resort 解法 典型的なDP問題です。 dp[i][j]: マス(i, j)に来た時の滑り方のパターン数 とすることで解けます。dp[i][j]はdp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]の3つの値が求まっていれば求められるので、iが大きい方(…
問題リンク At Boss's Expense 解法 N個の料理の値段の和で表せる かつ 素数 かつ 予算以下という数字を見つければいいです。 予算の大きさの配列を用意し、値段xを料理の値段の和で表せるならばxのところにtrueを入れていくことで解けます。 ソース
問題リンク Wrought Gold Master 解法 アイテムiを手に入れるための最小費用は「(材料リストにあれば)値段」「各レシピの最小入手費用の和」のうち安い方です。これをメモ化再帰などで求めます。Runtime Errorが起きやすい理由として、作ろうとしているアイ…
問題リンク Traveling Alone: One-way Ticket of Youth 解法 時間について、金額について、2点間の最小コストが欲しいので、それぞれについてワーシャル・フロイド法を適用します。 ソース
問題リンク City Merger 概要 N個の都市の名前が与えられる。全ての都市の名前を部分列に含み、かつ長さが最小となる文字列を答えよ。 N 都市名の長さ 解法 巡回セールスマン問題になります。 dp[S][i]: 訪れた都市の集合S、最後に訪れた都市の番号iのときの…
問題リンク The Sorcerer's Donut 概要 H*Wに文字が並んでいる。ある文字からはじめて、周囲8方向へ向きを決めて読み続けることができる。表の外へはみ出すとき、上辺へはみ出すならば下の辺へ、右辺へはみ出すならば左辺へ、というように読み続ける。 magic…
問題リンク Gift from the Goddess of Programming 概要 ログイン・ログアウトのログ記録がN個ある。ログ記録には「日 時間 IorO ID」が記録されている。Iはログイン、Oはログアウトを表す。神様のIDは"000"である。このとき、神様と一緒にログインしていた…