ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ

AOJ 1327 : One-Dimensional Cellular Automaton

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1327N個のセルからなるセルオートマトンS(i, t)があり、以下の更新則を持つ。S(i, t + 1) = (A × S(i − 1, t) + B × S(i, t) + C × S(i + 1, t)) mod M初期状態S(i, 0)が与え…

AOJ 0092 Square Searching

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092最大の正方形の辺の長さを求める問題。解法 動的計画法で解くことができる。配列には dp[i][j] := (i, j)を正方形の右下としたときの最大の正方形の辺の長さ を持たせて…

AOJ 2321 Butterfly

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2321女性がいろんな男性とデートしたいというお話。解法 動的計画法で解くことができる。時間は6~22時なのでデートをする時間を (1 DPのテーブルは、dp[i 人目まで見た][予定…

AOJ 0596 Taxis

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596解法 ダイクストラ法で解くことができる。訪問済みのコスト情報については、 minCost[今いる町][現在乗っているタクシーで残り何回移動できるか] の最小値を持たせる。町…

AOJ 0595 Schedule

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0595解法 動的計画法で解くことができる。配列には、 dp[i][j] := i日目にj人いる(Jはビットで管理)ときの場合の数 を持たせておく。鍵を持っている人は必ず次の日も来なけれ…

AOJ 1516 Nasty Boys

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1516解法 i文字目からi+1文字目に移動できるかを調べていけばよい。(0 ソースコード #include <iostream> #include <string> #include <vector> using namespace std; const string key = "ABCDEFGHI"; </vector></string></iostream>…

AOJ 2443 ReverseSort

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2443解法 両側探索で解く事ができます。(通常のBFSではTLEになります)両面探索とは、スタートとゴールと両方の側から探索していき合流点を探す探索方法のことをいいます。N…

AOJ 1325 Ginkgo Numbers

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1325 解法 この問題ではガウス整数を扱っていることが分かります。 http://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E6%95%B4%E6%95%B0#.E3.82.AC.E3.82.A6.E3.82…

AOJ 1246 Concert Hall Scheduling

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1246 解法 動的計画法、または最小費用流で解くことができます。動的計画法で解く場合、 dp[1つ目の部屋の日にち][2つ目の部屋の日にち]=収益の最大 で解くことができます…

AOJ 1512 Smartphone Game

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1512某パズルとドラゴンのゲームみたいなやつ 解法 全状態数は、25 * 4 ^ 5 なので全通り試してやればよいです。 ブロックが消える処理でバグを発生させないように実装できる…

AOJ 2380 Bubble Puzzle

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2380 解法 幅優先探索で解くことができます。キューにはボタンを押した回数とフィールドの状態を持たせます。 風船の破裂、水滴の移動にもキューを用いて処理してやります。 …

AOJ 1507 Dungeon (II)

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1507 解法 クラスカル法っぽいやり方で解くことができます。UnionFindには自分が属するグループの要素数を持たせておくことで和を計算させることができるようになります。Uni…

AOJ 0099 Surf Smelt Fishing Contest II

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0099 解法 priority_queueをうまく使うと簡単に解くことができます。priority_queueは値を降順でソートさせてくれるので、 参加者番号にマイナスをかけてあげることで昇順も…

AOJ 2320 Infinity Maze

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2320 解法 Lの値がとても大きいので普通に探索をするのは不可能です。しかし 1 更にこの問題では行き止まりに達して動けなくなるということがないので、どこかしらで同じ場所…

AOJ 2165 Strange String Manipulation

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2165 解法 やるだけ問題です。全通り試してやればよいです。 しかしエントロピーの最小値計算の比較は誤差を考慮しないとWAになってしまうので注意が必要です。 ソースコード…

AOJ 2070 First Experience

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=20701から9999までしか値を持つことができない電卓を作る問題です。 ただし四則演算の優先順位はありません。 解法 ちょびっと構文解析&やるだけ問題です。上の概要にも書き…

AOJ 2058 Moduic Squares

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2058 解法 やるだけ問題です。入力で0が与えられた部分にはまだ使われていない番号を入れ、 縦・横・斜めの数の和を計算し、そのmodを取った値が全て一致するかどうかをみて…

AOJ 1316 The Sorcerer's Donut

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1316解法 やるだけ問題です。全ての文字に対して8方向に進めていき、その過程で生成できる文字列を全てsetに入れてやればよいです。 ソースコード #include <iostream> #include <string> #inc</string></iostream>…

AOJ 1315 Gift from the Goddess of Programming

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1315教会があります。 女神が教会にいる間にお祈りをしている一般人の中で一番時間の長いものを出力する問題です。 解法 シミュレーション問題です。時間に関するシミュレー…

AOJ 0541 Walk

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0541 解法 動的計画法(DP)で解くことができます。どのようにDPするか分からなかったのでこちらを見ました。 http://www.ioi-jp.org/それぞれのマスを何回通るかが分かるとn…

AOJ 2119 Finding the Top RPS Player

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2119以下のルールに従って、n人でジャンケンを繰り返し、誰かがm回連続で勝つまでにかかる試行回数を求める問題です。〇ルール ・k連続勝利してる人で2人ペアを作りじゃ…

AOJ 2249 Road Construction

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2249ある王国には、1つの都市と複数の町が存在します。 それらの町と町、都市と町をつなぐ道路を作りたいと考えています。 道路は距離dでそれを作るコストがcです。以下の…

AOJ 2284 The Legendary Sword

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2284 解法 幅優先探索(BFS)で解くことができます。入力の処理が若干面倒ですがそこは頑張りましょう。 キューの中には、現在地の座標・コスト・次に目指すべき番号を持たせま…

AOJ 2013 Osaki

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=20132013年一発目! 解法 いもす法で解くことができます。いもす法についてはこちら http://imoz.jp/algorithms/imos_method.html ソースコード #include <iostream> #include <string> #includ</string></iostream>…

AOJ 1056 Ben Toh

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1056&lang=jp 解法 動的計画法(DP)で解くことができます。int dp[何日目か][弁当を何連続でゲットしたか] = その確率 のような配列を用意しました。誤差が緩いので適当な回数…

AOJ 2182 Eleven Lover

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=218280000桁以下の数字(文字列)が与えられます。 その中で11の倍数である部分文字列の個数を求める問題です。 解法 動的計画法(DP)で求めることができます。int dp[(左から見…

AOJ 2207 Consistet Unit System

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2207 解法 ワーシャルフロイド法で解くことができます。この問題では単位の関係が云々といっていますが、これはグラフに落として考えることができます。 (例)1 km = 10^3 m …

AOJ 2253 Brave Force Story

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2253 解法 幅優先探索(BFS)で解くことができます。この問題でひとつ注意しないといけないことがあります。 問題文には「いずれの座標も絶対値が30以下である」と書いています…

AOJ 1503 Number

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1503 解法 この問題は全く解法が思いつかなかったので、nanikakaさんやその他の記事を参考にしました。感謝です。どうやら記事によると、 「(n + 1)! + 2, (n + 1)! + 3, (n …

AOJ 1502 War

AOJ

概要 問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1502 解法 4方向に渦巻くように進めていけばよいです。 ソースコード import java.util.*; public class Main{ void run(){ Scanner sc = new Scanner(System.in); int n = …