ABC027のCが面白かったので。 問題概要 A, Bがゲームをする。正整数Nが与えられる。 で初期化する。 を 倍するか、 倍した後、 を加算する Aさんから行い、 を超える操作を行った方が負け。 解説 操作を言い換えると、次のようになります。 ここから、 回目…

ABC129 F を解いた。 問題はこれ。 F - Takahashi's Basics in Education and Learning。 解説 行列累乗を使う問題。各桁に何個あるかを間違えたので、解説をつけておく。少し一般化した形で書きます。 を整数とし、 を正整数とする。 このとき、初項 、公差…

問題はこれ E - Max GCD 解説 操作前を とし、操作が終わったものを とする。 最終的に、全て の倍数になったとすると、 は全て で割り切れる。 つまり、 も で割り切れる。 和は操作で不変なので、 も で割り切れる。 つまり、解の候補は の約数に限られる…

ABC 134 E Sequence Decomposing を解いたので。 pythonだからか、少し違うコードなので記しておく。 問題はこれ E - Sequence Decomposing。 Remark bisect_left や bisect_right は順序を保ったまま挿入する場合のインデックスを示している。 bisect_left …

AtCoder Beginner Contest 132 F / Small Products を解答ACしたので、 行間の証明をメモしておく。問題はこれ F - Small Products。 解説 以下、""はガウス記号、" " は集合 の要素の個数とする。自然数 の積が 以下になるようなものをどうやって求めればい…

AtCoder Beginner Contest 128はリアルタイムで参加できなかった。 そのE問題が面白かったので、解説する。 問題はこれ E - Roadwork。 解説 一言で言うと、時刻 で考えれば十分。 簡単な場合に、説明する。 Aさんが、時刻 に出発して、時刻 から に道路工事…

AtCoder Beginner Contest 126 で苦手な構築系がでたけど、解けたので記念に記事にしておく。 実験が初めてうまくいったので。問題はこれ F - XOR Matching。 解説 実験する。 次のようなコードを書いた。 実験プログラム from itertools import permutation…

面白かったので。 解けてもおかしくなかった。めっちゃ苦戦したけど。問題はこれ E - Polynomial Divisors。ポイントはフェルマーの小定理と、 次方程式の根の個数。 解説の準備 フェルマーの小定理 を素数とする。任意の の倍数でない整数 に対して、 とな…

Tenka1 Programmer Contest 2019 に参加した。C しか解けなかった。 D の Three Colors が解けそうで解けなかったので、その解説。 問題はこれ D - Three Colors。 解説 ほぼほぼ公式解説の通りだけどね。 とする。 三角形の最長の辺が 以上だと、正の面積を…

エクサウィザーズ 2019 E Black or White の解説。コンテスト中に解けたのが嬉しかったので、ついでに解説を書く。問題はこれ E - Black or White。 解説はこれ https://img.atcoder.jp/exawizards2019/editorial.pdf。 解説 まず、 回目までに 個の黒が全て…

トポロジカルソートの勉強をした。もともとの目的は EDPC ( Educatiocal DP contest ) の G. Longest Path を解くためにやった。これ G - Longest Path。 トポロジカルソートとは いい感じに有向グラフの頂点の番号付けを変える操作。 いい感じっていうのは…

AtCoder Grand Contest 011の B の Colorful Creatures を解いた。 解説と違ってたから、解説を書く。 ２分探索を使って解いた。問題はこれ B - Colorful Creatures。 解説はこれ https://img.atcoder.jp/agc011/editorial.pdf。 解説 全ての生き物の色が異…

AtCoder Begginer Contest 083、AtCoder Regular Contest 074 D Restoring Road Network よくわからなかったので、解説の解説をする。 他の人のコードを見ながら勉強した。 問題がこれ D - Restoring Road Network。 解説がこれ https://img.atcoder.jp/arc0…

をリストとすると、 X.sort() でソートできる。を2次元配列のリストとする。上と同様にソートすると、第1成分がソートされたあと、第2成分がソートされる。ところで、第2成分についてソートしたくなることがある。 そうするには、 X.sort(key = lambda x:x[1…

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選 B - Sum AND Subarrays B - Sum AND Subarrays を解いた。 公式解説はこれ https://img.atcoder.jp/dwacon5th-prelims/editorial.pdf。bit演算系の問題は苦手だけど、初めてコンテスト中に…

これ D: Game on a Grid - Indeedなう（オープンコンテストB） | AtCoder です。最小全域木の問題です。 Prim法で解きました。 Kruskal法の、やり方がわからなかった。 解説曰く、できるらしい。Prim法の解説記事です。 最小全域木をpythonで - kamojirobrot…

これ D - Built? です。最小全域木の問題です。Kruskal法で実装しました。 最小全域木をpythonで - kamojirobrothersのブログ Kruskal法の記事です。よくある考察のやつです。 気づきませんでした。プログラムはこれ。 from heapq import * def find(A,x) ->…

最小全域木の勉強をしたので、まとめる。これ AtCoder 版！蟻本 (初級編) - Qiita をやってて、最小全域木の項目があったのでやった。やり方はwikipedia 全域木 - Wikipedia を参考にした。これのKruskal法とPrim法をやった。 Kruskal法 Kruskal法の理論 Kru…

ABC 107 / ARC 101 D Median of Median D - Median of Medians をpython(pypy)で解いた。解説はこれ https://img.atcoder.jp/arc101/editorial.pdf。ほとんど解説どおりだけど、勉強のため自分の言葉で解説する。 解説 以下、 により、 以上の最小の整数を表…

これ D - Robot Arms を解いた。 解説はこれ https://img.atcoder.jp/arc103/editorial.pdf。 参考にしたのはこれ AtCoder ARC 103 D - Robot Arms (600 点) - けんちょんの競プロ精進記録。という長さのアームがあれば、各格子点のx座標とy座標の和が奇数で…

AtCoder Grand Contest 028のB問題を解いた。 時間内には解けなかったし、解説もよくわからなかった。 問題はこれ B - Removing Blocks。 解説はこれ https://img.atcoder.jp/agc028/editorial.pdf。 参考にしたのはこれ AGC028 B問題 Removing Blocks - ban…

めっちゃ調べて、なるほどって言いながら解いた。 解いた問題はこれ D - Worst Case。 解説がこれ https://img.atcoder.jp/arc094/editorial.pdf。 解説はよくわからなかったので、これ AtCoder ARC 094 D - Worst Case (700 点) - けんちょんの競プロ精進記…

写経して、通したが、そのコードに反例があったので、メモ。 pythonでやたら速いやつに対する反例。 Submission #3336978 - AtCoder Beginner Contest 056。 5 12 6 4 3 2 1答えは0だけど、1が出力される。

AtCoder Beginner ContestのD問題を解いた。 問題はこれ D - Maximum Average Sets。 解説はこれ https://atcoder.jp/img/abc057/editorial.pdf。 今回は問題自体の話ではなく、Counterのfor文の挙動がバージョンによってかなり違うということ。 次のコード…

AtCoder Regular ContestのD問題を解いた。 問題はこれ D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder。 解説はこれ AtCoder Regular Contest 036 解説。 書いてみたら、最後のテストケースだけREになって、なんでや！ってなって、調べた。 あっ…

pythonでやってる人が全然いない・・・。 トポロジカルソートよくわかんないけど、解けたから解説する。 AGC027のC問題 AtCoder Grand Contest 027のC問題です。 これ C - ABland Yard。 解説 公式の解説はこれ https://img.atcoder.jp/agc027/editorial.pdf…

unionfindの勉強をしたので。 unionfindはグラフの頂点で互いに繋がっているかどうかを判断するのに便利です。 追加の仕方がややこしくて、まだ全然、体に馴染んでない。 unionfindのプログラムの肝は、繋がっている頂点に対しては、同じ値を返すという関数…

優先度付きキュー(priority_queue)の勉強をしたので。 heap型を使えば良い。 heapはリストに比べて最小値の取り出しがはやく、新たな数の追加もはやい。 pythonにはheapqというmoduleがある。 heapqのheapには、基準となる数以外に別の数をtupleの形で持つこ…

これhttp://hos.ac/slides/20140319_bit.pdfを見ながら、これの基本問題をやった。 やり方はこれを見れば十分です。 問題設定はこちら。 N個の変数v_1, ..., v_n。 Q個のクエリ。 各クエリはv_a_jにw_jを加えるという操作。 answerは各クエリに対してv_1 + .…

atcoderで2分探索に気づけないので、覚えるために、書き残しておく。 問題はABC063のD問題。 D - Widespread 解説はこれ。 https://atcoder.jp/img/arc075/editorial.pdf 大事なのは中のコメントのみ(##以下)。 ついでだけど、遅かったので、少し修正した。#…