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の対応する位置の葉を更新する そこから登っていき, ノード…

CODE FESTIVAL(コンテスト)

本戦 A, B, C, D, E パパパッと解く もちろん後半に比べると簡単ではあるんだけども、C,D,Eは自明ではなかった D問題imosで解けなかったのダメかもしれない(StarrySkyTree並感) E問題は面白かった F 1時間ぐらい使う。無理。 G O(N4)はすぐに思いつく。ウン…

CODE FESTIVAL 2日目

(あさ) Mi_sawaとコンビニへ行く。買ったオレンジジュースを2秒で飲み干してた 非常に眠い (あさプロ) 適当にやる 頭が寝ているのが自分でもわかるぐらいに寝ていた 45分ぐらいたったらエンジンがかかってきた エンジンがかかってもCは厳しい 結局8位だった …

CODE FESTIVAL 2015 参加記(1日目、コンテスト除く)

1日目 適当に起きる 赤坂から行ったら微妙に迷う 飲み物をたくさん買った 早めに行っても暇しないだろと思ってたけど結構暇だった ついでに競プロ勢スタッフ各位もめちゃ暇そうにウロウロしてた、気のせいかも。 いろんな人と話す、プロコンオンサイトは夏合…

CODE FESTIVAL 予選B D問題

この問題はかなり苦労しました。というのも、動的SegmentTreeで解こうとすると空間計算量が非常に厳しくなるからです。 ですが、よく考えると動的SegmentTreeの空間計算量がO(log|区間の幅|)というのは変な気がします。なので少し考えてみたら、平衡二分木を…

作問リスト

JAG夏合宿2014 夕食。原案。 Kagamiz Irregural Contest 03 (KCS) 4題。爆散。 Yosupo Wetterberb (KCS) スペルは適当。5題。爆散。 Yosupo Contest 2 (KCS) 3題。爆散 CF #286 2題。 Problem - A - Codeforces Problem - C - Codeforces TTPC 5題原案。その…

CODE RUNNER 予選B

せっかく1位だったので参加記書きます。 最初10分で大体読みます。 1分ごとに5%減ということでgoogleに0.95 ** xのxを変えていろいろ突っ込んでみる。 どうやら減衰はかなり激しいが、max scoreなのでさっさと強力なAIを書いたら有利だなぁと思う、がこうい…

RBSTはコピー可能は嘘

まずこちらをご覧ください。 RBSTがコピー可能は嘘という疑惑 - よすぽの日記 これをちょっと変更すると以下のコードになります。 このコードを実行すると木の高さが5000近くに到達すると思います。 gist.github.com これを利用して、AtCoderのグラフではな…

RBSTがコピー可能は嘘という疑惑

コピー可能なRBSTを持っている人は以下の疑似コードっぽい動作をやってみてください。多分結構な確率で高さが300を超えます。 gist.github.com 永続が必要な時は赤黒木とか使うと良さそうです

HL decomposition+SegTreeのlogを1個消す

はじめに この記事はHL分解について書きます。 HL分解+SegTreeでパス上のクエリに答えると、最悪ケースで O(log2 N) per query ですが、これを O(logN) per query に改善したいと思います。 アイデア HL分解の詳細についての解説は省きます。たくさんネット…

天下一プログラマーコンテスト 2015 参加記

Klabさん主催の天下一プログラマーコンテストという大会に参加してきました。3位でした。 F問題 A, Bはペナルティが無いらしいし、問題を見る限り高々80点しか差がつかないので放置 とりあえず一番配点の低いFを考える 根へのパスに1を足すこととパスの値を…