問題 codeforces.comいろいろ誤読や勘違いが多くてAC出来なかった 解法 この問題で出てくる頂点被覆は問題文に書いてある通りで、「あるグラフのすべての各辺について、その辺につながっている2つの頂点どちらかまたは両方の頂点を選択した頂点の集合」がグ…

問題 abc014.contest.atcoder.jp 考察 追加辺を(a,b)間につなげた場合に出来る閉路の長さ(辺の長さ)を求めるということなので、aのノードとbのノードから追加辺以外の辺を辿って最も早く合流できるノードcが分かれば、 cとaの間の長さ + cとbの間の長さ = (a…

問題 abc017.contest.atcoder.jp 考察 部分点まで自力で行けたけど、満点解法は解説を見ながら、AC。解法としてはしゃくとり法をしつつ、DPをしていく。dp[i] = i番目のサプリメントまでを見た時の摂取方法の組み合わせdp[i] := dp[i - 1] + dp[i - 2] + ...…

問題文 codeforces.comリアクティブ方式。 考察 最初は素数を使って割り切れるかどうか試していこうと思いましたが、[2,100]での素数の数が25個なので、97,89などの素数がhidden numberだと20クエリ以内に収まらない。よく考えると,エストラネスのふるい等を…

問題 abc023.contest.atcoder.jp 考察 まず解法として最初に思い浮かんだのは、その時点の高さが最大の風船を割っていく貪欲だが、 風船iと風船jがあり、H[i] S[j]であると、ある時点では風船jの方が割られる風船だが、 最終的な高さは風船iの方が高くなる可…

問題 arc055.contest.atcoder.jp 考え 本番中は全く分からなくて、解説放送をみてもあんまり理解できなかったので、 下記の解説を参考させていただきました。とてもわかりやすいです。ソースコード中に考えをまとめながらコーディングしたのでそちらを参照し…

問題 No.375 立方体のN等分 (1) - yukicoder 考え 同じ方向からN - 1枚の平面で切断するのが最大なので、TMaxはN - 1下図のA方向からの平面の切断数をa、B方向はb、C方向はｃ、とすると TMinはa + b + cの最小の値となる。 なので、aの値を全探索をして、残…

問題 abc038.contest.atcoder.jp 考え 部分点までは自力で行けたけど、満点解法は分からずで、解説などを見て通しました。主に2通りの解き方があるらしい。1つ目は公式解説であるようなセグメントツリーというデータ構造を使う方法。セグメントツリーは蟻本…