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

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

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

speakerdeck.com

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

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

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

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

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

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

赤色を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 ... みたいになってる。つまり…

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

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

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

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の素因数を列挙して適当に包除すれば良い。

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

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

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

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