はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミング

Collatz [yukicoder 887]

https://yukicoder.me/problems/no/887 解説 https://yukicoder.me/submissions/382000 制約を見てみると、シミュレートできそうな雰囲気がある。 400回までが上限なので、ぶん回す。 int n0; //----------------------------------------------------------…

約数の総和 [yukicoder 888]

https://yukicoder.me/problems/no/888 前提知識 約数列挙 O(sqrt(N)) 解説 https://yukicoder.me/submissions/381998 約数列挙は O(sqrt(N))で行うことができる。 これをしていれば答えることができる問題。 やり方はここの約数列挙 O(sqrt(N))に概略がある…

Collatz [yukicoder 887]

https://yukicoder.me/problems/no/887 解説 https://yukicoder.me/submissions/382000 制約を見てみると、シミュレートできそうな雰囲気がある。 400回までが上限なので、ぶん回す。 int n0; //----------------------------------------------------------…

隣接3項間の漸化式 [yukicoder 891]

https://yukicoder.me/problems/no/891 前提知識 行列累乗 解説 https://yukicoder.me/submissions/382008 問題を見るとフィボナッチ数の定義に似ている。 ある項のフィボナッチ数を高速に求める方法として、行列累乗が知られている。 今回の問題もこれで解…

移調の限られた旋法 [yukicoder 890]

https://yukicoder.me/problems/no/890 前提知識 109+7mod上での二項係数 約数系包除原理 解説 https://yukicoder.me/submissions/382005 回転対称性について考える。 まず、beetさんが質問していたので見てみる。 回転対称性を持つとはある整数i(0

約数の総和 [yukicoder 888]

https://yukicoder.me/problems/no/888 前提知識 約数列挙 O(sqrt(N)) 解説 https://yukicoder.me/submissions/381998 約数列挙は O(sqrt(N))で行うことができる。 これをしていれば答えることができる問題。 やり方はここの約数列挙 O(sqrt(N))に概略がある…

素数! [yukicoder 889]

https://yukicoder.me/problems/no/889 解説 https://yukicoder.me/submissions/382002 いろいろな種類の数に対する判定をする問題。 こういうものは関数化してライブラリとして持っておこう。 完全数判定なんて、どこで使うかわからないが、いつか役立った…

アマリクエリ [yukicoder 885]

https://yukicoder.me/problems/no/885 解説 https://yukicoder.me/submissions/379434 剰余にまつわる重要な性質がある。 1度剰余が行われると、値が変わらないか、半分未満の数に変わる。 よって、各要素について値が変わる回数はlogA[i]回となる。 つまり…

ぬりえ [yukicoder 883]

https://yukicoder.me/problems/no/883 解説 https://yukicoder.me/submissions/379423 構築問題は色々な方針があるが、今回は最適方針があり、それで構築する方針を取ろう。 頑張れば全部の行と列でK個配置することができる。 つまり、Mを固定したときにMK…

Eat and Add [yukicoder 884]

https://yukicoder.me/problems/no/884 解説 https://yukicoder.me/submissions/379432 操作について考えてみると、2kを足すか引くかということができる。 各位について、「2kを1度足すか、2kを1度引くか、なにもしない」の3択を選択すればいい。 2kを足して…

約数倍数 [yukicoder 882]

https://yukicoder.me/problems/no/882 解説 https://yukicoder.me/submissions/379418 条件を満たす整数は、Aの約数なので、[1,A]のどこかにある。 なので、これを全探索して、Aの約数であってBの倍数であるものがあれば、YES そうでないならNO int A, B; /…

Range High-Element Query [yukicoder 878]

https://yukicoder.me/problems/no/878 前提知識 ダブリング 解説 https://yukicoder.me/submissions/377919 高い要素の個数を答える方針でしばらく考えていてダメだったので、 ちょっと言い換えを考えてみる。 区間が与えられた時に、先頭から順に最も近い…

Many Slimes [AtCoder Beginner Contest 140 F]

https://atcoder.jp/contests/abc140/tasks/abc140_f 解説 https://atcoder.jp/contests/abc140/submissions/7444067 まず、218は5*105くらいあるので、小さい数ではない。 割り当て問題としてマッチング問題があるが、そんな雰囲気は全然しない。 全然思い…

Range Compress Query [yukicoder 876]

https://yukicoder.me/problems/no/876 解説 https://yukicoder.me/submissions/377914 問題をよく見ると、隣り合う数が異なる組+1を答える問題になっている。 つまり、数の実際の大小は特に意味がない。 加えて、今回は区間addのクエリもあるため、階差を使…

Range ReLU Query [yukicoder 877]

https://yukicoder.me/problems/no/877 前提知識 セグメントツリーにセグメントツリーを乗せるテク 解説 https://yukicoder.me/submissions/377916 やりすぎ回答かもしれない。 maxという制約が入ったままだと問題としては扱いづらい。 なので、[l,r]という…

Maximal Value [AtCoder Beginner Contest 140 C]

https://atcoder.jp/contests/abc140/tasks/abc140_c 解説 https://atcoder.jp/contests/abc140/submissions/7443482 なるべくA[i]を大きくするように考えたい。 A[i]中心に考えてみると、A[i]≦min(B[i-1],B[i])を満たす必要がありそう。 最大化したいので等…

Buffet [AtCoder Beginner Contest 140 B]

https://atcoder.jp/contests/abc140/tasks/abc140_b 解説 https://atcoder.jp/contests/abc140/submissions/7443466 シミュレーションしていこう。 前に食べた料理の種類を記録しておけば、満足度Ciを得られるかどうかが分かる。 int N, A[20], B[20], C[20…

Second Sum [AtCoder Beginner Contest 140 E]

https://atcoder.jp/contests/abc140/tasks/abc140_e 解説 https://atcoder.jp/contests/abc140/submissions/7443801 総和を求める問題でよく使うテクであるが、「全てのパターンについてある値の総和」というのを 「(ある値×その値になる組み合わせ)の総…

Face Produces Unhappiness [AtCoder Beginner Contest 140 D]

https://atcoder.jp/contests/abc140/tasks/abc140_d 解説 https://atcoder.jp/contests/abc140/submissions/7443535 400点にしてはだいぶ難しく見える。 回転というのは厄介か。 まず、重要な考察がいくつかある。 方向が一致してない箇所で幸福が1つ減る …

Password [AtCoder Beginner Contest 140 A]

https://atcoder.jp/contests/abc140/tasks/abc140_a 解説 https://atcoder.jp/contests/abc140/submissions/7443443 各桁についてN通りの候補があるため、答えはNNNになる。 つまり、N3を答えよう。 int N; //--------------------------------------------…

Engines [AtCoder Beginner Contest 139 F]

https://atcoder.jp/contests/abc139/tasks/abc139_f 前提知識 幾何問題 解説 https://atcoder.jp/contests/abc139/submissions/7340335 頂点全てを偏角ソートすると、最適な組み合わせは、連続する区間の頂点を選んで選択することである。 言われてみればそ…

ModSum [AtCoder Beginner Contest 139 D]

https://atcoder.jp/contests/abc139/tasks/abc139_d 解説 https://atcoder.jp/contests/abc139/submissions/7339048 Nの上限が109なので、Nに起因するアルゴリズムではなさそう。 それで400点ということもあり、特殊な解法が存在するっぽい。 という訳で実…

League [AtCoder Beginner Contest 139 E]

https://atcoder.jp/contests/abc139/tasks/abc139_e 解説 https://atcoder.jp/contests/abc139/submissions/7339484 全くいい方針が思いつかない。 AtCoderなので、貪欲法かもしれない。 先頭から順番にペアでとってこれる場合はとってくる動作を繰り返せば…

Lower [AtCoder Beginner Contest 139 C]

https://atcoder.jp/contests/abc139/tasks/abc139_c 解説 https://atcoder.jp/contests/abc139/submissions/7338829 全探索を考える。 始点を全探索して、右側にどれだけ移動できるかを確かめると、O(N2)で解が求まる。 例えば、「6 5 4 9」 となっていて、…

Power Socket [AtCoder Beginner Contest 139 B]

https://atcoder.jp/contests/abc139/tasks/abc139_b 解説 https://atcoder.jp/contests/abc139/submissions/7340535 B口以上に拡張と問題にはあるが、すでに1口はあるので、B-1口増やしたいという問題で考える。 電源タップを1つ使うと、1つの口がA個に増え…

Tenki [AtCoder Beginner Contest 139 A]

https://atcoder.jp/contests/abc139/tasks/abc139_a 解説 https://atcoder.jp/contests/abc139/submissions/7338689 各文字について一致していれば答えのカウントをインクリメントする。 結果を答える。 string S, T; //----------------------------------…

救援 [東京工業大学プログラミングコンテスト2019 H]

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_h 前提知識 動的構築セグメントツリー マージテク 解説 https://atcoder.jp/contests/ttpc2019/submissions/7238575 まずは簡単なことから考えていく。 条件を見ると支援関係は連結成分ごとに考えられ…

Palindromic Love Letter [東京工業大学プログラミングコンテスト2019 G]

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_g 解説 https://atcoder.jp/contests/ttpc2019/submissions/7237908 操作は逆に行うこともできるので、問題の言い換えができる。 「操作をちょうどK回行うことで、文字列Tを何種類の回分にできるか」 …

Road Construction [東京工業大学プログラミングコンテスト2019 F]

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_f 解説 https://atcoder.jp/contests/ttpc2019/submissions/7237707 有向グラフで最小コストなので、とりあえずダイクストラか。 グラフはDAGなので、ダイクストラというよりDPできそう。 いつものトポ…

Next TTPC [東京工業大学プログラミングコンテスト2019 A]

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_a 解説 https://atcoder.jp/contests/ttpc2019/submissions/7225294 計算を頑張る。 周期cycle=B-Aである。 B, B+cycle, B+cycle*2, ...のようになるが、Tのままだと扱いにくい。 そこで、T-Bとしてお…