AOJ
問題 問題概要 スタートからゴールまで最短距離で移動したい. 影を通れば距離には加算されない. (2017 ICPC国内模擬 E) 解法 建物とその影を考えて多角形を作り, N個の多角形どうしの距離を計算して辺を作り, ダイクストラで最短距離を計算すれば良い. 建物…
問題 問題概要 グラフがあたえられる. 各頂点のいくつかはガソリンステーションでガソリンを入れることができる. ガソリンがなくならずに, スタートからゴールに行くまでの最短距離を求める. またLPGのタンクの最大容量もあたえられる. 車の燃費は10km/Lであ…
問題 問題概要 五芒星が与えられる. スタートの星からゴールの星までの移動の最小距離を求める. 星の中は移動距離に入らない. 解法 星と星の距離は, 各星は5つの辺からなっていることから, 5つの辺ぞれぞれを総当りで調べて, その中の最小値が距離になる. こ…
問題 問題概要 ボールが通る線分とそれをじゃまするN個の直方体が与えられる. 直方体に重ならずに線分をスタートからゴールまで通ることができるボールの半径の最大値を求める. 解法 長方形と線分の距離をdとして求める半径をrとすると, d <= hのとき, r = d…
問題 問題概要 頂点を(-100,-100)、(100,-100)、(100,100)、(-100,100) とする正方形とn個の線分が与えられる. 線分の両端は正方形の辺上にある. 線分により正方形がいくつに分割されるかを求めよ. 解法 順番に線分を書いていくことを考える. いま書く線分と…
問題 問題概要 長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける. 分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合…
問題 問題概要 W,D,Lの命令が与えられる。Wは書き込む数字とサイズ、Dは削除する数字、Rは読み込む場所を標示するという命令。書き込むは前から貪欲に、開いている部分にサイズ分書き込むこと。 解法 Wできる区間(空き区間)をprioroty_queueで保持することに…
問題 問題概要 数式を計算する。 解法 参考サイト とてもわかりやすい。 構文解析 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>…
問題 問題概要 盤面に命令が書いてある。命令通りに行動すればコストは0。命令以外の行動をすれば、コストは指定された通りのコストがかかる。スタートからゴールまで行くのにかかる最短コストを求めよ。 解法 拡張ダイクストラで解いた。頂点の状態に番号だ…
問題 問題概要 スタートからゴールまで冷凍されたものを溶かさずにもっていけるかを求める問題。冷凍されたものは最大でm時間保存することができ、時間がたつと解ける。与えらた条件にある頂点で氷を冷凍することができる。溶かさずにゴールまで行く最短時間…
問題 問題概要 Aliceから順に相手の欠点を選ぶ。次にボブは選ばれた欠点と関係あるAliceの欠点を選ぶ。これを続けていき、選べなくなったら負け。 解法 2部マッチングかなて感じはするが、どちらが勝つのかという判定をどうすればいいかわからなかった。 感…
問題 問題概要 青と赤のカードがある。青と赤のカードを選び、その2つの数が1より大きい約数を持つなら取ることができる。一度取った数字は次から選ぶことができない。何組のカードが取れるか。 解法 ペアの個数はペアを作る組によって変わってくる。約数を…
問題 問題概要 省略 解法 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>…
問題 問題概要 省略 解法 最小費用流 ミス 蟻本のやつを写経した。 コード #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>…
問題 問題概要 省略 解法 最大フロー確認問題。 ミス 蟻本のやつを写経したけど、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>…
問題 問題概要 LとRをK回2分探索をして、最終的な答えが、T-E < h' < T + Eに入る確率を求める問題。確率Pで誤った2分探索をして、確率(1-P)で適切な2分探索をする。 解法 全探索で、やろうと思うと、2k(k=30)でTLE?? ただし、2分探索をしていく途中で、 (T …
問題 問題概要 連結成分の数. 解法 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>…
問題 問題概要 スタートからゴールまでたどり着けるか。 解法 dfsで、スタートからゴールまでdfsでたどり着けるかやった。usedを使い、一度巡ったところをdfsしないようにしないと、オーバーフローで落ちた。 ミス なんか始めバグってた。でもなんか治った。…
問題 問題概要 nこの数字を使って、合計sにするパターンの総数 解法 dfsで周り4方向と連結した部分を塗りつぶしていく。連結成分を塗り終わると、dfsが終わる。次に、まだ塗り終わっていない場所からdfsを始めて、塗りつぶしていく。これを何回繰り返したか…
問題 問題概要 nこの数字を使って、合計sにするパターンの総数 解法 dfsで解いた。dfs(n, s, now) = (n := 残りの選択する数字の数 s := 残りの合計 now := 現在選択可能な数字) を要素として持ち、再帰関数を書けばいい。 ミス 教育的 コード #include <iostream> #in</iostream>…
問題 問題概要 与えられた数字を2つに分けて、共に、数字が昇順になるようにできるか。 解法 dfsで解いた。dfs(B, C, cnt) := (B:=Bの一番上の数 C:=Cの一番上の数 cnt:=何個目の数字か)を要素として持ち、再帰関数を書けばいい。 ミス シンプルなdfs コード…
問題 問題概要 お菓子に1ミリずつ切り目があり、切れ目ごとに切るためのコストが異なる。コストを最小にして、お菓子を半分ずつに分ける方法は。 解法 dpでとく。 dp[i][j][k] := (お菓子の長さがiでAさんの文がjの時で次ににkさんがお菓子をもらう時の切断…
問題 問題概要 複数のスタート場所があり、地点までの最短距離を求める。 解法 まず、ダイクストラを利用して、店から他の地点までの最短距離を入れる。このときの店というのは複数ある場合があるので、一番近い店からの距離を求めなければならない。最短距…
問題 問題概要 省略。 解法 動的計画法でやった。 dp[y座標][x座標][1つ飛ばしジャンプの回数] := (y, xに行くまでの最小の危険度)というdpを考えた。y座標が常に大きくなるので、DAGと考えるので、このようなやり方でやった。また、うまいやり方が思いつか…
問題 問題概要 試合結果が渡されて、順位がどのように決まるかを求める問題。 解法 まず、試合結果がわからないものは無視して、与えられた試合結果のみを使い、トポロジカルソートをする。aチームが勝ち、bチームが負けた場合、b -> aのような形で辺を貼る…
問題 問題概要 高校数学で出てくる場合の数の問題。 解法 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)へ行く方…
問題 問題概要 与えられたグラフに対して、幅優先探索を使い、条件を満たした新たなグラフを表す隣接行列を作り、ダイクストラで最小コストを作る。 解法 与えられたグラフのままでは、多くの条件あり、そのままではダイクストラをすることができない。そこ…
問題 問題概要 省略 解法 今回の問題は毎回すべての城を調べていたら、TLEになってしまう。そこで、ポイントは、「n回目の波で崩れる城はn - 1回目の波で崩れた城の周囲8方向の城に限られる」ということである。そこで、まずは、城が存在する座標をq1に入れ…
問題 問題概要 文字列bの連続した文字列が文字列aの部分文字列(連続していなくてもよい文字列)で作れる時の、最長の長さを調べる。 解法 連続文字列の先頭の文字を決め(b[i])、その文字が文字列aを先頭から見ていき、存在するかを調べ、文字存在するなら(a[k…
問題 問題概要 該当する文字列がいくつ存在するか求める問題。 解法 与えれた文字列(s)にIOIOI等の文字列があるかを調べる。sの先頭から調べていき、Iの文字であれば、その位置から、2*n + 1文字を切り取り、該当する文字(ans)と一致するからを調べている。…