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を足すこととパスの値を…

TDUCTF KeyGeneretor? 200pt writeup

まずは実行 なるほど、どうにかして4を実行しなさいってワケね IDAに突っ込む 終。 gdbでウェイすると簡単な条件分岐だったので、 set $pc = hoge で無理やり4を選ぶ。 4を選ぶとprint_flagという関数に飛んでいたので大勝利っぽい 人間を舐めている 終。 pr…

NETWARS2015 参加記

SANSさんのNETWARSという大会?勉強会?に参加してきました。 1日目 大手町のコンビニにはコピー機が少ない コピー機を諦め行こうとしたら普通に迷って遅刻 大学ごとに席が分かれているのコミュ力に問題がある人にはよかった。 困ってヘルプを求めたらチュー…

テスト

つらい

TCO 2015 R2C onsite

行ってきました。 コンテスト自体はMedにああもうこれわかんねぇなが出たため終了。easyが1つも落ちてない部屋だったためキレそう。2D頑張ろうな。 ハッカソンは面白かった。

Digit考察

f(2) = 1 f(i+1) = 2*(L^{f(i)} - 1) / (L-1) と定義する。 2*L^{f(N)} - 1 % M を求めよ。 という問題になるはず。 L-1の逆元が存在しないことが多々あるため終了する。どうしたものか L^{f(i)}-1 / (L-1) として考えずに (1 + L + L2 + ... L^{f(i)-1}) と…

秋葉原製作所レポ

今日はすぬけコン終了時に秋葉原にいる必要があったため、 秋葉原製作所(http://www.seisakujo.com/)というところで出ました これは有料貸しスペースのようなもので、同人誌とかを書く人がターゲットのようです。 それ以外の用途でも全然OKらしいです。 居心…

Golden Week Contest 2015 感想

A: 得点 はい。 B: アリ巣 ラングトンの蟻を見たことがあれば簡単。 C: Snukeと対戦 こういう系ゲームで一般的な対称に置いておくテク D: 最短路問題 インタラクティブ E: シフト塗り分け 偶置換とポリアの定理と仲良くないから解けなかった。残念。 F: 誕生…

ポリアの数え上げ定理

(x1, x2, .., xn) にそれぞれ1..kの値を割り振る。 (x1, x2, .., xn) -> (x2, x3, .., xn, x1)のようにrotate出来て、その動作によって同じくなるものは同じと考える これの数え上げをどうするかという話。 これは、 (x1, x2, .., xn) = (x1, x2, .., xn)と…

UTPC2014 感想

やっとUTPC2014が全部解き終わりました。 I: 盆栽 まあ…はい… ETTはあんまり真面目に整備してなかったためバグらす。 http://utpc2014.contest.atcoder.jp/submissions/371356 A: 二重否定除去法則 面倒なやるだけ http://utpc2014.contest.atcoder.jp/submi…

6/22-6/28

映画を見た。 ICPC国内予選に出た。 CFのレートが赤から黄色くなった。悲しい。

ICPC国内予選感想

5完で6位でした Cを読んだ ここで普通の構文解析のを書くのは"""素人"""、僕は去年のアジア予選で学んだ 再帰関数を書いて返り値をvectorにすれば綺麗に書けそう ABが通っていたので書き始める サンプルが通る ちょっと怖いので怒りの#define int long long…

6/15-6/21

財布忘れハプニングがあって靴下から金を借りた 映画を見てからアニメを見るとまるで別のアニメを見ているかのようなほど世界が変わる。 本当はキモオタク的長文を書きたいような感じはあるのだけど文才がない。 なるほど尊いという言葉はこういうときに使う…