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が小さい ・区間は共通部分を持たない と怪しい部分がたくさんあることに気づく。 区間を利用して高…

atcoder.jp 解法 再帰によって条件を満たすそれぞれの確率を求めようとすると、3100以上の計算量が必要になる場合がある。 愚直に解こうとすると指数時間になってしまう場合、DP(メモ化再帰)が有効になる場合は良くある。 そこで、3つの硬貨の数の取りうる場…

atcoder.jp LIS問題という有名問題を少し変えた問題です。 LIS問題について 最長増加部分列(LIS)問題は、昇順(または降順)となるような部分列は最長でいくつ作れるか？という問題です。 O(N2)のDPが最初に思いつきましたが、これでは間に合いません。 有名問…

問題のリンク 本当はAtCoder Libraryを使って解くことが想定されている問題ですが、全く使わず解きました。 とりあえずなんでもいいので、遅延評価セグメント木の練習がしたかったので。 転倒数について まず、これがわからないと問題が解けません。 一応問…

セグメント木 セグメント木は、区間更新・区間上の最小値や和などを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>…

問題リンク ワーシャルフロイド法は名前も知っていたし、使う問題も解いたことがあったが、アルゴリズムの理解が足りなかったため、この問題はコンテスト中に解くことができなかった。 解法 ワーシャルフロイド法は、 dp[k][s][t]: k以下の頂点を中継してよ…

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

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

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

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

問題リンク 解法 公式解説では2分探索の解法が紹介されていましたが、自分はクエリ先読みで解きました。 $ K_1, K_2, … , K_Q $ と $ A_1, A_2, …, A_N $ をそれぞれ昇順にソートして、先頭から順に突き合わせて、クエリの答えを先に求めておくことを考えま…