Can't Stop の確率とか求めた。 https://boardgamearena.com/gamepanel?game=cantstop確率が大きい順連続してサイコロをふれる回数のうち、確率 以上のうち最大のものも記載（右端）。 目 目 目 確率 回数 6 7 8 0.9197530864197531 8 5 7 8 0.9143518518518…

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。 解説 以下、""はガウス記号、" " は集合 の要素の個数とする。自然数 の積が 以下になるようなものをどうやって求めればい…

セグメントツリーを python でかいた。 参考文献 理論はこれ。 セグメント木について - beet's soil 実装はこれ。 セグメント木をソラで書きたいあなたに - hogecoder 実装 ほぼほぼそのまま python で書きましたくらい。 解答 class SegmentTree: def __ini…

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

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

木の直径、重み付き木の直径のライブラリ作ってないと思って作ってみた。 python です。 操作は、幅優先探索を2回するだけ。 AtCoder Grand Contest で直径を使う問題が出たけど、 直径まで考えが及ばなかったので、覚えるために記事を書いてる。 アルゴリズ…

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

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

yukicoder contest 210 に参加した。 A、Bしか解けなかった。 Cは面白い問題だと思ったけど、解けなかった。 というわけで、C の問題はこれ。 No.811 約数の個数の最大化 - yukicoder 解答を見て、なるほどってなったので解説を書く。 解説 ポイントは、自然…

エクサウィザーズ 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。 トポロジカルソートとは いい感じに有向グラフの頂点の番号付けを変える操作。 いい感じっていうのは…

正確に言うと、単語帳の単語をランダムに問題として出力してくれるプログラムをpythonでかいた。 strip() が便利だった。 説明 ./tangocho.orgというファイルを読むことにする。 path = "./tangocho.org" とする。中身は | apple | りんご | | tomato | トマ…

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…

pythonで行列を高速に計算したい！numpyを使うと良いのじゃ。 を 乗する。 import numpy as np X = np.matrix([[....],...,[...]]) A = X**r 終わり。速い気がする。 np.array(X) np.matrix(X) で互いに行き来できる。

をリストとすると、 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座標の和が奇数で…

忘れないように。 簡単のため、関数などを書いたソースファイル及びヘッダファイルを source.c source.h、この関数を使ったソースファイルを main.cとする。これをコンパイルして、 main.exeと名付ける。次をやればよい。 gcc -o main.exe source.c main.c

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が出力される。