JavaのModIntを考える

序論 プログラミングコンテストでは「答えの数を1000000007で割った余りを求めよ」という問題が大変よく出題される。1000000007は素数で、ほかにも 998244353 が代わりに出題されることもよくある。これらは真の解は大きくなりすぎて計算できない場合でも、…

プリミティブタイプはJavaのジェネリクスに入らない

int, long, doubleなどのプリミティブな型を使うことは当然だ。これらに対して同じデータ構造やアルゴリズムを適用したいことがあるのも当然だ。 ジェネリクスがあるのだからint, long, doubleで共通な計算は実装できそうなものだが、できない。例えば配列の…

疑似乱数メルセンヌツイスタは連続 624 項が分かれば完全に再現できる

標準ライブラリのメルセンヌツイスタは実装と定数が公開されている。すると、出力された疑似乱数列から内部状態をコピーすることができる。 メルセンヌツイスタの実装 英語版の wikipedia の実装を見る。 en.wikipedia.org 定数 標準ライブラリは周期が 2^19…

Codeforces エイプリルフール 2023 解法

Codeforces April Fools Day Contest 2023 の感想 CF のエイプリルフールコンテストの特徴は タイトルやサンプル入出力がヒント プログラミングコンテストのローカルネタ ミステリーランゲージ (マイナー言語、エソラング) など codeforces.com理不尽に難…

USACO 2023 Feb. Problem 1. Hungry Cow 解法

USACO 2023 February Contest, Platinum Problem 1. Hungry CowUSACO 2023 の 3rd Contest の復習をする。 全体感想 問題名 略解 目標時間 Hungry Cow セグツリー 2時間 Problem Setting bit dp 20分 Watching Cowflix 木dp 3時間 解説を見てコンテスト4時間…

任意精度平方根と素数テスト (SRM821 CrossPrimesOut)

独特な要素が多く、結構印象深い問題。出題されたのは1年前。 出題はSRM 821 Div1の3問目。 問題 community.topcoder.com 正整数Xが1つ与えられる。その平方根を取って小数点を無視して、無限の長さの数字の文字列が得られる。 例 : sqrt(47) → 68556546004…

コミュニケーションの問題(COCI 2022 COI Mensza)

出典 COCI 2022 COI 問2 Mensza https://codeforces.com/blog/entry/103280 IOI系 ではコミュニケーションと呼ばれる独特な形式の問題が出題されることがある。 問題 4人の人物がいる Mr. Malnar マルナー先生 Alojzije アロイジエ Benjamin ベンジャミン Ce…

感想:COCI COI 2022 (Croatian Olympiad in Informatics 2022.)

Croatian Olympiad in Informatics (COI) 2022 - Codeforces 2022年5月30日にCOCIの最終ラウンド (COI) があった。Openコンテストに参加した。非公式解答を書いておく。 COCIについて COI は IOI のクロアチア大会および代表選考の大会である。COI はクロア…

(XIX Open Cup, Grand Prix of Siberia) Problem 11. Recursive Circuit 解法

再帰的な構造の迷路。考察が結構面白いので解法は読まない方がいい。 はじめに 2018年11月18日に開催された XIX Open Cup named afer E.V. Pankratiev, Grand Prix of Siberia の問11「Recursive Circuit」の問題と解法を述べる。 Open Cup Open CupはICPCに…

2021年終わり

2021年は1770問を読んで1270問の正解をした。解けなかった問題をほぼ復習しなかった。 それら問題の表を置いておく。ただしテスターとして参加したものは削除しておいた。コメントを書くのが面倒なのこの形式でメモしているが、ちょっとでもコメントがあると…

「競プロ典型 90 問」解いた感想

典型90問を全て解いた。 競プロ典型 90 問 - AtCoder 詩 年始から初めておよそ3週間やった。典型90問は2021年4月くらいからオンラインジャッジが利用可能だったはずなのでかなり時代遅れになってしまった。 せっかくまとまった教材があるのでやってみよう。 …

読書感想文「ガードナーの数学パズル・ゲーム」

「完全版マーティン・ガードナーの数学ゲーム全集」の1~4巻を読んだ。その1巻「ガードナーの数学パズル・ゲーム」の感想 シリーズについて 本書はMartin Gardnerさんが月刊雑誌「Scientific American」で書いていた「数学ゲーム」というコラムのまとめ。レ…

Parking Function の数は (n+1)^{n-1}

Parking Function、 駐車関数、木 Parking Function 台の車() が順番に駐車場に入ってくる。駐車スペースは個 () ある。 1番目の車から順番に駐車する。 番目の車は駐車スペース に停めようとする ()。このとき、空いていない場合は 、それでも空いていない…

全域最小カット (Stoer-Wagner algorithm)

Global Minimum Cut Stoer-Wagner algorithm 無向グラフに対して、あらゆるペア(s, t)のカットの中で最小の s-t-カットを求める。 問題 重み付無向グラフが与えられる。各頂点にSかTを割り当てたとき、一端がSでもう一端がTの辺の重みの総和をその「割り当て…

2020年終わり

プログラミングコンテスト 2020年は参加したコンテストをほとんどすべて記録することに成功した 参加したプログラミングコンテスト 320 読んだ問題数 1564 その内ACした問題数(終了後ACを含む) 1227 コンテストとは関係のないAC(オンラインジャッジ、過去…

Aizu Competitive Programming Camp 2020 Day 3 感想

ACPC 2020 Day3 コンテストサイト Aizu Online Judge Arena 解説 kaisetu - Google ドライブ

Aizu Competitive Programming Camp 2020 Day 2 感想

ACPC2020 Day2 コンテストサイト Aizu Online Judge Arena解説 ACPC Day2 解説 - Google ドライブ

JOI 2011 本選E JOI国のお祭り事情 解法

atcoder.jp 問題 辺に距離の付いた無向グラフがある。このうち、K個の頂点で祭が開かれている。 グラフと祭の頂点が与えられる。Q個の質問に答えよ。 質問 (s, t) : s から t へのパスで、最も祭の頂点に近づくときの距離を最大化し、その距離を出力せよ

JOI春合宿2020 ビルの飾り付け 4 解法

JOI春合宿2020 ビルの飾り付け 4 atcoder.jp www.ioi-jp.org 問題 2つの数列 A, Bが与えられる。それぞれ長さは2N。 長さ2Nの文字列Sを S_i = 'A' or 'B' とする。 Sに対応して、長さ2Nの数列Cを、S_i = 'A' ならば C_i = A_i、S_i = 'B' ならば C_i = B_i …

Codeforces Microsoft Q# Coding Contest Summer 2020 感想

Microsoft Q# Coding Contest - Summer 2020 に参加してQ#言語を書いて量子コンピュータを学んだ。量子ゲートを通すのはできたが機械学習は結局最後までBiasがどこに影響してくるのか理解できなかった。解いた問題だけ記録しておく。

「7つのツリー」と「1つのツリー」の全単射

元ネタ arxiv.orgツリーを「『リーフ』または『2つのツリーを持つノード』」と定義する。ラベルは無く、ノードの左右は区別する。本記事ではリーフをL、ノードを [x, y] と略記する。Coqによる定義は以下のようになる。 Leaf と Node が T (ツリー) の2つの…

高速なMOD演算 Barrett Reduction, Montgomery 乗算

% を剰余演算子とする。 を2以上の2^31未満の整数とする。 をたくさん求めたいときに、 について前処理をしておけば除算・剰余算を使わずに計算できる場合がある。 とくに、 が定数であるがコンパイル時に決定できない場合に高速化することができる(コンパ…

Nimberの乗法・Sqrt・逆元・二次方程式

Nimber(Grundy数)はその和と積が定義されている。 Nimber - Wikipedia Nimber和 これは単純に言えばxとyのビット毎のXORになっている。 丁寧に言うと次の性質がある。 Nimber和の性質1: のときこれらのNimber和は普通の非負整数の和(正確には順序数の和)…

Kotlin error: no set method providing array access

Kotlin の error: no set method providing array access は明示的にキャストして型を合わせると解消できる fun main(argv: Array<String>) { val d = LongArray(10) d[0] += 1 // error: no set method providing array access d[0] += 1L // good d[0] = d[0] + 1 </string>…

切片昇順で構築するConvex Hull Trick

問題 最初、 を空集合とする。次の2種類の命令を大量に与えられるので順に実行し、Find 命令の場合は値を出力せよ Add(a, b): に ペア を追加する Find(x): を求める オンライン問題、つまりクエリを先読みしない問題とする。 a, b, x は整数 -100000000 こ…

PAST アルゴリズム実技検定 感想

2019/12/14 にPASTアルゴリズム実技検定を受けた。2週間経って解法が解禁されたので感想を書く。 感想 難易度はサンプル問題のものとほぼ同じ。個人的には atcoder beginner contest の200~600がそれぞれ3問の15問に感じられた。 値段は8800円。問題のクオリ…

ECR78 F Cards 解法

Problem - F - Codeforces 解けなかったので復習 問題 整数n, m, kが与えられる。1/m の確率で成功する事象を独立にn回行う。成功した回数をxとしてpow(x, k)の期待値を MOD 998244353 で求めよ。n, m k 解法 i 回目の事象の確率変数を として、成功ならば …

数列を2つの等差数列に分割する

COCI 2019 #3 Drvca 問題 入力で整数列Aが与えられる。それを2つの数列P, Qに分割する。順番は並べ替えてもいい。P, Qを等差数列にするようにできるか? 解法 Aのサイズが4以下なら半分に分けて自明。 それより多い場合。Aはソートされているとする。 Aの小…

TopProver

問38 Midpoint https://top-prover.top/problem/38 Require Export Arith. Definition task := forall m n, S m < n -> m < (m + n) / 2 < n. まず初めに、Search _ inside Lt. SearchAbout "div" inside Nat. などで使えそうな定理を探す。 Phase 1, div2 x…

Coq と TopProver

TopProver 問37 Zero test https://top-prover.top/problem/37 Inductive iszero : nat -> Prop := | iszero_0 : iszero 0 | iszero_S : forall n, iszero (S n) -> iszero n. Definition task := forall n, iszero n <-> n = 0. まだcoqに慣れないので翻訳…