A 隣り合う要素をswapして数列をsortする最小回数は転倒数と呼ばれています B 2で割れる回数でグループ分けして←いらない 大きい順にマッチしていく という解法で解いた、1個目いらない 証明 xとマッチできる値たちのうち、x以下のものは1種類しかない、とい…

本選 対策 特になし 結果 ふつう 原因 Hの得意度は参加者の中でトップクラスだった自信があるため，Iを速やかに解ければ勝っていたと思うが，Iに90分掛けたためどうしようもないね 対策 転生？ りんごの挑戦状 対策 ペイントで様々な色を作って眺める トップ…

背景 突然寒くなって二度寝不可避 →出来る限りしんどくなく早起きしたい 目的関数 minimize しんどさ s.t. 早起き, 現実的な予算 10時起き安定を目標にする 環境 照明 空き巣対策に決まった時間に勝手に電気がつく機能があるのでオンタイマーとして使用，30…

C++ライブラリのストレステストを切り出しているという話 背景 プログラミングコンテストのライブラリには色々と要求されるが，一番重要なのはバグを少なくすることだと思う。 バグが無いだろうと信頼できればバグったときでもライブラリ以外の部分だけ疑え…

-D_GLIBCXX_DEBUGを付けて以下のコードを実行するとアサートにひっかかります(https://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor)。 struct S { vector<int> a; } S s; swap(s, s); どう</int>…

たまには記事を書きます，優勝したし(イキリ) 最初 何はともあれ木や数列にクエリを投げている100,000を探します。2題もありました。 M 実家のような安心感 クエリ3は見たことない気がします，有名？ 最初に実装を間違えてWA+MLEを貰いました。 理由はわから…

！！！解法のネタバレが含まれます！！！でも解説ではないです！！！ yosupo, sigma, sugim, maroonでJAGの夏合宿を1セット作りました 経緯 petrozavodsk(ロシア)では、毎年競プロの合宿が行われています。ロシアなので人外ばっかりいるので、セットもそれ相…

イロモノにしか見えないと思いきや案外いいのでは？ #include <bits/stdc++.h> using namespace std; using uint = unsigned int; template<class T> using V = vector<T>; //template<class D, class L, auto op_dd, auto op_dl, auto op_ll> (since c++17) template<class D, class L, D (*op_dd)(D, D), L (*op_dl)(D, L), L (*op_ll)(L, L)> str…</class></class></t></class></bits/stdc++.h>

色々隠蔽の方法を考えています。 これはなんかごついね #include <bits/stdc++.h> using namespace std; using uint = unsigned int; template<class T> using V = vector<T>; template<class OP> struct SegTree { using D = typename OP::D; using L = typename OP::L; static constexpr auto e_</class></t></class></bits/stdc++.h>…

#include <bits/stdc++.h> using namespace std; using uint = unsigned int; template<class T> using V = vector<T>; template<class D, class OP> struct SegTree { OP op; //f(data, data) -> data D e; //単位元 int n, sz, lg; //サイズ, 2^lgに拡張後のサイズ, lg V<D> seg; SegTree(V<D> first, OP _op, D</d></d></class></t></class></bits/stdc++.h>…

A 数列を2個に割って(l_max - l_min) * (r_max - r_min)をminimize →arc073.contest.atcoder.jp B 0, 1が書かれたグリッドなのでなにはともあれ二部グラフ →連結なら完全グラフにできそう →連結成分の個数 C とりあえずどこを使うか決まってたら？ →各場所に…

a * b + c * d * eみたいに+と*のみからなる式が与えられた時に，いろんな部分文字列を高速に評価するのが本質です。 こういう変なのはad-hocにやろうとすると大体大変だしバグると詰むんですが，SegTreeで強引にやってしまえばノード2個のマージに落とせる…

A うん(ループを1からn-2まで回しWA) B A, A+B, B, 0 → A, Bが独立 → AC C 数直線をジグザグして移動距離の総和を考える →区間が全部点だったら？ → ARC 087 Fに酷似，各[i, i+1]ごとに左右の個数に注目すると自明な上界が出る →区間が区間だったら？ →かぶ…

Um_nik回 A 制約がO((N+M)K)と言っている → K回幅優先できそうだしこれだろう → 一応sortじゃなくてnth_element使っとくか(logが消えます) B オッ乱択 → ランダムスワップの回数が増えるとどうなる？ → a[i] = iの要素数が減っていくんじゃないか？ → とりあ…

タイトルに反して実は作り始めたのは1.5年ぐらい前ですが… 結構安定してきたんで紹介をします。でも使うのはオススメできないかも(いろいろ壊れてるかもしれないため)。要するにせっかく作ったから見てくれというやつです。 準備 まずD言語のコンパイラをイ…

AB はい C ちょっとすき，条件がつよいから結構Noが多そう →サンプルの図を見ると次数>=3が2個以上がたいへんあやしく D ちょっとすき，値が大きい + 2進数を感じさせる演算 + maximize →これAGCで見た →上bitから貪欲するとDPです →250(は？)(きらい(手のひ…

いつもはvmware+linux+vscodeで出ていたんだけど，今回はwindows+wsl+clionで参加(したかった) F お金を配りながら移動していく，ただし移動するときには頂点ごとにしきい値がある →サンプル1を書いてみて想像をする →どうやらお金はありすぎて困ることはな…

E 解けません，全然解けません，おわりです D 問題の理解が大変 とりあえず最小値を求めないといけない →AGCで無向木の意味不明な性質を求められたらとりあえず直径に注目しろという法則があり →(直径+1)/2色は絶対必要なことがわかる →なので(直径+1)/2色で…

思考要素が無さすぎて書くことが… D 読めないね 読めた？(start gridは任意に選べると誤読をしていた) →16パターン全探索するだけだと思うんですが… →WA 間違いが見つからない&問題が読めないので誤読を疑う →誤読だね →WA →1*nで死んでいて →プログラムがバ…

D えーN<=32, 1e9, 構築，これは明らかにbase2で考えるタイプの性質であり →base2で考えると解けました E 誤差が非常に厳しい →微調整をしたいね →sqrt(x+1) - sqrt(x)は？だいたい1/sqrt(x) →全然精度足りないね →じゃあ(sqrt(x+2)+sqrt(x)) - 2×sqrt(x+1)…

A 素因数系？1018なのでgcd/lcmでなんかやるタイプだろう 条件は？ →とりあえずp, qは既約にする →gcd/lcm系なので素因数ベクトルで考える →まずb=10の場合は？ →どうやらqが2x * 5yならば可能 →さすがにqの素因数のなかでbに含まれないものがあったら不可能…

CD: 反射 E Nが2000 →数えるのにO(N2)かかる保存量がある？ 保存量 →転倒数を拡張？ →i個目とi+1個目を通る個数？ →a[i] > a[j]ならj-iを足す？ →全部ダメ 最終的な数列が定まると答えは簡単(転倒数) →最終的な数列はどういう形になるか？ → (W1, W2, ..., W…

精選過去問→AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita, Tasks - AtCoder Beginners Selection いろんな言語のまとめ→百花繚乱！なないろ言語で競技プログラミングをする資料まとめ - Qiita 既にあるやつ …

D言語で競技プログラミングをやってみたい…でもなかなか踏み出せない… 実はそんな人が相当数居るはず[要出典]なので，宣伝記事を書きます 主な対象読者 既に競技プログラミングをしており，C++を使っている Javaを使っている人も対象ですが，基本的にC++より…

随時更新 ☆ = 0.5★ 名前 ジャッジ対応 速度 使用者数 C++ ★★★ ★★★ ★★★ Java ★★★ ★★ ★★ C# ★★ ★☆ ★ D(DMD) ★ ★★ ★ D(LDC) ★★☆ ★ Rust ★☆ ★★★ ★ Go ★ ★★ ★ Python ★★★ ★ ★★ C++ 王道、大鉄板、これが使えないジャッジは競プロサイトにあらず ジャッジ速度使用…