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は油断ならない。 解法 場合分け。

SRM 626 Hard

k o r e h a k u u h a k u 本質部分は、1~Kのうち、gcd(x, K)=1なるxの二乗和。(K <= 1,000,000,000) Kの素因数を列挙して適当に包除すれば良い。

SRM 622 Hard

Hardを頑張ってちょいちょい解いていきたい。メモ。 k o r e h a k u u h a k u [0, A)のフィボナッチ表現のi桁目の立っているbitの個数の偶奇がわかれば良い(いつもの) 桁を固定して考えると、直感的にフラクタル的な感じになりそう…と決めうちして考えると…

SRM 658 Med

概要 3*Nの行列が与えられる。 K回、以下の動作ができる。 異なるi, j, kを選ぶ。(1, i)と(2, j)と(3, k)の値を1ずつ減らす。 どういう行列なら、すべての値を0以下にできるか? というのが本質部分です。 これについて考えていたら、面白い結論が出たのでメ…

DDPC 参加記

前日 特に理由は無いけど酒を持って__math家にお邪魔する。飲酒は最高。飲酒したら気づいたら寝ていた。 朝 なんかよく眠れなかったし微妙に頭が痛いしコンディションが悪い。迎え酒で万事解決。 コンテスト 冷えました。 A問題: 記憶に無い B問題: 嘘解法を…

AOJ-ICPC 1000点 非幾何まとめ(ネタバレ含む)

Cellular Automaton以外を解きました。Cellular Automatonはあまりに意味不明なので解説を見ました。 Do use segment tree 問題, 解法ともにめっちゃ有名ですね。ライブラリチェック用問題。 HL分解かL/C Treeを貼ります。おすすめは後者 Common Palindromes…

CODE FESTIVAL 2015 沖縄

楽しかったです。今年は少し写真も撮りました。人の写真は顔の写ってないのを選びました。問題があったら教えてください。 1日目 めっちゃ早く空港に着く。そういえばラブライブ!で出てくる空港ってどっちなんやろと検索したら13話と5thは羽田で映画は成田…

Distance Sum

考察パート 求めたいのは木の重心みたいなやつ。 今見てる点に、markされた木の半分以上を持つ部分木があったらその方向に動く、みたいなのを繰り返すと行き着く場所。 頂点を1,2,...,nと塗っていって、その度にこの重心を求め、その点までの距離の総和を求…

ちょっと重いSegTree

http://www.adventar.org/calendars/850の3日目の記事です。 微妙に役に立ちそうで役に立たないSegTreeテクニック SegTreeで1点を更新するクエリを処理することを考えます。 これはおおむね SegTreeの対応する位置の葉を更新する そこから登っていき, ノード…