atcoder.jp 解法 行に対して操作を行った場合、列には何も影響を及ぼさないことから、行と列は別々に考えても問題ないことがわかる。 今回問われているのは、どの要素も使用してない行や列を全て削除したときに、それぞれの要素の座標はどうなるか？というこ…

atcoder.jp 解法 参考: 桁DPについて nizi-24.hatenablog.com 桁DPをしよう。 dp[i][smaller][k] ← i: 上から何桁目まで確定しているか、smaller: 未満フラグ、k: 今までに何個0以外の数字が登場したか 遷移するときには、0かどうかで場合分けすればよい。 …

atcoder.jp 桁DPの問題。初めて桁DPについて学んだので記事にします。 桁DPとは？ ・N以下の自然数で条件を満たすものは何通りか？ ・N以下の自然数で条件を満たすものの中で最大のものはいくつか？ みたいな問題で活躍するアルゴリズムです。 説明は少し複…

atcoder.jp 解法 類題1 蟻本にのっているAOJの問題。 poj.org 類題2 典型90問の1問目。 atcoder.jp 最大値の最小化をしろということなので、二分探索を考える。 探索する条件としては、「K以下の切断回数で答えをXにできるか？」 なぜK以下でよいかというと…

atcoder.jp 一応自力ACはしたのですが、理解が曖昧だったので学んだことをメモしておこうと思います。 下の記事の解説がわかりやすかったです。 drken1215.hatenablog.com math-stan.com 解法 iとjを分離できれば、前計算を行って高速に答えを求めることがで…

atcoder.jp 解法 ぱっと見、部分和問題かなと思うが、O(N2)になってしまうため間に合わない。 他の方法を考えてみると、 ・なぜか区間が与えられている ・Kが小さい ・区間は共通部分を持たない と怪しい部分がたくさんあることに気づく。 区間を利用して高…

セグメント木 セグメント木は、区間更新・区間上の最小値や和などをO(logn)で求めることができるデータ構造です。 セグメント木を理解するために役立つリソース かつっぱさんの動画です。説明が丁寧なのでわかりやすいです。 part1では、セグメント木の雰囲…

AOJの問題 区間和の取得は普通にできるが、更新は工夫が必要。 二分木は区間和を保持する。 また、遅延配列はINFで初期化しておこう。これはフラグとして利用する。(更新後の値として与えられる可能性があるため、0はフラグの値として使えない。) 更新すべき…

AOJの問題 RMQ and RUQ、RSQ and RAQからそれぞれ関数をとってきて貼り付けただけでは解けない。 加算の際に多少工夫が必要。 RMQ and RUQでは、2分木に区間和を保持していたが、今回必要なのは区間の最小値なので、それを保持する。 加算の際には、区間の全…

AOJの問題 RSQ&RAQのコードを少し変更しただけ。 区間更新の場合は加算と違って、普通に値を代入するだけでよい。 遅延配列の要素は、更新クエリで与えられることのない値で初期化すること。これがフラグの代わりになる。 実装 #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

AOJの問題 区間加算と区間和の取得を同時にこなさないといけないので、普通のセグメント木だと難しくなってくる。 そこで、遅延評価セグメント木を導入する。 普通のセグメント木では、区間更新にO(nlogn)だけかかってしまうが(区間更新・一点取得の場合は別…

問題 nodeの値を保存しているだけではどの値がいつ更新されたモノなのかがわからないので、更新された時間も保持しておくことにする。 値を取得するときは、子から見ていって最新の更新時刻を持つnodeの値が現在の値になる。 管理する情報が増えただけで後は…

問題 RSQのコードを少し弄れば解ける。 具体的には、一点更新→一点取得、区間取得→区間更新、のように取得と更新の役割を逆転させる。 かつっぱさんの動画がわかりやすい。 実装 #include <bits/stdc++.h> using namespace std; struct RAQ_SegTree { int n; // 葉の数 vect</bits/stdc++.h>…

問題 RMQでは0-indexedだったのに、こっちは1-indexedになってて引っかかった。 RMQのコードを少し弄っただけです。 実装 何をやっているかはコメントに書いてあります。 #include <bits/stdc++.h> using namespace std; struct RSQ_SegTree { int n; // 葉の数 vector<long long> node</long></bits/stdc++.h>…

問題 RMQは、与えられた区間の最小値を求めるというもの。 セグメント木を使って解きます。 実装 セグメント木の実装の中で何をしているかはコメントに書いてあります。 AOJのテストケースはパスしましたが、バグが潜んでいるかもしれません。 #include <bits/stdc++.h> usi</bits/stdc++.h>…

問題リンク 解法 問題文を読んだだけでは、観覧車がどのような動きをしているのかわかりにくいが、図を書いてみると、中心を(0, 0, L/2)とした半径2/Lの円周上を動いていることがわかる。 まず、与えられた時間の時の現在地の座標が知りたい。 中心を(0, 0, …

問題リンク 解法 a,b,cのなかにKが持っていない素因数を持っている数が含まれることはないので、a,b,cは必ずKの約数だとわかる。 後は約数の中から条件を満たす組を全探索できれば良いが、最大5000個以上の約数を持つ可能性があるのでN3では間に合わない。 (…

問題リンク 解法 解説スライドで紹介されていた解法とは違う方法で解いた。(解法2に少し似ているかも) 既にoxが含まれている区間を、右左どちらに広げても必ずoxが含まれることがわかる。 線形時間で問題を解きたいので、lかrを固定したい。今回はlを固定し…

問題リンク 解法 体重・身長の取る範囲が小さいということがとても気になる。 これをどうにか使えないかと考えてみると、二次元平面上に(身長, 体重)のようにプロットして、何らかの方法で条件を満たすそれぞれの範囲内にいくつ点が存在するかを高速に計算で…

問題リンク 解法 $ O(N\log N) $ の解法です。 O(N2)でも間に合うのですが、制約を勘違いしていたので、O(NlogN)の解法を考えました。 まず、開区間のまま考えるとややこしいので全て閉区間に変換することを考えます。 $ l_i≠l_j, r_i=l_j $ の時、 $ [l_i, …

問題リンク B問題にしては難しかった。 解法 N回操作した後の赤色のボールの数はC×D×Nなので、一回の操作でC×D個の赤ボールを追加するとしても問題ない。 そうすると赤ボールの数が青ボールの数以上になるのはいつか、という問題になる。 一回の操作で赤ボー…

問題へのリンク 解法 最短経路を求めたりする問題ではないので、BFSではなくDFSがしたい気分になる。 制約がとても緩いので、全探索が有効そう。 スタート地点は最大でも16通りしかないので、すべてのスタート地点から探索を開始してみることにする。 DFSの…

問題へのリンク 解法 区間の和を求めるということでまずしゃくとり法が思いついた。 全体の総和をsumとして、x = sum/10 とすると、区間の総和がx以上になるまで右端を動かし続け、x以上になった時点で区間の総和がsumと等しいかを確認すれば良い。 また、su…

N進数→10進数の変換 Nの部分を変換して使いましょう。 numは任意のN進数です。 powはdouble型などを返すので、誤差に注意。(誤差が気になる場合は自作累乗関数を作ろう。) string str = to_string(num); long long n = 0; long long sz = str.size(); for (i…