ひらめの日常

プログラミングと読書と

atcoder

ABC142-E Get Everything (500)

問題はこちら 考え方 解答 別解 問題はこちら atcoder.jp までの箱がある。 個目の鍵のコストは であり、 種類の箱を開けることができる。全ての箱を開けるために必要な費用の最小値を答えよ。不可能な場合は を出力せよ。 考え方 まず、これは割と複雑な遷…

ABC140-E Second Sum (500)

問題はこちら atcoder.jp 長さ の順列 が与えられた時、区間 に対して以下を計算せよ。 全ての重複しない区間において、二番目に大きい数の和。 考え方 簡単バージョンとしてこの問題があるので見ると良い。 atcoder.jp step1 - 問題の言い換え 愚直にやると…

ABC140-D Face Produces Unhappiness (400)

問題はこちら atcoder.jp 長さ の文字列 が与えられる。L は自分の左に L が来た時、R は自分の右に R が来た時、幸福になるという。以下の操作を 回以下繰り返して、幸福なものを最大いくつにできるか答えよ。 操作: となる を選び、 ] 内にある文字列を左…

ABC123-D Cake 123 (400)

問題はこちら 考え方 解答1 - 解の候補を絞る 解答2 - 貪欲とpriority_queueを使う 解答3 - K個以上になる境目の値を二分探索 問題はこちら atcoder.jp 美味しさは以下のように表される。 種類のケーキ 種類のケーキ 種類のケーキ この時、それぞれのケーキ…

ABC136-E Max GCD (500)

問題はこちら atcoder.jp から となる を選び、 とする。この時、 以下の操作回数で の最大公約数として考えられるもののうち、最大のものを求めよ。 考え方 step1 - 解の候補 まず、 に+1して、 に-1するという操作は、 の値を一つ に移動する操作と考える…

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

問題はこちら atcoder.jp 今回はほぼ解説放送と解説ブログを参考にした自分用のメモ。 考え方 JSC2019予選 - D 「Classified」 (600) - Mister雑記 [AtCoder 参加感想] 2019/08/25:JSC2019予選 | maspyのHP 奇閉路が存在しないようにグラフを分割できれば良…

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

問題はこちら atcoder.jp 考え方 なんか自分で書いててもあまり納得感がないかもしれない... 記事を書いた後に自分がわかりやすかったものを参考として載せておきます。 misteer.hatenablog.com Cで僕が考えたこと・累積的な何かを考えるとよさそう・[L, R]…

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 …

Tenka1 2019-C Stones (300)

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

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

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

ABC095-D Static Sushi (500)

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