srupのメモ帳

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

abc

abc 019 D - 高橋くんと木の直径

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

abc 019 C - 高橋くんと魔法の箱

abc

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

ABC 016 D - 一刀両断

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

ABC 016 C - 友達の友達

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

ABC 015 D - 高橋くんの苦悩

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

ABC 015 C - 高橋くんのバグ探し

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

ABC 014 D - 閉路

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

ABC 013 D - 阿弥陀

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

ABC 014 C - AtColor

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

ABC 045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit)

問題 問題概要 省略。 解法 書かれていた通りに、シミュレーションをする。 ミス なし コード #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>…

ABC 045 A - 台形 / Trapezoids

abc

問題 問題概要 省略。 解法 台形の面積の公式を利用。 ミス なし コード #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>

ABC 043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit)

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

ABC002 C - 直訴

abc

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

ABC041 D - 徒競走

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

ABC041 C - 背の順

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

ABC041 B - 直方体

abc

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

ABC041 A - 添字

abc

問題 問題概要 指定された添え字の番号を出力する 解法 やるだけ ミス 特になし コード #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>