https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_g 前提知識 二分探索 DP 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7037185 制約が割と小さい。小課題でヒントとして与えられている情報を考えると、dpできそうな感じがする。 dp[i][k] …
![はてなブックマーク - 平均レーティング [技術室奥プログラミングコンテスト#4 Day2 G]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/20/111658)
https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_f 前提知識 2次imos法 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7036758 考え始めが難しい問題である。 制約にはこれと言った弱点が見つからない。 問題を見ると、「ちょうどゼロになる…
![はてなブックマーク - Segtree☆Magica [技術室奥プログラミングコンテスト#4 Day2 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/20/111656)
https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_e 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7035886 何から手をつけたものかと思うのだが、何か全探索対象か固定できるものを考える。 q[i]を固定してみると、操作がやりづらいが、Lを…
![はてなブックマーク - 引きこもり [技術室奥プログラミングコンテスト#4 Day2 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/20/111651)
https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_d 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7034041 さて、何かを全探索することから考え始めるわけだが、xを固定してみよう。 すると、A[y], A[z]をどうするかという話になるが、まず…
![はてなブックマーク - 新入生歓迎数列 2 [技術室奥プログラミングコンテスト#4 Day2 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/20/111650)
https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_c 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7033757 実験せよと問題が囁いてくるので、実験をする。 labo関数を使って、バックトラックで実験してみる。 眺めると、ゼロの個数は偶奇し…
![はてなブックマーク - Parity [技術室奥プログラミングコンテスト#4 Day2 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/20/111648)
https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_b 前提知識 全方位木DP 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7033397 問題を少し読み替えて考えてみる。 全ての写真を集めることができない状況というのは、どういう状況だろうか。…
![はてなブックマーク - Stalker [技術室奥プログラミングコンテスト#4 Day2 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/20/111646)
https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_a 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7031891 操作を見ると、y座標は+2するしかないので、yが負の場合は達成できない。 目標のy座標の上限が105なので、多くても105/2回くらいし…
![はてなブックマーク - Jumping!! [技術室奥プログラミングコンテスト#4 Day2 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/20/111644)
https://atcoder.jp/contests/abc138/tasks/abc138_e 解説 https://atcoder.jp/contests/abc138/submissions/7015274 文字列tを先頭から貪欲にs'からとっていく。 貪欲にとるためには、文字列sのある場所から一番近いどころにある、とある文字の座標を取って…
![はてなブックマーク - Strings of Impurity [AtCoder Beginner Contest 138 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/19/024031)
https://atcoder.jp/contests/abc138/tasks/abc138_d 前提知識 imos法 解説 https://atcoder.jp/contests/abc138/submissions/7014727 木上でimos法をやる。 頂点p[j]にx[j]を足す。この状態で根からある頂点の値を子供に足していく。 これを続けていくと、…
![はてなブックマーク - Ki [AtCoder Beginner Contest 138 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/19/024030)
https://atcoder.jp/contests/abc138/tasks/abc138_c 解説 https://atcoder.jp/contests/abc138/submissions/7014597 abcの具材があったときに、((a+b)/2+c)/2=a/4+b/4+c/2のような場合が考えられる。 なるべく、分母が大きいものは、なるべく小さい数にあて…
![はてなブックマーク - Alchemist [AtCoder Beginner Contest 138 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/19/024028)
https://atcoder.jp/contests/abc138/tasks/abc138_b 解説 https://atcoder.jp/contests/abc138/submissions/7014467 問題で与えられている計算を素直にやろう。 割り算は整数同士でやると、整数の結果となってしまうので、A[i]もdoubleで取得して、全体的に…
![はてなブックマーク - Resistors in Parallel [AtCoder Beginner Contest 138 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/19/024027)
https://atcoder.jp/contests/abc138/tasks/abc138_a 解説 https://atcoder.jp/contests/abc138/submissions/7014434 A以上とA未満の場合分けをして、出力する文字列を分けよう。 int A; string S; //-----------------------------------------------------…
![はてなブックマーク - Red or Not [AtCoder Beginner Contest 138 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/19/024026)
https://yukicoder.me/problems/no/868 前提知識 戻すDP 解説 https://yukicoder.me/submissions/370474 戻すDPを知っている人は、適用するだけである。 まずは、普通にDPを作ろう。 dp[i][k] := 配列Aのi番目まで使って、総和がkである組み合わせ 戻すDPを…
![はてなブックマーク - ハイパー部分和問題 [yukicoder 868]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/18/112505)
https://yukicoder.me/problems/no/867 解説 https://yukicoder.me/submissions/370451 まず、やはり気になるのは、制約である。 K2がついているし、かつ、A[i][j]の値がとても小さい。 これはKが増えれば増えるほど、K2による影響が増えていきそう。 なので…
![はてなブックマーク - 避難経路 [yukicoder 867]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/18/112502)
https://yukicoder.me/problems/no/866 解説 https://yukicoder.me/submissions/370328 結構計算量が厳しいらしいので、ゴリゴリ計算系であろうと思う。 全探索で考えると、左上をHW通り試し、正方形の一片を試してmin(W,H)通り試す。 これだと間に合わない…
![はてなブックマーク - レベルKの正方形 [yukicoder 866]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/18/090115)
https://yukicoder.me/problems/no/865 解説 https://yukicoder.me/submissions/370121 クエリ計算を行っていくが、降水量が減ることはないため、 変化する分を計算すればいい。 ある個所が変更されたときに影響を受けるのは24区間である。 なので、その24区…
![はてなブックマーク - 24時間降水量 [yukicoder 865]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/18/090113)
https://yukicoder.me/problems/no/864 解説 https://yukicoder.me/submissions/370113 ab + bc + cd + da = Kを変形していく (ab + da) + (bc + cd) = K a(b + d) + c(b + d) = K (a + c)(b + d) = K となるので、a+c, b+dはKの倍数になる。 なので、Kを2つ…
![はてなブックマーク - 四方演算 [yukicoder 864]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/18/090111)
https://yukicoder.me/problems/no/863 解説 https://yukicoder.me/submissions/369283 計算量が線形時間であれば、Nが40倍になれば、かかる時間も40倍になっているはずである。 小数点切り捨てでAミリ秒なので、実際には、A.0～A.9999であるので、40倍する…
![はてなブックマーク - 計算量 [yukicoder 863]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/18/090110)
https://atcoder.jp/contests/agc037/tasks/agc037_a 前提知識 DP 解説 https://atcoder.jp/contests/agc037/submissions/6964393 AGCの頭ということで貪欲で解きたい気持ちをこらえて解法を考える。 順位賞を見ると爆速で解いている人もいるが、結構落ちて…
![はてなブックマーク - Dividing a String [AtCoder Grand Contest 037 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/18/090108)
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_e 解説 https://atcoder.jp/contests/otemae2019/submissions/6931414 問題を整理すると、校長がまず出発して、先頭から順番に前との距離がある一定の距離になったら歩き出すような 入場でよくある…
![はてなブックマーク - 最悪の教頭 (Worst Head Teacher) [大手前プロコン 2019 E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/163213)
https://yukicoder.me/problems/no/858 解説 https://yukicoder.me/submissions/368837 A/Bをしていって商をこたえていく。 余りを10倍して小数点以下の答えを求めていく。 Bで割って、あまりを残して、10倍して…というのを繰り返す。 ll A, B; //----------…
![はてなブックマーク - わり算 [yukicoder 858]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161959)
https://yukicoder.me/problems/no/857 解説 https://yukicoder.me/submissions/368776 基本的にはZ回素振りをするのだが、X,YがZ以内になっていれば、そこは素振りしないので、デクリメントしよう。 ll X, Y, Z; //---------------------------------------…
![はてなブックマーク - 素振り [yukicoder 857]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161958)
https://codeforces.com/contest/1203/problem/E N要素の配列Aがある。 各要素1だけ増減することができる（自然数の範囲で）とき、作ることのできる数の最大種類数は？ 1≦N≦150000 解説 https://codeforces.com/contest/1203/submission/58867373 貪欲に作る…
![はてなブックマーク - Boxers [Codeforces Round #579 (Div. 3) E]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161956)
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_g 前提知識 座標圧縮 imos ダイクストラ 解説 https://atcoder.jp/contests/otemae2019/submissions/6932829 ベースはBFSな感じがする。 だが、BFSにしては盤面が広い。 そこで座標圧縮してダイク…
![はてなブックマーク - 空をかけるピ太郎 (Pitaro, who Leaps through Air) [大手前プロコン 2019 G]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161954)
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_f 前提知識 DP更新最適化 解説 https://atcoder.jp/contests/otemae2019/submissions/6931848 最小値を求める問題で制約も103くらいなので、DPかフローかという雰囲気がある。 まずはDPから考えて…
![はてなブックマーク - 天秤とコイン (Balance and Coins) [大手前プロコン 2019 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161952)
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_d 前提知識 桁DP 解説 https://atcoder.jp/contests/otemae2019/submissions/6931592 まずmod109+7なので、とりあえずDPを疑おう。 今回は桁数が大きく、かつ、上から決めていくので、桁DPを疑おう…
![はてなブックマーク - FizzBuzz (FizzBuzz) [大手前プロコン 2019 D]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161950)
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_c 解説 https://atcoder.jp/contests/otemae2019/submissions/6931000 カード列Bを使って、Ciを何個作れるかという問題であるが、カード列Bは毎回並び替えるので、特に順番は関係ない。 関係あるの…
![はてなブックマーク - カード並べ 2 (Arranging Card 2) [大手前プロコン 2019 C]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161948)
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_b 解説 https://atcoder.jp/contests/otemae2019/submissions/6930836 変数が多く、何か手を付けていいかわからないかもしれない。 こういう時は何かを固定するのがいい。 最も効果的な決め所を探…
![はてなブックマーク - 駒 (Pieces) [大手前プロコン 2019 B]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161947)
https://atcoder.jp/contests/otemae2019/tasks/otemae2019_a 解説 https://atcoder.jp/contests/otemae2019/submissions/6928689 B≦Aを満たすときに授業に間に合う。 そうでないなら、遅刻と答えよう。 int A, B; //--------------------------------------…
![はてなブックマーク - 寝坊だ！ピ太郎！ (You overslept, Pitaro) [大手前プロコン 2019 A]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/16/161945)
https://atcoder.jp/contests/abc137/tasks/abc137_f 前提知識 ラグランジュ補間 解説 https://atcoder.jp/contests/abc137/submissions/6896149 ラグランジュ補間ができるのでやる。 N個の頂点からO(N2)でN-1次元以下の多項式を復元できる。 https://mathtr…
![はてなブックマーク - Polynomial Construction [AtCoder Beginner Contest 137 F]](https://b.hatena.ne.jp/entry/image/https://www.hamayanhamayan.com/entry/2019/08/14/131223)