問題 C - Fair Elevator 解法 まず、各階に、乗った階が指定されている場合はを、降りた階が指定されている場合はをマークする（、は階数と被らない何かしらの数）。 ただし、どちらも指定されている場合は、乗った階に降りた階をマークする。 このとき、以…

問題 https://atcoder.jp/contests/abc161/tasks/abc161_d 番目のルンルン数を求めよ。 解法 今のルンルン数から次のルンルン数を求める方法を考える。 ルンルン数をある程度列挙して眺めてみると、繰り上がりが起きた桁は、一つ上位の桁より1小さい（0の場…

問題 https://yukicoder.me/problems/no/1170 座標がである個の駅がある。のとき、駅と駅に無向辺が張られている。各駅が含まれる連結成分の数を求めよ。 解法 座標が小さい順に見ていく。 Union-Findを用いて、各駅における、からの間に存在する駅を（二分…

問題 https://codeforces.com/problemset/problem/1391/D 行列の01行列において、全ての部分偶数長正方行列に含まれる1の数を奇数にするための最小操作回数を求めよ。 解法 とする（そうでない場合はを転置）。 の場合、部分偶数長正方行列は存在しないため…

問題 E - Balanced Path コード Submission #14018954 - AtCoder Beginner Contest 147 解法 左上のマスから右下のマスまで移動した際に、通ったマスに書かれている2つの数の差の絶対値を足すか引くかした値の絶対値をとすると、の最小値を求めたい。 これは…

問題 D - Gathering Children 解法 回の移動後は必ずRLとなっている箇所に集まるので（それ以外では明らかにループしない）、その箇所に集まる人数を求めれば良い。 あるRLとなっている箇所における左側のRの個数をとすると、は偶数であることから、人が左に…

問題 E - Two Currencies 解法 （計算量に関しては自信ないです） を頂点とみなす。ただし、は都市、は持っている銀貨の枚数を表す 銀貨の枚数はより多く持っていても意味がないので、頂点数はで済む。 上記のように頂点を増やした場合、辺は鉄道路線と両替…

問題 D - XXOR 解法 2進数での各桁におけるは、各の中で桁が0である個数と1である個数の多い方をにかけることで求めることができる。 ここでネックとなるのが以下という条件だが、これは桁DPを考えれば良い。 つまり、上位の桁から、未満が確定している場合…

問題 AtCoder Beginner Contest 113 - AtCoder 解法 条件を満たす横線の引き方は他の高さの引き方に影響されないため、各高さ毎に、各縦棒にたどり着けるのは何通りかをDPで求めれば良い。 DPの遷移としては、区間ごとに横線があるような引き方が何通りある…

問題 No.1011 Infinite Stairs - yukicoder 解法 コンテスト中はPython/Ruby/PHP/Golang(Go)で上限のある重複組み合わせ - Qiitaを参考にして解いたのだが、解説ではDP+累積和で解いていたので、そちらの解法が上手くイメージができなかったこともあり、解き…

問題 No.1008 Bench Craftsman - yukicoder 解法 基本は解説の通りであるが、自分なりの説明を行う。 まず、ベンチの耐久度を固定すると、人が番目の区画に与える負荷は、である。 この負荷は正の場合、人毎に等差数列になるため、imos法を用いることで、番…

問題 E - Simple String Queries 解法 クエリの回数分、文字目から文字目まで調べるのでは間に合わない。 そこで、各アルファベット毎に、以上で初めて登場する位置を探索し、その位置が以下だった場合、種類を増やすことにする。 始めて登場する位置は、各…

問題 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できたので、それについてです。（実行時間、メモリ共に良い結果ではありません）（参考程…