https://atcoder.jp/contests/abc119/tasks/abc119_d 解説 https://atcoder.jp/contests/abc119/submissions/4378458まず、lower_boundを知らない場合は学ぼう。 これを使うと、あるx以上で最も近い、Sの要素、Tの要素がO(logN)で得られる。 要素の添字を-1…

https://atcoder.jp/contests/abc119/tasks/abc119_c 解説 https://atcoder.jp/contests/abc119/submissions/4378296与えられた操作は順番によって、状況が変化したり、損をすることが無いので、別々に考えよう。 何か全探索する所を探すと、ある竹について…

https://atcoder.jp/contests/abc119/tasks/abc119_b 解説 https://atcoder.jp/contests/abc119/submissions/4378009単位変換をする問題であるが、問題にあることをそのまま実装する。 BTCのものだけ円に変換して、総和を取ると答え。 自分は小数を出力する…

https://atcoder.jp/contests/abc119/tasks/abc119_a 解説 https://atcoder.jp/contests/abc119/submissions/4377976入力が少し複雑なのだが、C++ならscanfという便利な関数があるので、これを利用するとスマートに入力が得られる。 あとは、平成との比較だ…

https://codeforces.com/contest/1131/problem/DN要素の配列X、M要素の配列Yを構築する。 A[x][y] := X[x]とY[y]の大小関係。＜ならX[x]＜Y[y]、＞ならX[x]＞Y[y]、=ならX[x]=Y[y] 配列Aが与えられたときに、配列X,Yを構築できるか判定し、できるなら構築せ…

https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_d 前提知識 半環問題 解説 https://atcoder.jp/contests/yahoo-procon2019-final/submissions/4353743半環をSegtreeであつかうテクを使う。 このテクを知らない場合は、先…

https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_c 前提知識 SegTree＋平面走査 解説 https://atcoder.jp/contests/yahoo-procon2019-final/submissions/4363922こういう矩形クエリについて答える典型として「SegTree＋平…

平面走査 幾何問題 未整理 SegTree+平面走査 AC Fortune Telling 問題 解説1 解説2 解説3 AC Checkered Stamps 解説 未整理 https://www.codechef.com/NOV16/problems/URBANDEV https://www.ioi-jp.org/joi/2013/2014-ho/2014-ho-t5-review.pdf https://qiit…

https://atcoder.jp/contests/yahoo-procon2019-final/tasks/yahoo_procon2019_final_b 前提知識 全方位木DP（これじゃなくてもいいけど） 解説 https://atcoder.jp/contests/yahoo-procon2019-final/submissions/4358833まず、それぞれの木について、ある頂…

https://yukicoder.me/problems/no/794 解説 https://yukicoder.me/submissions/319074まず、Aはソート可能なのでソートする。 ペアを考えると、A「どちらもK/2以下」、B「片方K/2以下、もう片方K/2より大きい」になる。 重要なのが、AのペアとBのペアの個数…

https://yukicoder.me/problems/no/793 解説 https://yukicoder.me/submissions/319055桁ごとに分解して考えると、例えば、1333は 1333 = 1000 + 300 + 30 + 3 となる。 つまり、10^N + (3 + 30 + ... + 3*10^(N-1))である。 10^Nは繰り返し二乗法で高速に計…

https://yukicoder.me/problems/no/792 解説 https://yukicoder.me/submissions/319041ルールが色々書いてあるが、主加法標準形を作れという問題。 情報学部出身なら学んでいる人も多いだろう。 あとは実装を頑張る。 int N; int Q[20], R; //--------------…

https://yukicoder.me/problems/no/791 解説 https://yukicoder.me/submissions/319032場合分けで解く。 あまりに巨大な数は整数型で受け取らず、文字列型で受け取って処理していく。 様式チェックをして、与えられたNがうし数列になっているか確認しよう。 …

https://yukicoder.me/problems/no/790 解説 https://yukicoder.me/submissions/319026考えうる文字列を全探索しよう。 これは、bitを使った全探索で行う。 以下では、1を'('、0を')'として実装している。 正しいカッコ列かの判定は(なら+1, )なら-1とする典…

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_d 前提知識 遅延評価セグメントツリー（区間add, 区間代入→区間sm） 解説 https://atcoder.jp/contests/nikkei2019-final/submissions/4314272この問題は区間add,区間代入,区間総和get…

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c 前提知識 BIT 二分探索 マンハッタン距離についての知識 解説 https://atcoder.jp/contests/nikkei2019-final/submissions/4312922まず、この問題を考える糸口だが、「マンハッタン…

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_b 解説 https://atcoder.jp/contests/nikkei2019-final/submissions/4312776与えられた式はよく見てみると、K進数の数になっている。 そのため、K進数で与えられた数の大小を答えよと…

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_a 前提知識 累積和 解説 https://atcoder.jp/contests/nikkei2019-final/submissions/4312713累積和を知っていれば、それぞれの整数Kについて全探索できると分かる。 練習のために尺取…

https://atcoder.jp/contests/abc118/tasks/abc118_d 解説 https://atcoder.jp/contests/abc118/submissions/4287467嘘解答の可能性があります最適方針として、なるべく桁数を増やしたほうがいいことは分かる。 そのためには、一番少ない本数で作れる数をた…

https://atcoder.jp/contests/abc118/tasks/abc118_c 前提知識 GCD、ユークリッドの互除法 解説 https://atcoder.jp/contests/abc118/submissions/4280971競技プログラミングは時にはエスパー力が求められる。 エスパーをすると、全部のgcdが答えになりそう…

https://atcoder.jp/contests/abc118/tasks/abc118_b 解説 https://atcoder.jp/contests/abc118/submissions/4280142データの渡し方が後から扱うのにシンプルではないので、扱いやすいように入れ替える。A[i][j] := i番目の人がj番目の食べ物が好きなら1, 無…

https://atcoder.jp/contests/abc118/tasks/abc118_a 解説 https://atcoder.jp/contests/abc118/submissions/4278906問題で要求されていることをそのまま実装する。 自分は以下のように実装した。 int A, B; //--------------------------------------------…

https://codeforces.com/contest/1114/problem/Eインタラクティブ問題。 初項X0, 交差D, 項数Nの数列がある。 この数列がランダムな順で入った配列Aがある。 項数Nの情報と、以下のクエリを60回以下行うことで、X0,Dを見つけよ。操作1 : 「? i」A[i]の要素を…

https://codeforces.com/contest/1114/problem/FN要素の配列Aがある。 これについて以下のクエリをQ回行う。操作1: "MULTIPLY l r x" A[l], A[l+1], ..., A[r]全てにxをかける 操作2: "TOTIENT l r" φ（A[l]*A[l+1]*..*A[r]) mod 10^9+7を答える φ(x)はトー…

https://codeforces.com/contest/1114/problem/DN要素の色の配列Cがある。 ある要素を指定する。 指定の要素から以下の操作を何回か行って全ての色を同じにせよ。 操作「指定の要素と連結している（同じ色でつながっている）領域をある色に変える」1≦N, C[i]…

https://codeforces.com/contest/1114/problem/CN!をB進数で表記したときに、末尾に0が何個続くか。 1≦N≦10^18 2≦B≦10^12 解説 https://codeforces.com/contest/1114/submission/49705240Bを素因数分解したときに、p1^e1*p2^e2*...となったとする。 この時、…

https://codeforces.com/contest/1114/problem/BN要素の配列Aがある。 この配列を「連続していてM要素以上の列」にK個に分ける。 分割後の各列について、大きい方からM個取ってくる。 取ったMK個の総和の最大値を求めて、分割地点を答えよ。2≦N≦2*10^5 1≦M 2…

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_e 前提知識 mod2上でのガウスの消去法（掃き出し法） 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4221314本当にちゃんと解きたい場合は線形代数…

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d 前提知識 連結DP 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4212545今回の問題は一筆書きをしたときに通る回数と要求される回数との差を最小…

https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_c 解説 https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4207345交換操作をするためにはA枚にはする必要があるので、A枚までは叩いて増やそう。 この過程で…