問題リンク Water Tank 解法 実装問題です。 ある仕切りの場所に水を量V流していき、溢れた水の量V'を隣へ流すという処理を再帰的にします。水が溢れ、水位が隣と同じになったら以降その2つは同じ水槽として扱う、など面倒な処理が多いです。 気合いで乗り切…

問題リンク Circle and Points 解法 この問題、実は AOJ0090 Overlaps of Sealsとやりたいことは全く一緒です。なのでこちらを参照してください。平面を4つに区切って行き、解がよさそうなところを探していく最良優先探索で解けます。 ソース

問題リンク Unit Fraction Partition 解法 全探索＋枝刈り問題です。 求めたい値がp/qで有理数となるのですが、浮動小数点で扱うと結構厄介なので分数の形で扱った方がいいと思います。 a/bとp/qが等しいかどうかはa*q = b*pが成立するのと同値なので、結局…

問題リンク Red and Black 解法 深さ優先探索、幅優先探索、なんでもいいと思います。 とてもシンプルな探索問題だと思います。 ソース

問題リンク Hanafuda Shuffle 解法 シミュレート問題です。シャッフルを頑張って実装します。 ただ、最終的な山の一番上のカードさえ分かればいいので、シャッフルの手順を逆順に追って、一番上のカードがどこから来ているかを調べる方法があります。こちら…

問題リンク Square Carpets 概要 W*Hのグリッドにタイルがあり、汚れているものと汚れていないものがある。全ての汚れているタイルを正方形のカーペットで覆って隠すとき、必要なカーペットの最小個数を求めよ。ただし、カーペットは汚れていないタイルを覆…

問題リンク Power Calculus 概要 x^nを求めるための最小乗除回数を答えよ。最初x^1から始まり、計算の途中で表れたx^kを使ってx^iから、x^(i+k)もしくはx^(i-k)を得ることができる。 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"である。このとき、神様と一緒にログインしていた…

問題リンク Byakko Delivery Company 解法 交差点とその進入方向をノードにしたダイクストラ法が基本方針です。辺のコストは移動時間です。 ただし、(交差点、進入方向)だけではこの問題は解けないです。なぜなら、その交差点に最短で辿りつく場合が常に解の…

問題リンク Towns along a Highway 概要 N個の町が直線状に並んでいる。町iと町jの距離の上半分行列に登場する値が降順で与えられる。この行列の値に従って町を配置できるときの隣り合う町の距離を答えよ。配置方法が複数通りある場合、距離の辞書式順序で出…

問題リンク Balloon Collecting 概要 1つの家と1つの車とN個の落ちてくる風船がある。車はX軸上のみを移動する。 風船は場所xに時間tに地面に落ちる。この時間tに車がその場所にいれば風船を取ることができる。しかし、一度に乗せられる風船の数は3つまでで…

問題リンク Membership Management 概要 N個の「グループとそのメンバーリスト」が与えられる。メンバーリストに載っているのは人物の名前だけでなく、別のグループの名前が書かれていることもある。このとき、入力の一番最初のグループに所属している人物は…

気合 11月12日〜11月14日に行われたICPCアジア地区予選福岡大会に明治大学のチーム「MINTIA」として出場してきました。 ICPCに出場できる権利があるのは今回までということでかなり気合を入れていきました。 うちの大学からは過去数回アジア地区予選まで進出…

問題リンク Swimming Jam 概要 2レーンからなるプールがあり、それぞれ一方通行で往路と復路である。N人の水泳者がいて常にそれぞれ決められたスピードで泳ぐ。レーン内で人を抜く泳ぎ方は禁止されている。レーンに入るときに同時に入る人が複数いた場合、飛…

問題リンク Repeated Substitution with Sed 概要 N個の文字列のペア(αi, βi)と、文字列γ、δが与えられる。N個のペアの置換を行ってγからδを得るための最小ステップ数を答えよ。δが得られない場合は-1とせよ。ここで1ステップは次のように定義される。 ペア(…

問題リンク Cubist Artwork 概要 1*1*1の立方体を積んでアートを作る。作ろうとするアートを正面から見たシルエットと側面から見たシルエットが与えられる。このシルエットの形になるようなアートを作るために必要な立方体の最小個数を答えよ。 正面から見た…

問題リンク Bug Hunt 概要 簡単なプログラム言語の構造がBNFで与えられる。このプログラムは配列の宣言文と代入文のみで構成される。 配列はアルファベット1文字の名前がついており、宣言の時に配列の大きさが指定される。配列内の初期値は未定義値である。 …