mayoko’s diary

プロコンとかいろいろ。

AOJ

AOJ 2439 Hakone

AOJ

問題 Hakone | Aizu Online Judge 解法 まず, '-' があるところは順位が一意的に決まるので, 無視して良いです。与えられる文字列は 'U' と 'D' しか含まれないものとしましょう。そしたら dp します。問題では今の中継地点での i 位の人が, 前の中継地点で…

AOJ 2397 Three-way Branch

AOJ

問題 Three-way Branch | Aizu Online JudgeW*H のグリッドが与えられる。これらのうち, N 個のセルは通れなくなっている。あるセル(x, y) からは (x-1, y+1) or (x, y+1) or (x+1, y+1) にのみ行ける場合, (0, 0) から (W-1, H-1) までの経路は何通りあるか…

AOJ 2638 Hyperrectangle

AOJ

問題 Hyperrectangle | Aizu Online Judge 解法 まず, このページを見ると d 次元の立体における体積の求め方が分かります。各辺の長さが 1 の三角錐(?) の体積は 1/d! なんですね。 単体 (数学) - Wikipediaで, 後は包除原理です。例えば 各辺の長さが {2, …

AOJ 2538 Stack Maze

AOJ

問題 Stack Maze | Aizu Online JudgeH*W の迷路が与えられる。この迷路には小文字のアルファベットで表される宝石と, 大文字のアルファベットで表されるそれに対応する宝石を埋め込む穴がある(例えば 'a' とそれに対応する 'A' がある, という感じ)。あなた…

AOJ 2296 Quest of Merchant

AOJ

Merchant, かわいい(小並感) 問題 Quest of Merchant | Aizu Online Judge 解法 すごく複雑そうな問題に見えますが, 落ち着いて問題を分解すると一個一個は大したことありません。まず, 1 回の出張で訪れる町の集合がわかったら, その町の集合へ訪れる最短時…

AOJ 2168 Luigi's Tavern

AOJ

問題 Luigi's Tavern | Aizu Online JudgeH 人の勇者, W 人の戦士, C 人の僧侶, M 人の魔法使いがいる。以下の条件を満たすパーティは最大いくつ作れるか。 パーティには必ず勇者がいなければならない。 同じパーティの勇者と戦士は仲良くなければならない。…

AOJ 2305 Beautiful Currency

AOJ

問題 Beautiful Currency | Aizu Online Judge要素数 n の数列 a が beautiful であるとは, 1 以上 n-1 以下の任意の i について, a[i+1] % a[i] == 0 となることである。数列 a のいくつかの数を入れ替えて, a を beautiful にしたい。a[i] の値を b[i] に…

AOJ 2326 Number Sorting

AOJ

問題 Number Sorting | Aizu Online Judge 解法 dp[i] = (A+i 番目の数字から始まる数列の数) とします。B-A 例えば 792 という数字の次に来るものを考えると, 8**, 9** となるもの i.e. [800, 1000) 79* となるもの i.e. [793, 800) というように, 各桁を 1…

AOJ 1302 Twenty Questions

AOJ

問題 Twenty Questions | Aizu Online JudgeN 個の物体で構成された世界がある。これらすべては, M 種類の Yes/No で答えられる特徴で区別することができる。 あなたは, 今目の前にあるものがなんの物体であるかを調べたいのだが, 最悪の場合でもなるべく少…

AOJ 2333 My friends are small

AOJ

問題 My friends are small | Aizu Online Judge 解法 ある集合が有効かどうかを調べるときは, 「まだ選ばれていないやつの中で一番重さの小さい友達をリュックの中に入れることができないか」というのが判定基準になります。そこで, 配列 w をソートしたの…

AOJ 2222 Alien's Counting

AOJ

alien「ありえんよさみが深いw」— マヨ子@大天使クサハエル (@mayoko_) 2016年7月7日 問題 Alien's Counting | Aizu Online Judge宇宙人に N 本の指があり, この間に M 個の拘束条件が成り立っている。各拘束条件は, 「i 番目の指を曲げたら j 番目の指も自…

AOJ 2425 A Holiday of Miss Brute Force

AOJ

全探索お姉さんとアルゴリズムお姉さんはどっちが先だったんだろう? 問題 A Holiday of Miss Brute Force | Aizu Online Judge 解法 時間に関しては 6 で割ったあまりのみを考えれば良いです。そう考えると, d[t][x][y] = (時間 t に x, y にたどり着けるよ…

AOJ 2382 King Slime

AOJ

問題 King Slime | Aizu Online JudgeH*W のグリッド上に N 個の頂点がある。各頂点は, 上下左右いずれかの方向に移動でき, 移動する際は壁にぶつかるか別の頂点にぶつかるまで動き続ける。別の頂点にぶつかった場合, ぶつかった頂点同士は合体する。この移…

AOJ 2170 Marked Ancestor

AOJ

問題 Marked Ancestor | Aizu Online Judgeルートが頂点 0 の木が与えられる。頂点 0 の点は最初から黒く, それ以外の点は白い。これについて, 以下の二種類のクエリが投げられるので, 対応する。 頂点 v を選び, その点を黒く塗る。 頂点 v, もしくはその先…

AOJ 2182 Eleven Lover

AOJ

問題 Eleven Lover | Aizu Online Judge数字のみからなる文字列 s が与えられる。この中に, 連続した文字列でその表す数が 11 の倍数であるようなものは何通りあるか。ただし, 先頭が 0 であるような数は数とみなさないことにする。 解法 区間 [i, j] が 11 …

AOJ 1320 City Merger

AOJ

問題 City Merger | Aizu Online Judgen 個の文字列が与えられる(それぞれの文字は 20 字以下)。これら n 個を連続部分文字列として含む文字列を作りたい。この文字列の最小の長さはいくらか。 解法 bitDP します。dp[now][state] = (state にある文字列は作…

AOJ 2442 ConvexCut

AOJ

問題 ConvexCut | Aizu Online Judge 解法 答えがあるとしたら, それは重心以外ありえません。重心が答えになるとき, 図形は重心に関して点対称になっているはずです。素直にそれを実装しましょう。 typedef long double Real; Real eps = 1e-12; Real add(R…

AOJ 2157 Dial Lock

AOJ

問題 Dial Lock | Aizu Online Judgek 桁の数字が与えられる。もとの数 now から target という数を作りたいが, そのために以下の動作が許される。 動作: 区間 [s, t] および数 d を選び, その区間の数について, nxt = (prev+d)%10 とする。動作回数の最小の…

AOJ 2176 For The Peace

AOJ

for the peace という問題でキレてるの, 悲しみがある— マヨ子@大天使クサハエル (@mayoko_) 2016年6月27日 問題 For the Peace | Aizu Online Judgen 個の国がある。各国はいくつかのミサイルを持っているが, これを以下の条件を満たすようにすべて捨てたい…

AOJ 2383 Rabbit Game Playing

AOJ

問題 Rabbit Game Playing | Aizu Online Judge数列 D が与えられる。これに関して, 以下の条件を満たす並べ方は何通りあるか求めよ。 条件: 任意の i について, D[i] 解法 挿入DP というやつ?dp[i] = (i 番目までの並べ方の場合の数) というのが分かってい…

AOJ 2306 Rabbit Party

AOJ

問題 Rabbit Party | Aizu Online Judgen 匹のウサギがパーティーをする。各ウサギには友達度が定義されている(これが正の値を取るのは高々 m 個)。 ウサギ i がパーティーに参加した際の満足度は, パーティーに参加したウサギのうち, 友達度が最も低いもの…

AOJ 2249 Road Construction

AOJ

問題 Road Construction | Aizu Online Judge連結な無向グラフが与えられる。各辺には長さとコストが定義されている。このグラフを次の条件を満たすように変更したい。 各点 v の 0 からの距離(距離は辺の長さで定義される)が元のグラフと変わらない。 任意…

AOJ 1330 Never Wait for Weights

AOJ

問題 Never Wait for Weights | Aizu Online JudgeN 個の頂点があり, 各頂点には W[i] という特徴量がある。次の二つのクエリが与えられるので適切に処理せよ。 W[b] - W[a] = w という情報が与えられる。 a, b を与えるので, 今までの情報で W[b]-W[a] が求…

AOJ 1138 Traveling by Stagecoach

AOJ

問題 Traveling by Stagecoach | Aizu Online Judge 解法 bitDP 的なダイクストラやるだけ。 const int MAXN = 8; const int MAXP = 1000; const int MAXM = 33; const double INF = 1e18; int T[MAXN]; int dist[MAXM][MAXM]; double dp[MAXM][1<<MAXN]; int main() { int n, m, p, a, b; while (cin >> n >> m ></maxn];>…

AOJ 2224 Save your cats

AOJ

問題 Save your cats | Aizu Online JudgeN 頂点, M 辺の平面グラフが与えられる。平面グラフの面の数が 1 になるように辺を破壊したい。これを達成する最小コストを求めよ。 解法 下のスライドの前半を読めばすべてを察することができます。 平面グラフと交…

AOJ 2369 CatChecker

AOJ

最近のんびり過ごしています。 問題 CatChecker | Aizu Online Judge 解法 区間 dp をします。dp[l][r] = (区間 [l, r) が猫の鳴き声文字列になっているか?)というのを判定します。これは, s[l] = 'm', s[r-1] = 'w' s[m] = 'e' の時, dp[l+1][m-1], dp[m+1…

AOJ 2201 Immortal Jewels

AOJ

問題 Immortal Jewels | Aizu Online Judge 解法 ある最適な直線があったとします。この直線を少し動かしても結果は変わりません。結果が変わる直線の動かし方は, その直線が ある円の内部を貫くか, ある円の中心からの距離が Ri + Mi となるときです。なの…

AOJ 1295 Cubist Artwork

AOJ

問題 Cubist Artwork | Aizu Online Judge箱を並べる。これを前から見ると D 列のキューブが X1, X2, ..., XD 個並んでいるように見え, 横から見ると W 列のキューブが Y1, Y2, ..., YW 個並んでいるように見える。 これを満たすようなキューブの並べ方のう…

AOJ 2403 The Enemy of My Enemy is My Friend

AOJ

問題 The Enemy of My Enemy is My Friend | Aizu Online Judge 解法 半分全列挙しました。まず, N 頂点を半分ずつに分けて, dp[s] = (集合 s だけを使う場合の軍事力の最大値) を計算します。で, これらを合わせるときは, 前半の頂点と隣り合っていない頂点…

AOJ 2629 Manhattan

AOJ

問題 Manhattan | Aizu Online Judge 解法 一方の点 A は x 軸と平行な直線の上に乗せて考えても問題ありません。こうすると, もう一方の点 B の位置によって場合分けができます。B が y 軸と平行な直線の上に乗せられている場合 この場合は, A の位置をうま…