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

問題 問題概要 多角形を１つの直線で分断すると、いくつに分断されるかを求める問題。 解法 公式解説がわかりやすい。 分割された多角形の数 = 切っている本数+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回上…

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

問題 問題概要 もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。 解法 区間が始まる点を+1、区間が終わる点を-1することで、[a, b]をインクリメントする必要がなくなり、最後に一度だけ、全体をなめるだけで、最大数がわかる。 ミ…

問題 問題概要 省略。 解法 書かれていた通りに、シミュレーションをする。 ミス なし コード #include <iostream> #include <cstdio> using namespace std; string s[3]; int main(void){ cin >> s[0] >> s[1] >> s[2]; int now = 0; while(1){ if(s[now].size() == 0){ if(no</cstdio></iostream>…

問題 問題概要 省略。 解法 台形の面積の公式を利用。 ミス なし コード #include <iostream> #include <cstdio> using namespace std; int main(void){ int a, b, h; cin >> a >> b >> h; printf("%d\n", (a + b) * h / 2); return 0; }</cstdio></iostream>

問題 問題概要 省略 解法 条件通りにの文字列を作る。 0の時は、文字列の末尾に0を付け加え、1の時は文字列の末尾に1を付け加え、Bの時は、文字列の末尾を取ればよい。 ミス ClangだとACだけど、GCCだとREでよく分からない。 [追記] @mmxsrup 空の文字列に対…

問題 問題概要 ３つの座標が与えられる。その３点を頂点とする三角形の面積を求める問題。 解法 3 点 (0,0), (a,b), (c,d) で構成される三角形の面積は、|ad−bc|⁄2という公式で求められる。この公式を用いるため、三角形の頂点の１つが原点になるように平行…

問題 問題概要 M個のクエリ満たす数字の並びを求める問題。 解法 まず、 どのような数字が数字の集合としてあり得るのかを計算してflagに入れておく。そして漸化式でdpを解く。感覚的には空集合の場合の数から全集合の場合の数へ、集合の数を増やす感じに計…

問題 問題概要 与えられた数字をソートして、もとの添え字の番号を出力する。 解法 pairは1つ目の要素でソートした後、2つ目の要素でソートするので、pairに(身長, 番号)を入れることで、身長でソートした番号がわかる。 ミス 特になし。 コード #include <iostream> #</iostream>…

問題 問題概要 直方体の体積を求める問題 解法 ただ計算するだけだが、2辺をかけるとlong long型を超える可能性があるので、modをとることでオーバーフローを防ぐ。 体積 = a * b % mod * c % mod ミス 特になし コード #include <iostream> #include <cstdio> using namespace</cstdio></iostream>…

問題 問題概要 指定された添え字の番号を出力する 解法 やるだけ ミス 特になし コード #include <iostream> #include <string> using namespace std; int main(void){ string s; cin >> s; int n; cin >> n; printf("%c\n", s[n - 1]); return 0; }</string></iostream>