2014-01-01から1年間の記事一覧

CF #284 Div1 D. Traffic Jams in the Land

lcm(2,3,4,5,6) = 60なので60個SegTreeを作れば良い seg[l][r][k] = l~rを通るのにかかる時間、ただしlに突入した時点での時刻%60はk CFはこういうのをTLE2sN=100000で出してくるの怖い

Good bye 2014 E New Year Domino

Problem - E - Codeforces RMQでドミノを伸ばせるだけ伸ばして遅延評価SegTree

CODE FESTIVAL 上海ツアー参加記(4日目)

朝起きる。集合時間まであと30分。朝食が食べられなくて非常に残念。 まぁ間に合うだろと思って電気ポットでお湯を沸かしその間にお風呂に。お風呂を出て紅茶を飲む。飲んでたら電話が鳴る。ちーん(笑)。ガイドの人に遅いと言われた。最悪集合時間電話起きを…

CODE FESTIVAL 上海ツアー参加記(3日目)

起きる。9:45。朝ご飯を食べ損ねたと思ったが実は10:30までだったらしい(朝食の時間が書かれた紙を紛失していた)、やったぜ。 mathさんと朝ご飯を食べる。やっぱり美味しいなあ。 昼ご飯。また回転皿が同じ物に見える…。メインは北京ダックだった。これは本…

CODE FESTIVAL 上海ツアー参加記(2日目)

朝起きる。お風呂に入る(2回目)。 適当に部屋でだらだらして朝食を食べにいく。ビックリするほど朝食は美味しかった。ビックリ。 しおりに書かれている時間と本当の集合時間が違うとかいう意味不明な罠によって今何時か知っていますかした この日はコンテス…

AOJ-ICPC2405 姉妹港

1000なだけあって非常に悩んだけど、面白かった。 すべての道は交差しないというのが非常に強い制約。 まずは円環はNGなので切って伸ばして列にする。 これのおかげで区間DPとして考えられる。 また、n % 2 == 1の場合は答え1になる事と(r-l) % 2 == 0となる…

CODE FESTIVAL 上海ツアー参加記(1日目)

朝5時30分ぐらいに家を出る。数学演習のレポートを出しに大学へ向かう。 無事空港に到着する、遅くも速くもないくらい。 空港で朝飯を買って食べて飛行機に乗る。機内食が非常に美味しかった 上海に着く。ちょっと空気が汚れている気がしたが、殆ど気になら…

HackerRank Weekly12 White Falcon

Programming Problems and Competitions :: HackerRank 問題は登録しないと見れなかったりするのかな? 問題概要 N頂点のツリーが与えられる、頂点はそれぞれf(x) = ax+bという形で表せる関数を持っている 二種類のクエリが飛んでくる クエリ1.変更 u, v, a,…

Do use segment tree

Do use segment treeだけどHL分解は怖いしやり方がよく分からないのでSegment Treeは使わずLink-Cut Treeを使用。 めちゃ雑に書いたけど想像の10倍ぐらい速かった。いつかSplay木のポテンシャル云々を読んでおこう… 平衡二分木の子が左右入れ替わっても値が…

CF #284 Div1 C Array and Operations

問題を読むと明らかにフローだし辺の張り方が明らかに二部グラフだし… 本当にフロー流すだけ問題。 #include <iostream> #include <cstdio> #include <complex> #include <set> #include <vector> #include <stack> #include <tuple> #include <algorithm> #include <cassert> #include <cstring> #include <queue> using namespace std; typedef long lo</queue></cstring></cassert></algorithm></tuple></stack></vector></set></complex></cstdio></iostream>…

CODE FESTIVAL 本戦 I - Shapes

I: Shapes - CODE FESTIVAL 2014 決勝(オープン) | AtCoderこの問題は 平面走査をして木を作る LCA の二つのフェーズに分かれています 平面走査 解説にはBITでごり押しすると書いてありますが、 平衡二分木ライブラリがあれば割とよくあるタイプの木になる…

Tampopo Machine 解法

CPUが200倍の速度だとしたら通る解法を考えます 200倍速くしようとします 出来ない(◞‿◟) CPUが20倍の速度だとしたら通る解法を考えます 20倍速くしようとします 出来ない(◞‿◟) CPUが2倍の速度だとしたら通る解法を考えます 2倍速くしようとします 出来る…

平衡二分木を使う問題

平衡二分木は、定数倍は遅いしコード長がアホみたいに長くなりますがとても強力なデータ構造です。 そんな平衡二分木を使う事が最近多いので、使った問題を紹介します。 木の種類 RBST 軽実装かつコピー可能な(追記:不可能です。)プロコンなら最強感のある木…

ICPC ジャカルタ大会参加記(コンテスト編)

ICPCのジャカルタ大会に参加して来ました。コンテストについての記録を残します。来年以降の参加を考えて居る人のためになれば幸いですね。環境OS:Windows, CPUとかメモリはまともPCのスペック:Core i3か5、メモリは4GB?至ってまともコンパイラ:MinGW、コン…

CODE RUNNER参加記

やったことD言語で参加しました最初APIごとにそれを叩いて結果を返す関数を作るとりあえずテストとして色々召喚してみる(SSS石とか使っちゃった)モンスターリストはファイルサイズがでかくて怖いどうせ沢山の種類の石を使って召喚したほうが効率がいいんだろ…

ひとりICPC in インドネシア2013

インドネシアに飛ぶので過去問を解いた。10:52 ~ 15:52 AC Penalty 8 1192(932+260) A B C D E F G H I J 11(+3) 299(+6) 43 33 - 79 61(+1) 235(+2) 171(+1) - 2位(Bが通せてなかったら5位)初liveachieveなので 別の問題にsubmitしていた*3 gccだとコンパイ…

Splay Tree

スプレー木についてのメモ(1)普通のrotr, rotlを実装する(2) zig->そのまま zigzig->親を回転,自分を回転 zigzag->自分を回転*2 でSplayを実装(3) merge->左の木のMaxをSplay,左の木のRootの右に右の木のRoot split->k番目をSplay,そのまま分ける

CODE FESTIVAL参加記(まじめ)

CODE FESTIVALに参加してきました。前日 kagamizに会おうと言われたので会う。 神田明神に行ったり竹むらに行ったりkitayutaと合流したりわふれるかと合流したりカレーを食べたりした。 DDRは12のクリアが増えた。半年ぶりにビートおたくしたら四段がギリギ…

CODE FESTIVAL参加記

ABCDEF: やるだけGHIJ: N P 困 難

フィボナッチ数に詳しくなりたいあなたへ…

http://fibonacci.yosupo.com とても すばらしい ゲーム

Code Formula参加記

Code Formulaの本戦に行ってきました。 結果は全完で2位、嬉しかったから参加記とか書いちゃう。東京テレポート行ってレジャラン行ってDDRして肉食べて会場に行った。 AB:やるだけC: 誤 読 は 怖 い 結構時間が吸われた、C++で一行読み込みの方法がわからな…

アイマス

バンダイナムコチャンネルでアイマスを見ました ラブライブとはそんな似てなくね?って思ったけどどうなんでしょう好きな曲 自分REST@RT ごまえー♪ READY!! 蒼い鳥

4つの数字から10を作るwebサービス

今4つの数字から10を作るのが流行っているので、自動で解いてくれるのを作りました http://komati.yosupo.com A,B,C,Dに入れた数字と+-*/と()を上手く組み合わせて、Xを作ってくれます http://komati.yosupo.com/?send=on&d1=1&d2=2&d3=3&d4=4&x=10 分数も出…

KIC 003 解説

総評 antaさん全完おめでとうございます!(47:54) tanakhさん全完おめでとうございます!(102:34) 全完が2人しか居ないのは正直予想外でした。が、問題ごとの正解者数についてはおおむね予想通りです。 A問題 (FA:kyuridenamidaさん 02:08) CDに、曲を長さが…

D言語to競技プログラミング

最近ちょいちょいCode forcesの過去問とかをD言語で解いてるので、そのメモStopWatch(乱択とかでTLEギリギリまで回し続けるとか) import std.datetime; int main() { StopWatch sw; sw.start(); while (sw.peek().msecs < 1800) { hoge(); } return 0; } こ…

2014JAG夏合宿4日目 D問題:夕食 解説

原案、解答、問題文を担当していました。とこはるさんが解法、解答。まずこの問題、一番辛いところは自炊パワーが自炊でも食堂でも変動する事なのでなんとかします。自炊パワーは 自炊で+1、食堂で-1ですが、コレを自炊で+2、食堂で変動無し(±0)にしたと考え…

競技プログラミングについて

私半年以内にレッドコーダーになるよ!!!違ったら埋めてもらっても構わないよ!— ドイツ語は消えろ (@yosupot) June 4, 2014 私半年以内に(TC)赤くなるよ!ならなかったら埋めてもらっても構わないよ!— ドイツ語は消えろ (@yosupot) August 29, 2014

askに対する解答

年上でもネットでは丁寧語さえ使わないことについて、何か持論があるようですのでマジレスお願いします という質問に対する解答です。 こんな質問が飛んできたのは数日前にそのようなツイートをしたからかなぁ… と思って漁るとネットで会ったことも無い先輩…

アジア予選までにCFDiv1CDE150問とくるくるくるりんを解きます

冷静に無理なので150問にしました。くるくるくるりんが150問分だからしかたがないね。 http://codeforces.com/contest/444/problem/C http://codeforces.com/contest/444/problem/D http://codeforces.com/contest/429/problem/C http://codeforces.com/cont…

ICPC国内予選2014参加記

国内予選にチームkatouで出ました、11位でした。 学内3位なのでアウト、世の中にはワイルドカードなるものが存在することもあるらしいので期待 方針 2人がtwitterとかあんまやってないのでAさんとNさんで Aさん:A問題、幾何 Nさん:B問題、幾何 僕:Cから出来…