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

hamayanhamayan's blog

2019-08-01から1ヶ月間の記事一覧

正規表現間距離 [yukicoder 874]

https://yukicoder.me/problems/no/874 前提知識 DP(【テク20: 編集距離】編集距離の計算は、2つの文字列の添字を持つDPでできる) 解説 https://yukicoder.me/submissions/374482 編集距離はDPで解けることが知られているので、とりあえずDPで考えてみよう。…

バイナリ、ヤバいなり!w [yukicoder 873]

https://yukicoder.me/problems/no/873 解説 https://yukicoder.me/submissions/374460 42+32+22+11+11というのが決まれば、ここからバイナリを作るのは難しくないので、 二乗の和がNであって、底の総和が最小であるようなものを探せばいい。 まずは、実験す…

All Tree Path [yukicoder 872]

https://yukicoder.me/problems/no/872 解説 https://yukicoder.me/submissions/374451 全てのパスの長さの総和を求める問題であるが、こういう問題は集計方法を変えるといい。 全てのパスを列挙するのには、O(N2)かかるので、全てのパス全探索はしたくない…

かえるのうた [yukicoder 871]

https://yukicoder.me/problems/no/871 前提知識 二分探索 BFS 解説 https://yukicoder.me/submissions/374448 シミュレーションを考えてみる。 あるカエルが鳴くとそれに共鳴するのは、とある区間のカエルになる。 どこからどこまでのカエルかどうかの端点…

無敵囲い [yukicoder 870]

https://yukicoder.me/problems/no/870 解説 https://yukicoder.me/submissions/374446 シミュレーションしていこう。 A,B,Cの駒を動かしていって、最終的に指定の座標になるかを見ればいい。 駒毎に位置を持つのではなくて、盤面全体を管理すれば、操作はsw…

Card Collector [第一回日本最強プログラマー学生選手権-予選- E]

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_e 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7125615 とりあえずは、解説放送を見るのがいい。 これを元にして考察過程を想像して書いてみる。 グリッドの問題は行と列をそ…

Classified [第一回日本最強プログラマー学生選手権-予選- D]

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_d 前提知識 分割統治 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7125024 何もわからず解説を見てしまった。 分割統治を行う。 まず、パスが全て偶数になるために満たすべき…

Cell Inversion [第一回日本最強プログラマー学生選手権-予選- C]

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7123399 何から手を付けていいかわからないかもしれない。 こういうときは、色々試していくしかないが、全探索対象を探してみる…

Kleene Inversion [第一回日本最強プログラマー学生選手権-予選- B]

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b 前提知識 転倒数の計算 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7121477 Kの値が109なので、繰り返しの分をどのように効率的に計算するかが問題となる。 まず、2回Aを繰…

Takahashi Calendar [第一回日本最強プログラマー学生選手権-予選- A]

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_a 解説 https://atcoder.jp/contests/jsc2019-qual/submissions/7120856 Mヶ月でD日なので、全部でMD日分あり、これは全探索が可能である。 全探索をして、条件を満たすものを数え上げよう。 i…

平均レーティング [技術室奥プログラミングコンテスト#4 Day2 G]

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_g 前提知識 二分探索 DP 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7037185 制約が割と小さい。小課題でヒントとして与えられている情報を考えると、dpできそうな感じがする。 dp[i][k] …

Segtree☆Magica [技術室奥プログラミングコンテスト#4 Day2 F]

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_f 前提知識 2次imos法 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7036758 考え始めが難しい問題である。 制約にはこれと言った弱点が見つからない。 問題を見ると、「ちょうどゼロになる…

引きこもり [技術室奥プログラミングコンテスト#4 Day2 E]

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_e 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7035886 何から手をつけたものかと思うのだが、何か全探索対象か固定できるものを考える。 q[i]を固定してみると、操作がやりづらいが、Lを…

新入生歓迎数列 2 [技術室奥プログラミングコンテスト#4 Day2 D]

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_d 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7034041 さて、何かを全探索することから考え始めるわけだが、xを固定してみよう。 すると、A[y], A[z]をどうするかという話になるが、まず…

Parity [技術室奥プログラミングコンテスト#4 Day2 C]

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_c 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7033757 実験せよと問題が囁いてくるので、実験をする。 labo関数を使って、バックトラックで実験してみる。 眺めると、ゼロの個数は偶奇し…

Stalker [技術室奥プログラミングコンテスト#4 Day2 B]

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_b 前提知識 全方位木DP 解説 https://atcoder.jp/contests/tkppc4-2/submissions/7033397 問題を少し読み替えて考えてみる。 全ての写真を集めることができない状況というのは、どういう状況だろうか。…

Jumping!! [技術室奥プログラミングコンテスト#4 Day2 A]

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回くらいし…

Strings of Impurity [AtCoder Beginner Contest 138 E]

https://atcoder.jp/contests/abc138/tasks/abc138_e 解説 https://atcoder.jp/contests/abc138/submissions/7015274 文字列tを先頭から貪欲にs'からとっていく。 貪欲にとるためには、文字列sのある場所から一番近いどころにある、とある文字の座標を取って…

Ki [AtCoder Beginner Contest 138 D]

https://atcoder.jp/contests/abc138/tasks/abc138_d 前提知識 imos法 解説 https://atcoder.jp/contests/abc138/submissions/7014727 木上でimos法をやる。 頂点p[j]にx[j]を足す。この状態で根からある頂点の値を子供に足していく。 これを続けていくと、…

Alchemist [AtCoder Beginner Contest 138 C]

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のような場合が考えられる。 なるべく、分母が大きいものは、なるべく小さい数にあて…

Resistors in Parallel [AtCoder Beginner Contest 138 B]

https://atcoder.jp/contests/abc138/tasks/abc138_b 解説 https://atcoder.jp/contests/abc138/submissions/7014467 問題で与えられている計算を素直にやろう。 割り算は整数同士でやると、整数の結果となってしまうので、A[i]もdoubleで取得して、全体的に…

Red or Not [AtCoder Beginner Contest 138 A]

https://atcoder.jp/contests/abc138/tasks/abc138_a 解説 https://atcoder.jp/contests/abc138/submissions/7014434 A以上とA未満の場合分けをして、出力する文字列を分けよう。 int A; string S; //-----------------------------------------------------…

ハイパー部分和問題 [yukicoder 868]

https://yukicoder.me/problems/no/868 前提知識 戻すDP 解説 https://yukicoder.me/submissions/370474 戻すDPを知っている人は、適用するだけである。 まずは、普通にDPを作ろう。 dp[i][k] := 配列Aのi番目まで使って、総和がkである組み合わせ 戻すDPを…

避難経路 [yukicoder 867]

https://yukicoder.me/problems/no/867 解説 https://yukicoder.me/submissions/370451 まず、やはり気になるのは、制約である。 K2がついているし、かつ、A[i][j]の値がとても小さい。 これはKが増えれば増えるほど、K2による影響が増えていきそう。 なので…

レベルKの正方形 [yukicoder 866]

https://yukicoder.me/problems/no/866 解説 https://yukicoder.me/submissions/370328 結構計算量が厳しいらしいので、ゴリゴリ計算系であろうと思う。 全探索で考えると、左上をHW通り試し、正方形の一片を試してmin(W,H)通り試す。 これだと間に合わない…

24時間降水量 [yukicoder 865]

https://yukicoder.me/problems/no/865 解説 https://yukicoder.me/submissions/370121 クエリ計算を行っていくが、降水量が減ることはないため、 変化する分を計算すればいい。 ある個所が変更されたときに影響を受けるのは24区間である。 なので、その24区…

四方演算 [yukicoder 864]

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 863]

https://yukicoder.me/problems/no/863 解説 https://yukicoder.me/submissions/369283 計算量が線形時間であれば、Nが40倍になれば、かかる時間も40倍になっているはずである。 小数点切り捨てでAミリ秒なので、実際には、A.0~A.9999であるので、40倍する…

Dividing a String [AtCoder Grand Contest 037 A]

https://atcoder.jp/contests/agc037/tasks/agc037_a 前提知識 DP 解説 https://atcoder.jp/contests/agc037/submissions/6964393 AGCの頭ということで貪欲で解きたい気持ちをこらえて解法を考える。 順位賞を見ると爆速で解いている人もいるが、結構落ちて…

最悪の教頭 (Worst Head Teacher) [大手前プロコン 2019 E]

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_e 解説 https://atcoder.jp/contests/otemae2019/submissions/6931414 問題を整理すると、校長がまず出発して、先頭から順番に前との距離がある一定の距離になったら歩き出すような 入場でよくある…