メモ

yukicoderでゆるふわgolf

Project Euler 401-450 解説

これの続き sugarknri.hatenablog.com何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ401 主客転倒でO(√N) D - Sum of Divisors 凸包テクでO~(N^(1/3))になるらしい。1乗のときの解説はここ 凸関数に囲まれた領域の中の格子点の凸包の…

特性多項式O(N^3)

自力で発明したのでメモ。たぶん既知のアルゴリズムと同じ? ref: ABC323G これの行列式を求めたい。ところでこれを というような、下三角+余分に斜め1列の形にできれば、行列式の定義通りにN!項の和をとるやつを dp[x][y]=x行目までの選び方を決めて、選ん…

Project Euler 351-400 解説

これの続き sugarknri.hatenablog.com何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ351 Dirichlet convolutionでO~(N^(2/3)) Dirichlet 積と、数論関数の累積和 | maspyのHP これくらい単純ならDirichlet級数に思いを馳せなくても普…

Project Euler 301-350 解説

これの続き sugarknri.hatenablog.com何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ301 Nimの必勝法を知っていますか?302 上からDFS303 BFSやるだけ D - Small Multiple 桁数を2倍にしたときどうなるかのチェックを挟むと早くなるら…

AGC063D後半

前半は自明です。後半は次の問題に帰着されますばかでかい正の整数Mがあります。でかすぎて値はわかりません。正の整数nを渡すとMをnで割ったあまりを返すオラクルが定数回使えます。 ax=b mod M を満たす最小の非負整数xをmで割ったあまりを求めてください…

Project Euler 251-300 解説

これの続き sugarknri.hatenablog.com何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ251 x^3+y^3=(x+y)^3-3xy(x+y)は受験数学典型 後半パートは特殊な形の数たちの素因数分解をosa_k法っぽくやるやつ 整数問題みたいにmodとかgcdとか…

競プロ小説

「競技プログラミングやろう!」 「なに?」 「競技プログラミング」 「プログラミングの勉強をしたいってこと?」 「それもあるけど、競技プログラミングはゲームだから」 「そうなんだ」 「そうだよ。……テンション低いな?」 「いや、何ヶ月か前にお前が似…

包除原理

■いわゆる包除原理 N個の条件を全て満たすものの個数を求めてください→N個の条件いずれかに違反するものの個数を求めてください、と読み替えて包除しがち 2乗のDPになりがち■min・max 期待値とかで使うらしい。ところでいわゆる包除原理とどういう関係にある…

ABC220Ex O(N^3)解法

これを読解した Submission #27805654 - AtCoder Beginner Contest 220参考にしたツイートこれやっと読解できた気がする適切に行列作ると求めたいものは二次形式の値が偶数になるような01ベクトルの個数になる問題の性質から作れる操作と直交変換かますこと…

Formal Power Series (FPS)

この記事を書いた4時間後に以下の記事が公開されました。これを読もうね-完- maspypy.com以上で本質情報は終了です。ありがとうございました。以下はおまけです。 まえがき この記事を読んでも競プロに強くはなれませんよ。 FFTで多項式乗算が高速にできる…

期待値

期待値= というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。 問題: S+1の状態があり、状態0から始めて、状態Sに到達したら終了。 1回の操作で状態iから状態jに遷移する確率がのとき、終了…

約数包除原理

というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。記号 メビウス関数 命題Pに対してをPが真なら1、偽なら0とする(アイバーソンの記法 - Wikipedia) やりたいこと がある。を求める。 例…

yukicoder 1962の解説の解説

writer解説が読解不可能でワロタという話を観測したので読んでみたら俺にも読解不可能でワロタ。FPSパワーを感じる学びがあったのでまとめる。出典「全ての要素がiであり、条件を満たすような長さ N の数列の個数」の母関数は になる。 したがって、「全ての…

ABC249Ex解説の解説

公式解説の読解に5000兆年かかったので、記号や論理の展開の仕方を全て俺好みに書き換えたものを記す。 オリジナル:Editorial - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249) 数列 に対して、終了条件を満たすまでの操作回数の期待値…

Project Euler 201-250 解説

これの続き sugarknri.hatenablog.com201 DP202 前座パートは中受典型 No.306 さいたま2008 - yukicoder 本編前半は3種類の直線をZ[ω]座標系で書いて考える 本編後半は素因数分解してDPなり包除原理なり203 やるだけ クンマーの定理を思い出してもいい204 O(…

Project Euler 151-200 解説

これの続き sugarknri.hatenablog.com「DPの状態数が少ないので行列累乗や高速きたまさ法で計算量落ちまーす」の類は実りがないので以降言及しません。151 DP152 1/kpを使ったら、pがどこかで約分される必要があります バックトラックDFSで全探索 指数でも分…

Project Euler 101-150 解説

これの続き sugarknri.hatenablog.com101 ラグランジュ補間 普通にやるとO(N^3) 補間に使う点が等差数列なのでO(N^2)にできる ラグランジュ補間したときの係数をぐっと睨むと求めるものをexplicitにも書ける102 多角形の内外判定 普通は半直線と線分の交差判…

project Euler 51-100 解説

これの続き sugarknri.hatenablog.com51 3の倍数で枝刈り52 有名問題すぎる53 尺取 rが小さいうちは境界を直接計算すると早い54 気合55 多倍長整数56 多倍長整数 嘘下界を使って嘘枝刈りで高速化57 連分数の最後に1項増やしたときの挙動を知っていますか 分…

project Euler 1-50 解説

間違ってたりより良い解法があったら教えて計算量は四則計算の回数。桁が増えすぎると壊れる 1 包除原理 これくらい手で解け2 愚直で解ける 項数を先に求めて行列累乗すればO(loglogN) 一般項を出して適当なmodを取ってCRTすると実質O(1)3 素因数分解の計算…

segment tree beats 覚書

これを読め rsm9.hatenablog.com ~終わり~ 以下ポエム ひとなのでさんによるこの記事を読むまでbeatsの理解が困難だったが、この記事を読むと全てを3秒で理解できた。 これ以前に存在していた記事で理解が困難だったのは、まずそもそもbeatsというデータ構…

a+b=a^b+2(a&b)の一般化

bit毎の排他的論理和を 、論理積を と置くと、 任意の非負整数 に対して が成り立ちます。 これは を観察すれば成り立つことが示せます。 この等式は競技プログラミングで非常によく使われるテクニックの一つです。 Yukiちゃんはこの等式を一般化して、 の形…

線形漸化式と微分方程式

微分方程式を微分作用素で解くやつ知ってる?f''-3f'+2f=0 の解は? 微分作用素をDとして、与えられた方程式は(D-1)(D-2)f=0 ここで一般に(D-k)f=0の解はC*e^kxなので、f(x)=C1*e^x+C2*e^2x全く同じようにして線形漸化式の一般項が出るんですよねa[n+2]-3a[n…

sum of multiplicative function

これはなに?Min_25さんの以下の記事を自分が読みやすいように書き換えたものです。 min-25.hatenablog.com Min_25さんによる実装はこちら https://ideone.com/9F9amv 要求知識 ・平方根の上下で分けるテク ・fenwick tree ・線形篩の"気持ち"を知っていると…

A Sequence of Permutations

a[i]=a[i-1]-a[i-2]の特性方程式が1の6乗根だからmod6で見れる、なるほどなぁという気持ちに— お気持ち表明を控える (@tk0_math) 2021年2月10日 ほんまか? は を満たすので、mod 6で見たいという気持ちで式変形をすると となって として を得る。よってで解…

yukicoder 1322

お断り:提出してないので間違ってるかもO(N^0.75) prime countingを完全に理解していてこれが解けないのは端的に言ってカスなんだよね・そもそもφはmultiplicativeなので、当然素因子ごとにわけて考えたくなる ・dp[i][j]=#{n | nの全ての素因子はPi以下、φ…

純粋培養競技プログラマが就職して1年

■スペック 国立大理系院卒 就職まで競プロ以外でのプログラミング経験なし 今はAtCoder橙 社会性破滅・就活破滅 英語壊滅 IT中小企業にどうにか潜り込む就活編はこちら sugarknri.hatenablog.com■1年経過時点での環境 pythonで機械学習やってる git使ってな…

指数型母関数

この記事は 37zigenさんによる以下の記事をもとに、お気持ちパートを自分にとってわかりやすいようにメモしたものです。 真面目な解説は書いていないので、そういうのを読みたい人は元記事の方をみてください。 37zigen.com ・物を数える気持ち:「互いに区…

コネと学歴は就活の役にたつ

就活記事です M2 5月 なんで就活の記事がM2から始まるんですか? 社会のことを何も知りません。人々はいつから就活をしているんですか? 実は修論どころか単位がそろわない可能性があって、就活どころじゃなかったし、この時点でもそれどころじゃない けどま…

FFT

何回見ても非再帰FFTの話が覚えられないのでメモ1のN乗根をgとする。 を離散フーリエ変換したい。 その結果は になる。ということで、全てのiについての が求められればよい。 これを頑張って計算する。 ところで、再帰FFTの気持ちには2種類あることをご存じ…

純粋培養競プロerが応用情報技術者試験に合格するまで

Q.これはなに笑 A.う笑 ・スペック 理系だが情報系ではない 競プロ以外のプログラミングをしたことはない ・2019年2月 基本情報技術者試験とかいうのを受けておくといいことがあるらしい 適当に参考書を1冊買う・2019年3月 とりあえずノー勉で過去問を1回分…