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

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

平面グラフ メモ

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

6/8-6/14

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

天下一2012 予選B D問題 大爆発

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

6/1-6/7

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

5/25-5/29

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

ぽコン 感想

http://comp.yosupo.com/index.html で1.5時間のwebゲームを行いました プレイヤーが適当な数字を言って、下半分が言った数字分の点数を貰える。 多少のノイズがある(うさぎ)という感じ。詳しくはページ見てください。 サーバーは落ちずにバグも無かったです…

2015/4/20 - 2015/4/26

月曜日 英語2を寝坊した (非意図的な)寝坊は今学期初 悲しい 離散構造とアルゴリズムは2彩色をやった 火曜日 計算機アーキテクチャーはアセンブリをやった PIC32MXってMIPSだったんですね(要出典) 計算基礎論 これは面白い プロ1 forとかwhileとか 中身の記…

GCJ Round1A

A問題英語力検定。B問題1時間を(美容師の人数)分割して、i人目の美容師は(X+i/美容師の人数)時間目で切り始められるように考えればそれで二分探索が出来て終了なんか危なそうなのでBigint使ったC問題適当に尺取り

よすぽコン2解説

よすぽコン2 解説 お疲れ様でした。 A 数列swap 最初の数列の反転数をXとすると答えは max(X-K, 0) です 隣り合う要素を交換する時 左のほうが大きい -> 反転数は-1 要素の大きさは同じ -> 反転数は変化なし 右のほうが大きい -> 反転数は+1 となります また…