AGC028のB問題 Removing Blocks

なんか最近難化傾向にあるような... D - All Your Paths are Different Lengths 1. 以下のようにノード 間に長さ の二つの辺を貼ると , の時のグラフが表現できる. 2. をサイズが2の累乗の区間の和で表すことを考える. ( ルール : サイズの大きい区間から貪…

競プロとは関係ないですが。授業で聞いて面白かったので実装してみました。 アルゴリズムの解説(準備) 素数 を決める (十分大きな数) を求め、 と互いに素な数 を1つランダムに選ぶ。 となる を求める。( の特殊解を求めることと同値 ) (暗号化) 平文 (数字)…

E - Or Plus Max 高速ゼータ変換の問題。といっても貼るだけの問題ではなく、集合や演算を自分で考察してうまくテンプレに落としてやる必要がある。 また、やってることはbitDPなので言葉を知らなくても解ける(僕はコンテスト中には解けてない) この記事では…

解けなくて悔しいので記事に。考察の流れとかも書いておく。 排反をとるというのがtwitterで見ててわかりやすそうだったので実装。bitflyer2018-qual.contest.atcoder.jp 考察した(ダメ)解法 1. : 左端と真ん中を決めて右端の数を二分探索で数える。左端と真…

気が向いたので作ってみました。固有値求める機能とかも追加したいけどとりあえず後回し。四則演算,累乗,ビット演算,転置,行列式,逆行列とかその辺は実装しました〜

D - 食塩水 解いたのでメモ。悩んだけど、どうやら典型の模様。 蟻本p132の「平均最大化」とほとんど同じ問題。 最初は、ナップザック問題っぽいなぁと思って、DPを必死に考えてたけど よくよく考えてみれば以下の式は別物。 本問 : ナップザック : ~ アルゴ…

700点問題のD問題。むずかった。 D - Worst Case 高橋君のとった得点を とする。 高橋君よりスコアの小さい最大の人数を求めたいので、1つ目のコンテストが高いスコアならば、2回目は低いスコア(逆もしかり)というように掛け算のペアを作ってあげる。(考察1)…

競プロ用の整数周りのライブラリ(言語はc++14用) 使用可能なメソッド 1.素数関連 エラトステネスのふるい 素数かどうか判定 素数列挙 n以下の素数の個数 2.約数倍数関連 素因数分解 3.階乗累乗関連 ※数が大きいのでを法としてmodをとっている。 n階乗 mod割…

競プロ界ではとても有名(?)なダイクストラ法。 典型問題からちょっとひねった問題で個人的には良問だと思った。 codeforces.com 問題文の要約 (訳に脚色入ってます。) 個の町と本の道があって道には通行料が存在。コンサートが全ての町で行われるが、チケッ…

初投稿です。個人的にはアルゴリズムも実装も大変だったので書き残しておきます。 agc021.contest.atcoder.jp乱数で決まるは半径の円の内部。穴は1辺 の正方形の内部の領域に存在する。 がめちゃめちゃ大きいので、穴の近くには滅多に落ちない。全体図穴を頂…