競技プログラミング

はじめに 絶対にバグらない二分探索の実装パターンと豪語している記事がありました。 qiita.com 今回はこれを使って競技プログラミングの問題を解けるのかを試します。 挑戦した問題 今回挑戦した問題はABC319のD問題です。 atcoder.jp 解き方としては、答えになりうる最大値と最小値を算出し、二分探索を行う、 というものです。 そこまでは分かったのですが、いろいろ試してもサンプル含め半分くらいしか正解できません...。 問題の解説を見ても、なぜか最後に-1するのが答えとなっていたりします。汎用的な解き方ではなさそうなのであまり納得ができませんでした。 また、めぐる式二分探索という方…

はじめに こんにちは！jastawayです。ABC393の参加記です！！ AHC043が昨日から始まりましたね！まだ正の得点を得られていませんが、参加してます。 目次 はじめに 目次 ABC393 A問題 B問題 C問題 D問題 E問題 F問題 E問題(帰還) コンテスト結果・感想 ABC393 参加前の私のレートは1910でした。前回のABC392で全完し、ARC192で3完2403パフォで大勝利してました！ ついに1900台に到達し、黄色が見えてきたところです。しかし、私は知っています。ここからが長いということに・・・ 今回の配点は100-200-300-425-475-500-675で、…

RMQを5分で理解するためのノート。 セグメントツリー 配列の区間 (範囲) に対するクエリを効率的に処理するためのデータ構造。特に、区間の最小値・最大値・和などを求める場合に適している。 データを動的に更新したり、区間の最小値・最大値・合計を求めるのに適している。 例題: 競技プログラミングの鉄則 演習問題集 A58 atcoder.jp 必要な処理は以下の３つ。 セグメントツリーを作ること セグメントツリーを更新すること セグメントツリーの区間を読み取っていくこと 順に見ていく。 セグメントツリーを作る セグメントツリーは2kで表現する必要があるため、N < 2k となるkを求めたうえで2…

ダブリングを5分で理解するためのノート。 ダブリング 行き先がN個あり、それぞれの要素について1回移動した時の移動先が決まっているとする。 このときK回の移動を繰り返した時の到達点を高速に求める手法のひとつにダブリングがある。 計算量 この場合愚直に計算しようとするとK回の移動をそのままシミュレートするので、計算量はO(K)となる。 が、ダブリングを用いることでO(N log K)とすることができる。なぜO(N log K)となるかは後の具体的な方法を知れば理解できる。 方法 dpに似ていて、あらかじめ計算結果のテーブルを用意しておく。このとき用意するテーブルは、穴iから2j回移動した場合の行…

問題文 https://atcoder.jp/contests/abc392/tasks/abc392_d 問題概要 $n$ 個のダイスがある．$i$ 番目のサイコロは $K_i$ 面ダイスであり，その各面の出目は $A_{ i, 1 }, A_{ i, 2 }, \dots, A_{ i, K_i }$ である．ダイス $i$ を振ったとき，各出目が出る確率は等しく $\frac 1 { K_i }$ である． $n$ 個のダイスから $2$ 個を選んで同時に振ることを考える．$2$ つの出目が等しくなる確率はダイスの選び方によって異なるが，確率を最大化した場合のその確率はいくらか？ 制約 …

優先度付きキューを5分で理解するためのノート。 優先度付きキュー 文字通り優先度が付いたキューだ。通常のキューはFIFOだがこのキューは値が小さいものから順にpopできる。 Pythonではheapqが用意されているので、特段独自実装する必要がない。名前がヒープなのかキューなのかという感じだが、内部ではヒープになってるっぽい。使い方は以下の通りでheapifyでリストを優先度付きキューに変えられる。heappushで要素を入れ、heappopで要素を出す。 import heapq list = [2,6,1] heapq.heapify(list) heapq.heappush(list, …

貪欲法を5分で理解するためのノート。 貪欲法とは 最も単純な貪欲法の例を挙げる。 例. 1週間毎日お小遣いを0~100円までもらえるとする。もらえる金額はあなたが決めることができるとする。 Q、1週間後に一番たくさんお金を貯めるにはどうすればいい？ A、毎日100円ずつもらう 以上、最もシンプルだと思う貪欲法である。要は求めたい答えに至るまでの各回で何かしらの行動を選択できる場合に、答えに対して最適な行動を取っていくのが貪欲法だ。 だいたいイメージが湧いたと思うので、例題を踏まえて実装パターンを確認する。…といっても最適な行動は毎回変わるので、考え方さえ分かればそれをコードで表現するだけになる…