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に通し番号振るのが難しすぎた) 帰国した翌日が情報実験第四(組み込み)の製作物発…

Grundy数

speakerdeck.com

Codeforces GYM 2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest J

数日掛けても全く解けなかった、提出コードも嘘っぽいものしかなくて、想定解っぽいものを得るために片っ端から読む必要があった 解法は知るとそんなに難しくないのだが、なんか異常に難しい。 問題概要 Dashboard - 2014-2015 ACM-ICPC, Asia Mudanjiang Re…

ARC 059 F バイナリハック

math, tokoharu, n_vip(と僕)の集合知によりmagicを使用しないO(N)解が錬成されました。 はじめに 解説のとおりに"なんでもいいので最終的な長さがM"となる操作の仕方を考えています。 操作列の条件 0add, 1add, delの3種類がありますが、とりあえずaddを1種…

New Year Contest お絵かき

まず黒の連結成分の個数で場合分けする。これをKとする 連結成分ごとに、a1, a2, .., amを使うとすると長さ[max(a1,a2, .., am), a1+a2+..+am]の連結成分が作れることに注目する。 すると、塗れる範囲というのはK次元平面上の長方形たちの和集合で表せること…

コンパイラ, 自分用まとめ

はじめに 文脈自由文法, LL(1), SLR(1) について書く 自分なりの理解を書きなぐってあります、間違ってたら教えて下さい。 文脈自由文法 A : B, C, d, e, F みたいなのが並んだやつ, ただし大文字は非終端記号(自分で定義した記号)で、小文字は終端記号(文字…

yosupo問題

yosupo問題 - Google スプレッドシート

TCO 2016 Round3A

AGC 001 F Wide Swap

まず転置をします。 すると、数列が与えられます。隣あう要素の差がK以上ならswap出来ます。転置した時に辞書順最小になるようにしてください。となる。この数列をa_iとします。 ここで、abs(a_i - a_j) < kならこの2つの位置関係がひっくり返ることはない。…

CODE FESTIVAL エキシビジョン Trax

赤色を1, 白色を0とする。すると4種類のコマは 0 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0 となる。要するに、左右と上下は独立。 ここで、線がつながってることに注目。すると、とある列/行だけ取り出した時の値は 0 1 1 0 0 1 1 0 0 1 ... みたいになってる。つまり…

ICPC国内予選

大反省。 反省点 チームとしての性能がヤバかった。今回で言えば、うまく動けば7問は解けていた(そもそもG以外は正しい解法が出ていた)のに、-2問、もちろん完璧に動くのは無理だけど、それでも許せるのはせいぜい-1問だと思う。 僕個人の話だけど、なぜかDE…

Matrix Calculator with パーサジェネレーター

Matrix Calculatorとは、知る人ぞ知るアホ問題です。 サンプルを見ただけで嫌になるすごい問題なんですが、今回はパーサジェネレーターで楽々解決を目指します。 使用したのは caper -- LALR(1) パーサジェネレータ です。C++でのソースコードが出力に出てく…

AOJ-ICPC Unfair Game

ゲーム系だから良問か?と見せかけて本質は場合分け。AOJ-ICPCは油断ならない。 解法 場合分け。