ひらめの日常

プログラミングと読書と

解法メモ

ABC134-E Sequence Decomposing (500)

Sequence Decomposing 問題はこちら atcoder.jp 問題文は次のように言い換えることができる。すなわち、「数列 が与えられた時に、その数列を狭義単調増加部分列に分ける。その分け方の最小値を求めなさい」という問題と同値になる。 考え方 sample1について…

ABC040-D 道路の老朽化対策について (500)

道路の老朽化対策について タイトルだけ見ると政策の説明みたいだけど、競技プログラミングの問題。 問題はこちら。 atcoder.jp 都市をつなぐ道路が与えられるので、都市を頂点、道路を辺としてみたグラフを考えることにする。 Unionfindを使ってクエリごと…

ABC127-E Cell Distance (500)

Cell Distance 問題はこちら atcoder.jp 数式があるので、それを文章にする。 「 行 列のマス目のうち、 マスに駒をおく。このコストは全ての駒のペアのx座標の差 + y座標の差の和で計算される。これを全ての配置について和を取りなさい。」 考え方 愚直にや…

ABC131-F Must Be Rectangular! (600)

Must Be Rectangular! 問題はこちら atcoder.jp 考え方 解説放送が一番わかりやすいと思うので、そちらを見ると良い。 www.youtube.com 座標を二部グラフで捉えるという考え方は典型らしい。 下記の座標を、x座標とy座標をそれぞれ頂点としてもつ二部グラフ…

ABC128-E Roadwork (500)

Roadwork 問題はこちら atcoder.jp 考え方 まずは、 に出発した人がどのような条件を満たした時に の地点で通行止に引っかかるかを考えてみる。すると、1秒ごとに1進むので、以下の条件を満たしているときに通行止に引っかかるということが分かる。 これを愚…

ABC130-E Common Subsequence (500)

Common Subsequence 問題はこちら atcoder.jp この問題はLCS(Longest common subsequence)と関わりが深いのでまずはそれから書いてみる。 LCS 最長の共通部分列の長さを求めてくださいというのが典型的な問題。次のような例を考えてみる。 s: abcd t: acfed …

Educational Codeforces Round 63 D. Beautiful Array

Beautiful Array 問題はこちら codeforces.com 自分が気づいたところ まず最初に,xが負の時は最小区間和を選んできてそれをx倍する.xが正の時は最大区間和を選んできてそれをx倍する.とすれば最大値が求まると考えた.ここでセグ木とかをググり始める... …

Tenka1 2019-C Stones (300)

Stones 問題はこちら atcoder.jp 自分が気づいたところ 全ての石が黒 or 白になると勘違いをし, WA 左端から ... と白が続いている時は無視し,そのさきは全て黒 or 白になると勘違いし,WA 右端から ### と黒が続いている時も無視できることに気づくが,黒…

Codeforces Round #552 (Div. 3) E. Two Teams

Two Teams 問題はこちら codeforces.com 自分が気づいたところ 愚直解は,毎回使っていない最大値を検索→幅 を探索し,使っていないものをk個チームに属させるというもの. 計算量としては, なのでそのまま実装すると になるので間に合わない. そこで,一…

Codeforces Round #551 (Div.2) C Serval and Parenthesis Sequence

Serval and Parenthesis Sequence 問題はこちら 問題文難しくないですか... codeforces.com 自分が気づいたところ 括弧を扱う問題では,stackを用いると綺麗に書けるなと思い実装.しかしコンテスト時間内に問題文を解読できなかった... 解説を読んで このブ…

JOI2018/2019-D 日本沈没(難易度6)

日本沈没 問題はこちら atcoder.jp 自分が気づいたところ 小課題1に関しては,愚直にシミュレーションしていけば求まるが,満点をもらうことはできない. のように,谷になっているものに注目した.すると,問題は「谷となっているところのうち,一番低いと…

ABC045-D すぬけ君の塗り絵 (400)

すぬけ君の塗り絵 問題はこちら atcoder.jp 自分が気づいたところ なので,全てのマス目を調べていくのは間に合わなさそう.そこで,黒く塗られているマス目だけに注目することにした. 一つの黒いマス目が影響を及ぼすマス目は,周囲の9マスだけである.こ…

ABC095-D Static Sushi (500)

Static Sushi 問題はこちら atcoder.jp 自分が気づいたところ 最大でも反対方向に向きを変える動きは一回だけなので,反転する場所を一つ決めてそこから反転した後の最大値を求めることを考えた. これだと,計算量は反転する場所が ,反転後の最大値探索が…