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

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

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

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

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

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

この問題はかなり苦労しました。というのも、動的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題原案。その…

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

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

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

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

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

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

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

つらい

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

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らしいです。 居心…

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

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

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

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

平面グラフの性質についてのメモ 随時更新 vは頂点数, eは辺数, fは窓数 ここでfには、一番外側も含む f = e - v + 2 非常に有名 証明は変数に関する数学的帰納法？ 3f <= 2e 全部の多角形に接する辺の個数の和が2e(以下)であることと少なくとも一つの多角形…

月曜日から金曜日 記憶がない ラブライブ！The School Idol Movie 尊い。 μ's Fan Meeting Tour 2015〜あなたの街でラブライブ！〜 ライブビューイング てっきりライブパートをやるのかと思っていたがトークパートのみであった あと映画を見た(2回目) 尊い。…

ちょくだいさんにオススメされた問題 難しいのでビームサーチをする。キーは普通に残りのマスの個数でやった。large/00_doubleslash_large_00.txt というケースが強い ビーム幅は100では通らず200では通ったhttp://tenka1-2012-qualb.contest.atcoder.jp/sub…

月曜日 英語3 遅刻した気がする。来週中間とかなんとか、死。再履修という逃げ道があるため何もやる気がない。 離散構造とアルゴリズム 難しくなってきた。そろそろまじめに受けよう。 基礎集積回路 死。 火曜日 計算機アーキテクチャ 今週はちゃんと出た。…

月曜日 この日は寝不足だったため全授業が崩壊した 英語3 ちょっと遅刻した記憶がある。相も変わらずあまり面白くはない。 離散構造とアルゴリズム 正直あまり聞いていなかった、教科書を読んでいた。7割ぐらいは知っているないようだが残りの3割がなかなか…