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)と一致するからを調べている。…

aoj 0524 - Pizza

問題 問題概要 探索問題。2分探索で値の前後を求める。 解法 まず、storeに店の位置を入れる。この時、少しsample1を使って、考察してみる。本店の位置を0にしてしまうと、宅配先1からの距離は4-0=4で正確に求まるが、宅配先2からの距離は6-0=6で正確なもの…

aoj 0529 - Darts

問題 問題概要 探索問題。単純に全探索してしまうと、TLE。 解法 まず、単純に考える。全てのパターンを考えれば良いので、以下のコードのように単純に4つの矢が刺さるマスを全探索すればいい。 int main(void){ while(1){ int n, m; cin >> n >> m; if(n ==…

aoj 0569 - Illumination

問題 問題概要 場合分けが必要な6方向の幅優先探索。イルミネーションが必要なところが色塗りの感覚でわかる。 解法 まず、イルミネーションが必要なのは、外側のみであり、内側の部分は必要ない。よって、その外側の部分(周りが完全に囲まれている中の部分…

aoj 0525 - Osenbei

問題 問題概要 2次元にあるビット(0, 1)を任意の縦列、横列を選び任意の回数反転させることができる。最終的に最も0が多くなる時の0の数を求めよ。 解法 この問題には「R の上限 10 は C の上限 10000 に比べて小さいことに注意せよ」と書かれていて、解法…

aoj GRL_3 Connected Components - Strongly Connected Components

問題 問題概要 強連結成分分解する問題。 解法 強連結成分を分解するアルゴリズムとして、Kosarajuというものがある。今回はそれを使って、実装した。アルゴリズム自体は下のサイトを見てもらえれば、分かりやすい。 mathtrain.jp ミス アルゴリズム自体の理…

aoj 0528 - Common Sub-String

問題 問題概要 共通部分文字列の問題。ただし、連続した文字列でなければならない 解法 単純なdp。文字列s1とs2の両方を何文字目ま見ているかという要素を配列の要素と持つdpを考えればいい。 dp[i][j] = dp[s1のi文字目までで考える][s2のj文字目までで考え…

aoj 0611 - Silk Road

問題 問題概要 都市0から都市Nへ移動する。都市iから都市i+1にj日目に移動するとき,Di*Cj疲労度がたまる。都市0から都市Nまで移動した時の疲労度の最小を求めよ.ただしM日以内にNに到達しなければならない。 解法 都市iにいて,その時j日目の状態において…

aoj 0579 - Hot days

問題 問題概要 服を選んで、|Cx1 - Cx2| + |Cx2 - Cx3| + … + |Cxi-1 - Cxi| の最大値を求める問題。 解法 動的計画法で解ける。i日目までの服の選び方を決めたとき,i + 1日目以降について服を選んで目的の値を最大化する際には,1日目からi - 1日目までの…

aoj 2442 ConvexCut

問題 問題概要 与えられた図形が、点Pを通るどのような直線で切ったとしても、面積を2等分する点Pが存在するかどうかを求める問題。 解法 点対称のような図形になればいい。なんて言えばいいかわからないけど、角張った円のような。(重心関して点対称であれ…

aoj 2176 - For the Peace(要復習)

問題 問題概要 各国は世界平和を目指して、ミサイルを破棄。ただし、各国はミサイルを製造が古い順番に破棄していかなければならず、さらに、各国のミサイルの威力の合計値(軍事力)の最大値と最小値の差がd以下を常に保ちながら破棄していく必要がある。 解…

aoj 2383 - Rabbit Game Playing

AOJ

問題 問題概要 ゲームのステージがN個あり、そのステージすべてをクリアするためのステージの並べ方の場合の数を求め問題。ただし、(k個目のステージの難易度) >= (k-1個目のステージの難易度) - Tでだければならない。 解法 ステージの難易度を昇順にソート…

aoj 0567 - Best Pizza

問題 問題概要 条件に合う最もよいピザを選ぶ 解法 この問題は貪欲法で解ける。なぜなら、トッピングの値段がすべて同じだからである。トッピングの値段が同じであるなら、トッピングのカロリーが高いものから優先的に選んでいけばいい。あとは、何個のトッ…

aoj 0558 - Cheese

問題 問題概要 幅優先探索で最短経路を求める問題。ただしスタートとゴールがいくつもある。 解法 よくあるstartからgoalまでの最短経路を求める問題と同じ。ただし、その途中でチーズを小さい順に食べていかなければならない。そのため、(ciをチーズi番目…

aoj 0546 - Lining up the cards

問題 問題概要 与えられる文字列(数字)n個の中からk個選んで、つなげることで、できあがる文字列の種類を求める。 解法 next_permutationを使い、すべての順列を作る。その順列すべてに対して、前からk個選んで選んだ順番に文字列としてつなげる。そのように…

aoj 0534 - Chain

問題 問題概要 一列バージョンのぷよぷよみたいな感じ。好きな場所の色を一箇所変えることができ、それを行うことにより最も多くボールを消せる場合を求める問題。 解法 まずすべての玉の色を変えて全探索する。そして色を変えた前後で同じ色の数をカウント…

aoj 0526 - Boat Travel

問題 問題概要 連続したクエリの中に頂点とそれをつなぐ辺の長さのクエリと、2点間の最短距離を求めよというクエリが含まれる。 解法 任意の2点間の距離を求めるにはワーシャルフロイト法で求めることができる。ただし、最短経路を求めよというクエリに対し…

AOJ 0517 - Longest Steps

AOJ

問題 問題概要 数字の連続した長さの最大値を求める問題。ただし与えられたクエリの中に、0があれば好きな数字に変えることができる。 解法 まず、与えられた数字をバケツソートしておく。前から順番に数字を見ていき、連続成分の大きさで最大ものを探す。そ…

AOJ 2382 - King Slime

unionfind tree構造を用いる問題