自己紹介 びふぉーあふたー 水になるまでのハイライト 1997/08/27 誕生 2019/09/01 黒から灰になる（ABC139） 2019/11/04 灰から茶になる（AGC040） 2020/01/11 茶から緑になる（第6回ドワンゴからの挑戦状 予選） 2020/03/28 緑から水になる（ABC160） 水か…

形式的冪級数（FPS）でやる解法で解いたので、まとめてみます。 問題リンク↓ atcoder.jp 考察 グラフに課される条件のうち、最初の2つの条件 自己ループを持たない すべての頂点の次数が以下である から、考えるべきグラフは直線グラフか頂点数2以上のサイク…

コンテスト中に通せたので、自分の解法を書いてみます。 問題 概要 電車が秒で一方の街からもう一方の街に移動し、街に着いたときに秒停車する。高橋君は秒寝て秒起きるを繰り返す。高橋君は街で降車することができるか？もし可能ならば、最短何秒で降車でき…

問題 E - Queen on Grid 行列のマス目がある。左上のマス目をとして、上から番目、左から番目のマス目をマスとする。1手ごとに、そのマスから下、右、右下方向の好きなマスに移動できる。ただし、障害物に移ったり、障害物をを飛び越える移動や、マス目の外…

さて、ここからが本題です。で、とが互いに素とは限らない一般の場合の離散対数問題を解きます。 実験 からの向きに辺を結んでできた有向グラフを考えます。鳩の巣原理より、どのようなについても、少なくとも乗するとより小さい指数乗の値に戻ることがわか…

前回の続きです。一般化されたBSGSはまとまりをよくするために次回に回し、今回は、 Pohlig-Hellman algorithm BSGS, Pohlig-Hellman algorithmの実装 について書いていきたいと思います。 Pohlig-Hellman algorithm を素因数分解したときの指数が大きい場合…

BSGSを知っていますか？私は知りません。 ということでBSGSのWikipediaを読み漁っていたら、何やらさらにつよいPohlig-Hellman's algorithmなるアルゴリズムがあるじゃないですか！ちょうどその数日前にSA-ISを実装して調子に乗っていたため、アルゴリズムが…