geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

アルゴリズム

構造体Loop

初めに 概要 コンストラクタ build get count 実装 アルゴリズム 前処理について getについて countについて AtCoderでの過去問でLoopを使える問題 初めに 独自で実装している構造体Loopについて書いておきます(C++です)。 AtCoderでこの構造体を使用して解…

Mo's Algorithm

AtCoder Biginner Contestに出題されたので、実装してみました。 解説へのリンク(ネタバレ注意) 解説に書かれている以下のリンクに詳細があるので、アルゴリズムについては要約して書きます。 概要 数列についての個の閉区間のクエリにで答える。 やっている…

牛ゲー

2022/01/15 修正 ・有向グラフの図追加 初めに 牛ゲーとは 最大値と最短経路 具体例 初めに AtCoderの問題で牛ゲーが出たので、まとめておきます。数学的に厳密でない部分や、誤りを含む場合もありますのでご了承ください。 牛ゲーとは 以下の2つの問題があ…

離散対数問題:Baby-step giant-stepのアルゴリズム

はじめに 離散対数問題についての問題がAtCoder Beginner Contestで出題され、色々と調べてみたので、その内容をメモします。 離散対数問題 を満たす最小の整数kを求める問題です。 これを求めるアルゴリズムにBaby-step giant-stepがあります。 Baby-step G…