問題 D - Checker 参考 解説PDF 解説放送 累積和を何も考えずに書けるようにする！ - Qiita ARC 089 D - Checker (500) - kurarrr's memooo 解法 マスが白の時、マスは黒（逆も然り） マスが黒の時、マスは黒（白の時も然り） よって、調べる範囲はで済む。 …

問題 D - Recording 解法 解説の解法に感動させられたが、自分なりの解法を残しておく。 まず、チャンネル毎に開始時間の早い番組から順に見ていき、同じチャンネルの連続した番組を一つの番組としてまとめる。 この操作を行う事で、全ての番組において、同…

問題 D - Wall からに書き換えるには魔力が必要であるとき、を全て1に変えるのに必要な魔力の最小量を求めよ。 ただし、の場合は変えなくて良い。 解法 制約上、ワーシャルフロイド法で解けそうだったが、ダイクストラ法の経験が乏しかったため、ダイクスト…

問題 C - Snuke Festivalにおいて、となる組み合わせは何通りあるか。] 解法 解説では二分探索で解いていたが、頭に尺取り法しか無かったため、尺取り法で解いた。 まず、単調減少である必要があるため、降順にソートする。次に、が大きい順にとなる組み合わ…

問題 E - Payment紙幣の価値がである時、価値のたこ焼き器を買う場合の、自分と店員の使う紙幣の枚数の合計の最小値を求めよ。 解法 下位桁から順に見ていく。 4以下の場合 自分がその枚数を使う。 6以上の場合 一つ上の桁を+1し、店員が10-xの枚数を使う。 …

問題 D - Pairs個の整数における全てのペアの積を求め、それらを小さい順に並び替えたとき、番目にくる数を求めよ。 解法 「積が以下であるペアの個数が個」となるの最小値を、二分探索で求める。最左値と右辺値は入力された値から求めても良いが、正負によ…

問題 D - Axis-Parallel Rectangle2次元座標上のN個の座標のうち、K個以上を辺または内部に含む、それぞれの辺がX軸とY軸に平行な長方形の面積の最小値を求めよ。 解法 制約より、各座標のX軸・Y軸の値は異なるので、各座標をX軸の値によってソートすると、…

No.990 N×Mマス計算（Kの倍数） - yukicoderがかのどちらかである時、がの倍数であるようなの組合せは何通りあるかという問題です。WAを抜け出せなかったので解説に沿って解いたのですが、解いていて楽しかったので記事を書くことにしました。（全面的にC++…

D - Restoring Road Networkノードのグラフにおける各ノード間の最短経路の長さが与えられるので、そのようなグラフの存在判定をし、存在するならば辺の長さの和の最小値を求めよという問題です。 int n; cin >> n; vector<vector<int>> a(n, vector<int>(n)); for (int i = 0</int></vector<int>…

E - Almost Everywhere Zero桁DPの問題ですね。考察力不足により、コンテスト中にACできませんでした。コンテスト後も実装に手間取ったので、水色への道は遠そうです。 解き方としては、大まかには解説の通りですが、少し自分なりに変更しています。（そのせ…

D - Decrease (Contestant ver.)長さの数列において、最大値の値を減らすという操作を回行うことにより、最大値がになるような数列を求めよという問題です。 に厳しめの制約がある為、の場合を考えます。私は、が変化した場合に何を変化させれば良いのかをか…

D - Fennec VS. SnukeN個のノードからなる木において、ノード1とノードNのそれぞれから、自分のノードと隣接している、他人のノードでないノードを取ることができるというルールで陣取りを行った場合、取るノードが先に無くならないのはどちらかという問題で…

https://atcoder.jp/contests/abc065/tasks/arc076_b座標とを繋ぐ辺の重みがである時、N個の座標における最小全域木の重みを求めよという問題です。 最小全域木は名前しか知らなかったので、解説を読み、最小全域木で検索することによって、何とか解けました…

見当がつかなかったので、解説を見ました。分かるまで考えると記憶に残るというのはあるのですが、精神が擦り減るので最近は気が向いたときにしかやっていません。（前回のブログで、解説を見ないと考察が中途半端でコードが汚くなると書いたのですが、今回…

青パフォの問題で詰まったので、水色パフォ以下の問題をまったり解くことにしました。（パフォはAtCoder Problems基準です） 今回のABC062Cは、長方形の2辺(H, W)が与えられるので、出来るだけ面積が均等な長方形3つに分割し、一番大きな長方形と小さな長方…

自分の考えたことを文字として残して置きたかったので、ブログを始めてみました。主にAtCoderの問題について書いていけたらと思っております。 手始めに、ABC139EをACできたので、それについてです。（実行時間、メモリ共に良い結果ではありません）（参考程…