srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

AOJ

aoj 2827 凸多角形柱工業都市

問題 問題概要 スタートからゴールまで最短距離で移動したい. 影を通れば距離には加算されない. (2017 ICPC国内模擬 E) 解法 建物とその影を考えて多角形を作り, N個の多角形どうしの距離を計算して辺を作り, ダイクストラで最短距離を計算すれば良い. 建物…

aoj 1318 Long Distance Taxi

問題 問題概要 グラフがあたえられる. 各頂点のいくつかはガソリンステーションでガソリンを入れることができる. ガソリンがなくならずに, スタートからゴールに行くまでの最短距離を求める. またLPGのタンクの最大容量もあたえられる. 車の燃費は10km/Lであ…

aoj 2402 Milky Way

問題 問題概要 五芒星が与えられる. スタートの星からゴールの星までの移動の最小距離を求める. 星の中は移動距離に入らない. 解法 星と星の距離は, 各星は5つの辺からなっていることから, 5つの辺ぞれぞれを総当りで調べて, その中の最小値が距離になる. こ…

aoj 1157 Roll-A-Big-Ball

問題 問題概要 ボールが通る線分とそれをじゃまするN個の直方体が与えられる. 直方体に重ならずに線分をスタートからゴールまで通ることができるボールの半径の最大値を求める. 解法 長方形と線分の距離をdとして求める半径をrとすると, d <= hのとき, r = d…

aoj 2009 Area Separation

問題 問題概要 頂点を(-100,-100)、(100,-100)、(100,100)、(-100,100) とする正方形とn個の線分が与えられる. 線分の両端は正方形の辺上にある. 線分により正方形がいくつに分割されるかを求めよ. 解法 順番に線分を書いていくことを考える. いま書く線分と…

aoj 1176 Planning Rolling Blackouts

問題 問題概要 長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける. 分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合…

aoj 2152 Restrictive Filesystem

問題 問題概要 W,D,Lの命令が与えられる。Wは書き込む数字とサイズ、Dは削除する数字、Rは読み込む場所を標示するという命令。書き込むは前から貪欲に、開いている部分にサイズ分書き込むこと。 解法 Wできる区間(空き区間)をprioroty_queueで保持することに…

aoj 0109 Smart Calculator

問題 問題概要 数式を計算する。 解法 参考サイト とてもわかりやすい。 構文解析 Howto · GitHub ミス しっかりとした構文解析は初めて。 コード #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cctype> #include <cstdio> using namespace std; typedef long long ll;</cstdio></cctype></algorithm></vector></string></iostream>…

aoj 1156 - Twirling Robot

問題 問題概要 盤面に命令が書いてある。命令通りに行動すればコストは0。命令以外の行動をすれば、コストは指定された通りのコストがかかる。スタートからゴールまで行くのにかかる最短コストを求めよ。 解法 拡張ダイクストラで解いた。頂点の状態に番号だ…

aoj 2021 - Princess in Danger

問題 問題概要 スタートからゴールまで冷凍されたものを溶かさずにもっていけるかを求める問題。冷凍されたものは最大でm時間保存することができ、時間がたつと解ける。与えらた条件にある頂点で氷を冷凍することができる。溶かさずにゴールまで行く最短時間…

aoj 2480 - Blame Game

問題 問題概要 Aliceから順に相手の欠点を選ぶ。次にボブは選ばれた欠点と関係あるAliceの欠点を選ぶ。これを続けていき、選べなくなったら負け。 解法 2部マッチングかなて感じはするが、どちらが勝つのかという判定をどうすればいいかわからなかった。 感…

aoj 1163 - Cards

問題 問題概要 青と赤のカードがある。青と赤のカードを選び、その2つの数が1より大きい約数を持つなら取ることができる。一度取った数字は次から選ぶことができない。何組のカードが取れるか。 解法 ペアの個数はペアを作る組によって変わってくる。約数を…

aoj GRL_7 A Matching - Bipartite Matching

問題 問題概要 省略 解法 2部マッチングの確認問題 ミス 蟻本のやつを写経した。 コード #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; co</algorithm></cstring></vector></cstdio></iostream>…

aoj GRL_6 B Network Flow - Minimum Cost Flow

問題 問題概要 省略 解法 最小費用流 ミス 蟻本のやつを写経した。 コード #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e9; struct edge { i</algorithm></cstring></vector></cstdio></iostream>…

aoj GRL_6 A Network Flow - Maximum Flow

問題 問題概要 省略 解法 最大フロー確認問題。 ミス 蟻本のやつを写経したけど、c++11だと通らないなー。 コード #include <iostream> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++)</algorithm></cstring></vector></cstdio></iostream>…

aoj 2301 - Sleeping Time

問題 問題概要 LとRをK回2分探索をして、最終的な答えが、T-E < h' < T + Eに入る確率を求める問題。確率Pで誤った2分探索をして、確率(1-P)で適切な2分探索をする。 解法 全探索で、やろうと思うと、2k(k=30)でTLE?? ただし、2分探索をしていく途中で、 (T …

aoj 0118 - Property Distribution

問題 問題概要 連結成分の数. 解法 dfsで連結成分の数を求めればいい. ミス なし. コード #include <iostream> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int dy[] = {1, 0, 0, -1}; int dx[] = {0, 1, -1, 0}; bool used[</iostream>…

aoj 0207 - Block

問題 問題概要 スタートからゴールまでたどり着けるか。 解法 dfsで、スタートからゴールまでdfsでたどり着けるかやった。usedを使い、一度巡ったところをdfsしないようにしないと、オーバーフローで落ちた。 ミス なんか始めバグってた。でもなんか治った。…

aoj 0067 - The Number of Island

問題 問題概要 nこの数字を使って、合計sにするパターンの総数 解法 dfsで周り4方向と連結した部分を塗りつぶしていく。連結成分を塗り終わると、dfsが終わる。次に、まだ塗り終わっていない場所からdfsを始めて、塗りつぶしていく。これを何回繰り返したか…

aoj 0030 - Sum of Integers

問題 問題概要 nこの数字を使って、合計sにするパターンの総数 解法 dfsで解いた。dfs(n, s, now) = (n := 残りの選択する数字の数 s := 残りの合計 now := 現在選択可能な数字) を要素として持ち、再帰関数を書けばいい。 ミス 教育的 コード #include <iostream> #in</iostream>…

aoj 0033 - Ball

問題 問題概要 与えられた数字を2つに分けて、共に、数字が昇順になるようにできるか。 解法 dfsで解いた。dfs(B, C, cnt) := (B:=Bの一番上の数 C:=Cの一番上の数 cnt:=何個目の数字か)を要素として持ち、再帰関数を書けばいい。 ミス シンプルなdfs コード…

aoj 0550 - Dividing Snacks

問題 問題概要 お菓子に1ミリずつ切り目があり、切れ目ごとに切るためのコストが異なる。コストを最小にして、お菓子を半分ずつに分ける方法は。 解法 dpでとく。 dp[i][j][k] := (お菓子の長さがiでAさんの文がjの時で次ににkさんがお菓子をもらう時の切断…

aoj 0562 - Shopping in JOI Kingdom

問題 問題概要 複数のスタート場所があり、地点までの最短距離を求める。 解法 まず、ダイクストラを利用して、店から他の地点までの最短距離を入れる。このときの店というのは複数ある場合があるので、一番近い店からの距離を求めなければならない。最短距…

aoj 0530 - Pyon-Pyon River Crossing

問題 問題概要 省略。 解法 動的計画法でやった。 dp[y座標][x座標][1つ飛ばしジャンプの回数] := (y, xに行くまでの最小の危険度)というdpを考えた。y座標が常に大きくなるので、DAGと考えるので、このようなやり方でやった。また、うまいやり方が思いつか…

aoj 0519 - Worst Reporter

問題 問題概要 試合結果が渡されて、順位がどのように決まるかを求める問題。 解法 まず、試合結果がわからないものは無視して、与えられた試合結果のみを使い、トポロジカルソートをする。aチームが勝ち、bチームが負けた場合、b -> aのような形で辺を貼る…

aoj 0515 - School Road

問題 問題概要 高校数学で出てくる場合の数の問題。 解法 dpで解きました。(x,y)=(0,0)への行き方を1通りとして、(1,0)は(0,0)からの1通り、(0,1)は(0,0)からの1通りの方法で行くことができ、(1,1)は(0,1)と(1,0)から行く方法があり、(0,1)と(1,0)へ行く方…

aoj 0596 - Taxis

問題 問題概要 与えられたグラフに対して、幅優先探索を使い、条件を満たした新たなグラフを表す隣接行列を作り、ダイクストラで最小コストを作る。 解法 与えられたグラフのままでは、多くの条件あり、そのままではダイクストラをすることができない。そこ…

aoj 0612 - Sandcastle

問題 問題概要 省略 解法 今回の問題は毎回すべての城を調べていたら、TLEになってしまう。そこで、ポイントは、「n回目の波で崩れる城はn - 1回目の波で崩れた城の周囲8方向の城に限られる」ということである。そこで、まずは、城が存在する座標をq1に入れ…

aoj 0572 - Card Game is Fun

問題 問題概要 文字列bの連続した文字列が文字列aの部分文字列(連続していなくてもよい文字列)で作れる時の、最長の長さを調べる。 解法 連続文字列の先頭の文字を決め(b[i])、その文字が文字列aを先頭から見ていき、存在するかを調べ、文字存在するなら(a[k…

aoj 0538 - IOIOI

問題 問題概要 該当する文字列がいくつ存在するか求める問題。 解法 与えれた文字列(s)にIOIOI等の文字列があるかを調べる。sの先頭から調べていき、Iの文字であれば、その位置から、2*n + 1文字を切り取り、該当する文字(ans)と一致するからを調べている。…