問題 問題概要 x軸上をスタートからゴールまで到達するのにかかる最短時間を求める問題。ただし、時間ごとに、動けるx軸上の位置が与えられる。 解法 ループが存在するわけでなく、ただ単にx軸上を動くだけなので、実験すると貪欲にやればいいことがわかる。…

問題 問題概要 省略 解法 bfsで解いた。進める方向は、進もうとするマスと、現在のマスと過去のマスの3つが門松列をなしているとき。注意しなければならないのは、基本的な最短経路問題で使うbfsのように、座標のみを状態として最短距離をメモしていくと、解…

問題 問題概要 省略 解法 がんばって実装しよう。 ミス なし。 コード #include <iostream> #include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) int n, m; int main(void){ cin >> n >> m;</algorithm></vector></set></cstdio></iostream>…

問題 問題概要 相似比を求める問題 解法 Aの座標に対して行われた操作は平行移動と回転なので、AとBは相似である。よって、相似比を求めれば、よいことなる。どこを見て相似比をみるかは多くの解法があるみたい。 一番簡単なのは、重心からの距離が最大の点…

問題 問題概要 省略 解法 ダイクストラでやろうと思うと、閉路の最短距離を出すのは普通にやったらできない。求めるのは0から初めて、0に戻るような閉路で最短距離。そのような経路は、0 -> u -> v -> 0 ものである。同じ道を２度通ることはできないので、u…

問題 問題概要 省略 解法 bfsで解いた。よくある最短距離を求めるときにやる、bfsは一度、到達したところは2回目以降むしをするが、今回は、初めて到達したあとも、その位置に最短距離として、ほかの経路から到達して来る可能性があるので、bfsで初めに到達…

問題 問題概要 省略 解法 2分探索and最短経路問題。 xを小さくしていけば、かならず、ゴールにたどり着け、無限に大きくしていけば、どこかで、たどり着けなくなる。このような場合、求めるxを2分探索で効率よく絞り込んでいける。あとは、そのxに対して、ダ…

問題 問題概要 木の直径を求める問題。 解法 木の直径を求めるアルゴリズムは、 1.任意の頂点sから最も遠い頂点をxを求める 2.頂点xから、最も遠い頂点yを求める 3.頂点xからyの距離が木の直径となる これを実装すればいい。 ミス なし。 コード #include <iostream> #</iostream>…

問題 問題概要 省略 解法 2倍したものは同じものとしてみなせるため、まずすべての数字を2で割れるだけ割る。そのあと、数字の種類が答えとなる。 ミス なし。 コード #include <iostream> #include <cstdio> #include <vector> #include <set> #include <algorithm> using namespace std; typedef long</algorithm></set></vector></cstdio></iostream>…

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

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

問題 問題概要 省略 解法 2部マッチングでできるのか、て感じ。公式解説を見ればわかる。実装はs,tを追加して、最大フローを求める感じで書いたもの。 ミス 制約が小さければ、bitDPでもできるぽい。グラフ問題に落とせるようにしたい。 コード #include <iostream> #i</iostream>…

問題 問題概要 省略 解法 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>…

問題 問題概要 省略 解法 まず、1つ分で、どこからスタートしたら、どこに到達するかをメモしておき、そのあと、すべてのスタート時点に対して、何回で同じ位置に戻ってくるかを計算し、それらの最小公倍数を求めれば、答えとなる。 ミス なし。 コード #inc…

問題 問題概要 多角形を１つの直線で分断すると、いくつに分断されるかを求める問題。 解法 公式解説がわかりやすい。 分割された多角形の数 = 切っている本数+1 = (多角形と線分の交点の数 / 2) +1 = (線分と交差する多角形の辺の本数 / 2) +1 ミス 写経。…

問題 問題概要 省略 解法 dfsで友達の友達を求めることにした。この時に、dfsの引き数として、現在の頂点と、前回の頂点、探索回数、スタート時点の頂点を持つことにした。前回の頂点は元の頂点に戻るのを禁止しするため。スタート時点を保持しておくのは、…

問題 問題概要 省略 解法 ナップザック問題に選んでいい品物の個数を制限する制約を追加した問題。 dp[i][j][l] := i番目のスクショまで見て、j枚貼り、幅lを使っているときの重要度の最大値 として、ループで値を埋めていく。 ミス なし。 コード #include <iostream></iostream>…

問題 問題概要 省略 解法 nやkは小さいので、全探索できるな。でも、kが毎回変わるから、単純にループを書こうと思うと、kに応じて、ループの回数を変えたコードを書かなければならなくなり、めんどくさいので、dfsで何回ループをしなければならないかを引数…

問題 問題概要 木のグラフが与えられる。その木に対して、辺を１つ加えでできる、閉路の長さを答える。 解法 まず、LCAを求める。LCAについては、蟻本。多くのクエリが与えられるので、いちいち親をたどっていては、間に合わない。そこで、頂点vから、2k回上…

問題 問題概要 与えられた文字列から、部分文字列として、共通のもの(T)を取り出し、S = T + TのSの長さを求める問題。 解法 まず、与えられた文字列を2つに分ける。その後、その2つの文字列の最長共通部分列(LCS)の長さを求めて、2倍したものが答えの候補と…

問題 問題概要 スペース入りのアルファベットンの文が与えられるので、単語ごとの頭文字をとり、それをつなげたものを表示する問題。 解法 まず、name[0]は必ず、頭文字になる。そのあとは、スペースのあとの文字が必ず頭文字になるので、スペースのあとの文…

問題 問題概要 省略。 解法 まず、簡単にわかることは、D=1の場合において、上側の何番目から始めたら、下側の何番目につくかというのを求める。それを利用して、それぞれの列から開始して、d回後にどこにいるかを求めればいい。しかし、このようにやってし…

問題 問題概要 省略。 解法 解説スライド見るとわかりやすい。 kmjp.hatenablog.jp スターリング数は、S(n, k) 区別できるn個のものを区別できないkグループに分類する方法の場合の数を漸化式と表すことができる。 S(n, k) = s(n - 1, k - 1) + k * S(n - 1,…

問題 問題概要 省略。 解法 ほぼ実装問題。文字の長さは短いので、数字で始まり終わる１周分の文字列をすべて全探索すればいい。このときに、sを２倍に伸ばしておくと、前に戻ってくる処理を簡単に省くことができる。あとは、前から見ていき、数字の部分num…

問題 問題概要 木の上での最短経路(根からの距離、葉からの距離)を求める問題。 解法 根から葉、葉から根へ向けて、bfsをすればいい。その時に注意することはbfsで次に進む方向を決めるときに、来た方向に戻ってしまうと、正確な値が求まらないので、queueの…

問題 問題概要 バスが通るのを記録する。それぞれの系統に対して、最終１つ前のバスと最終のバスはほかのバスとその他のバスをそれぞれ異なるように記録している。その記録が条件に沿ったものかを判定する問題。 解法 それぞれの系統のバスは、WGRの順に出て…

問題 問題概要 門松列になる組み合わせを求める問題。 解法 この問題の注意点は並び順が違っても、同じ竹の組み合わせなら同じとカウントするという点である。よって、門松列になる竹の組み合わせが何通りあるかを求めるには、３本の竹が異なるようにとるこ…

問題 問題概要 条件を満たす最大の値を求める問題。 解法 求める棒の長さは条件を満たす最大の値であり、その値より棒の長さを短くしても条件を満たすが、それより大きくすると条件を満たさなくなる。よって、このような場合は、二分探索をして効率よく求め…