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

hamayanhamayan's blog

競技プログラミング

Permutation Oddness [AtCoder Beginner Contest 134 F]

https://atcoder.jp/contests/abc134/tasks/abc134_f 前提知識 動的計画法(箱根DP) 解説 https://atcoder.jp/contests/abc134/submissions/6480100 箱根DPという典型DPテクがあるので、そこをベースに考えてみる。 今回の問題を1つの順列の入れ替えと考え…

Sequence Decomposing [AtCoder Beginner Contest 134 E]

https://atcoder.jp/contests/abc134/tasks/abc134_e 前提知識 2Dセグメントツリー、セグメントツリーにセグメントツリーを載せるテク ← 公式解法ではいらない 解説 https://atcoder.jp/contests/abc134/submissions/6479037 先頭から貪欲に増加列を作ってい…

Preparing Boxes [AtCoder Beginner Contest 134 D]

https://atcoder.jp/contests/abc134/tasks/abc134_d 解説 https://atcoder.jp/contests/abc134/submissions/6478841 B[i] := i番目の箱にボールが何個入っているかと定義しておこう。 まず、自明なところから考えていこう。 A[N]=B[N] これがまず分かるとこ…

Exception Handling [AtCoder Beginner Contest 134 C]

https://atcoder.jp/contests/abc134/tasks/abc134_c 前提知識 累積和 解説 https://atcoder.jp/contests/abc134/submissions/6478504 ある1要素以外の最大値を取りたいという要望には典型テクがある。 累積和を利用するのだが、先頭からと後尾からの2つを構…

Golden Apple [AtCoder Beginner Contest 134 B]

https://atcoder.jp/contests/abc134/tasks/abc134_b 解説 https://atcoder.jp/contests/abc134/submissions/6478072 監視員がカバーできる範囲は[i-D,i+D]なので、2D+1の範囲をカバーできる。 よって、len=2D+1とすると、N/Dの切り上げが必要な監視員の最少…

Dodecagon [AtCoder Beginner Contest 134 A]

https://atcoder.jp/contests/abc134/tasks/abc134_a 解説 https://atcoder.jp/contests/abc134/submissions/6477844 問題に書いてある計算式をそのまま実装しよう。 int R; //---------------------------------------------------------------------------…

イルミネーション (Illumination) [第18回日本情報オリンピック 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0656?year=2019 前提知識 動的計画法 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0654/judge/3757763/C++14 「区間についての制約があって、合計の…

日本沈没 (Japan Sinks) [第18回日本情報オリンピック 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0655?year=2019 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0655/judge/3760197/C++14 海面の高さが上昇すると、島が分割または消滅していって、ま…

マルバツスタンプ (Circle Cross Stamps) [第18回日本情報オリンピック 予選 C]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0654?year=2019 前提知識 動的計画法 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0654/judge/3757763/C++14 貪欲法でも行けそうな感じであるが、DP…

すごろくと駒 (Sugoroku and Pieces) [第18回日本情報オリンピック 予選 B]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0653?year=2019 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0653/judge/3757737/C++14 シミュレーションで解こう。 駒は追い越すことは無いので、…

ソーシャルゲーム (Social Game) [第18回日本情報オリンピック 予選 A]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0652?year=2019 解説 https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0652/judge/3757726/C++14 少なくともC日の間には条件を達成できるので、C日を上限とし…

最短経路の復元 [Hokkaido University Programming Contest 2019 Day 1 E]

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/E 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745712 説明のため、D[u][v] := 頂点uから頂点vへの最短経路としておく。 この問題を見たときに…

貪欲が最適? [Hokkaido University Programming Contest 2019 Day 1 D]

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/D 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3746197 問題を見ると、経験から特殊な性質・規則性を用いる問題だと見える。 こういう時は、実験…

短絡評価 [Hokkaido University Programming Contest 2019 Day 1 C]

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/C 前提知識 構文解析(優先順位有り) 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3746462 まずは、与えられた論理式が理解できないと、始まら…

自身の2倍 [Hokkaido University Programming Contest 2019 Day 1 B]

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/B 前提知識 エラトステネスの篩を使った区間約数列挙 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745884 クエリ問題への取り組み方はいろいろ…

four tea [Hokkaido University Programming Contest 2019 Day 1 A]

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/A 解説 https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3745829 A問題でむずかしめ感じに見えるが、とりあえず全探索を考えてみよう。 パッケージを買う…

MNCTF2019 解説まとめ

http://mnctf.info/mnctf2019/ 参考 CTFmanさん解説 yam7k5さん解説 悪意部品 分からんワード辞書 PLEAD: BlackTechという攻撃者集団が使ったマルウェア RAD機能:Remote Administration Tool, Remote Access Tool 攻撃対象のコンピュータにアクセスできるよ…

Colorful Tree [AtCoder Beginner Contest 133 F]

https://atcoder.jp/contests/abc133/tasks/abc133_f 前提知識 LCA クエリ先読み 解説 https://atcoder.jp/contests/abc133/submissions/6312857重要なこととして、制約を簡単にした問題が解けないか考えてみる。 今回で言うと、辺の長さの変更が難しいので…

Virus Tree 2 [AtCoder Beginner Contest 133 E]

https://atcoder.jp/contests/abc133/tasks/abc133_e 解説 https://atcoder.jp/contests/abc133/submissions/6312375木でmod10^9+7なので、とりあえず木DPを疑う。 dp[cu] := cuを根とする部分木での塗り方の総数 これをベースにまずは考えてみよう。 正直こ…

Rain Flows into Dams [AtCoder Beginner Contest 133 D]

https://atcoder.jp/contests/abc133/tasks/abc133_d 解説 https://atcoder.jp/contests/abc133/submissions/6312080各山にx1, x2, x3, ... 降ったとする。 すると、ダムには(x1+x2)/2=A1のように溜まっていく。 割り算は面倒なので、全部二倍しておこう。 1…

Remainder Minimization 2019 [AtCoder Beginner Contest 133 C]

https://atcoder.jp/contests/abc133/tasks/abc133_c 解説 https://atcoder.jp/contests/abc133/submissions/6313028300点問題にしては難しい問題に見える。 (i×j) % 2019 = (i % 2019) * (j % 2019) となる。 理論的な最小値は0であり、これを目指すことを…

Good Distance [AtCoder Beginner Contest 133 B]

https://atcoder.jp/contests/abc133/tasks/abc133_b 解説 https://atcoder.jp/contests/abc133/submissions/6311855(i,j)の組は全探索できるので、全探索して、距離が整数となる組を数え上げよう。 ルートの解決が少し厄介であるので、距離^2が平方数である…

T or T [AtCoder Beginner Contest 133 A]

https://atcoder.jp/contests/abc133/tasks/abc133_a 解説 https://atcoder.jp/contests/abc133/submissions/6311780選択肢は2つある。全員電車か、全員タクシーである。 よって、min(N * A, B)が答え。 int N, A, B; //-----------------------------------…

なかよし旅行 [yukicoder No.848]

https://yukicoder.me/problems/no/848 前提知識 ダイクストラ 解説 https://yukicoder.me/submissions/357498星2.5にしては、かなり難しい問題に見える。 こういう場合は、制約からエスパーするに限るのだが、N≦2000というのが弱点っぽい。 N^2っぽいので、…

Divisors of Power [yukicoder No.847]

https://yukicoder.me/problems/no/847 前提知識 枝刈り全探索 解説 https://yukicoder.me/submissions/357485まず、N^Kの正の約数であって、M以下のものというのはそんなに個数がなさそうな感じがする。 N^Kを素因数分解をして、適当な枝刈りをしながらDFS…

メダル [yukicoder No.846]

https://yukicoder.me/problems/no/846 解説 ceil(N/P)=AであるNの範囲は、[P*(A-1)+1,P*A]である。 他のメダルについても同様に条件を満たすNの範囲が存在する。 他のメダルについては、そのメダルだけの枚数で計算することになってしまうので、B+=A, C+=B…

成績上昇大作戦 [ICPC JAG 模擬国内予選 2019 E]

問題分と入出力 前提知識 最大クリーク 解説 M≦40なので、ビット的な計算量が出てくるだろうと仮定を立てる。 しかも、40というのは微妙な所で2^Mというのは間に合わない。 だが、2^(M/2)なら間に合う。 半分全列挙である。 ここで終わった。 最大クリークら…

文字列の魔法 [ICPC JAG 模擬国内予選 2019 D]

問題文と入出力 前提知識 動的計画法 今回の問題はパッと見て、編集距離DPっぽい。 競プロの問題で、典型的な問題と形が似ている問題は、元の問題の解き方をアレンジして解く場合が多い。 そのため、編集距離を求めるDPを元にして考えていこう。 Add, Erase,…

毒の沼地 [ICPC JAG 模擬国内予選 2019 B]

問題文と入出力 前提知識 01-BFS 解説 今回の問題は、 damage(sx, sy, tx, ty) := 座標(sx,sy)から座標(tx, ty)へ移るための最小ダメージ として、damage(X[0], Y[0], X[1], Y[1]) + damage(X[1], Y[1], X[2], Y[2]) + ...をしていけばいい。 damage関数の中…

割り勘 [ICPC JAG 模擬国内予選 2019 A]

問題と入出力 解説 それぞれが払うべき金額は、A[i]円かM/N円のどちらか安い方なので、 その総和を答えると答え。 int N, M, A[101]; //--------------------------------------------------------------------------------------------------- void solve()…