KUPC 2018

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

JAG夏 2018 Day2 準備記

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

遅延Segtree2

イロモノにしか見えないと思いきや案外いいのでは? #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>

遅延SegTree

色々隠蔽の方法を考えています。 これはなんかごついね #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>…

一般化(抽象化?)Segtree

#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>…

CF #500

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

ICPC Domestic G: 数式探し

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

AGC 025

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

CF #485

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

D言語の競技プログラミング用ライブラリを作ってみた

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

CF Avito Code Challenge 2018

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

ARC 098

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

AGC 024

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

GCJ R2

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

Yukicoder #191

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

CF #483

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

ARC 097

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

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた

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

D言語で競技プログラミング

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

競プロ 言語調査

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

CODE FESTIVAL 2017

当日朝 睡眠失敗。悲しいね 昼 早めに行く 周りがwafrelka, sigma, wo, tozan, hogloidでウンウンこれもまたdiversityだね 本戦 とりあえず1000点まで全部読む Fが面白そうだね(一番最初に構築ゲーやるの無謀すぎないか?)→しばらくいじったりエスパー発動し…

JOI 春合宿 2017 Broken Device 解法(未検証)

概要 略。 解法 この問題は、150 * 60の$\mathbb{F}_2$ matrixであって、「行ベクトルを110個選んだときに、どう選んでもrankが60になる」ような行列を構築すれば解ける。 ところで、 https://arxiv.org/pdf/1404.3250.pdf を見ると、ランダムに110 * 60選ん…

JOI Open 2013 Synchronization 人間的解法

JOI Open 2013 Synchronizationの人間的な解法を紹介します。 問題概要 略 解法 ある辺を追加すると、左右で互いに情報を交換します。この交換する個数を高速に求めたいです。 左が情報をa個、右がb個持っていて、そのうち共通のものがc個あったとします。 …

ICPC World Final 細かい話

practice 今までのworld finalの問題6問セット*2時間だった。 1: 知らない 2: 球形の穴が沢山空いた直方体が与えられるので、k等分 3: 知らない 4: 重実装幾何 どぼじて 5: 平面状に点がたくさん与えられて最大クリーク 6: 420と見せかけて状態が少ないハフ…

AGC 014 F Strange Sorting

AGC 014 Fを解きました。 解いた後に解説動画を見たら全然違いました。ゴリ押しです。 まず、数列を-1倍してよくある各点までのLISを求めるやつをします。 たとえば[3, 5, 1, 2, 4]ならば、[1, 1, 2, 2, 2]です。これは"初めてその値が高い項になるのは何回…

「みんなのプロコン」

久しぶりの参加記 コンテスト前 うっかり遅刻した(いつもの)(ごめん)(反省がない)(受付時間で差を付けろ)(鈍足) なんかsigmaとsugimにArrangement Tickets(JOIオープン)の僕の解法は嘘解法だとかいう言いがかりをつけられる。 コンテスト開始 問題を読んでる…

maroonさんのお正月問題

あけましておめでとうございます!↓はお正月問題のリンクです。新年早々重い問題を解きたい方はぜひやってみてください。https://t.co/GH0VwifmvK— 最高の夏 (@maroon_kuri) January 1, 2017 ヒント1 : FMTは使わない(MODが変な意味はない) ヒント2 : 式の形…

Fenwick Treeの定数倍高速化

Fenwick Treeの定数倍高速化 この記事はrogy advent calenderの3日目の記事です。 日本時間では4日になっているような気がしますが、地球上にはまだ3日の部分が残っているのでセーフです。 (本当は丁寧に書くつもりだったのですが、時間がないので、プロコン…

Codeforces Technocup F: Dirty plates

概要 スタックが3こある 1 -> 2はa個まで一気に運べて、2 -> 3はb個まで一気に運べる。sortできるか? 解法 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 空白 まず、愚直にシミュレーション…

ICPC Bangkok 2016

ICPCのBangkokアジア地区に参加してきました 出発まで なんか中間を休むために理由書が必要だった ライブラリの準備に手間取った(25枚以内で、チーム名と通し番号が必要)(pdfに通し番号振るのが難しすぎた) 帰国した翌日が情報実験第四(組み込み)の製作物発…