https://twitter.com/hogloid/status/284225774142251008 こんなことを言ったので 書きます 問題は、セグメント木を使う解法がおそらく楽で、セグメント木が問題の重要な部分で、JOIとかPCKでない問題、とします（JOIの問題とかみんな知ってる&解いてるだろ…

URL:http://www.codeforces.com/contest/258/problem/E 問題概要 N頂点からなる全域木がある。根は頂点1。 それぞれの頂点はあるリストを持っている。 M回処理をする。i番目の処理は、 頂点uiより下の部分木、頂点viより下の部分木 の頂点すべてのリストに、…

URL http://www.codeforces.com/contest/249/problem/C 問題概要 棚がN個ある。 それぞれの棚には、最初、未開封のハチミツ瓶がa[i]個入っている。 q回イベントがある。 それぞれのイベントでは、棚uからランダムにk個ハチミツ瓶を選び、それらを開けて、棚v…

URL:http://www.codeforces.com/contest/238/problem/C 問題概要 有向全域木が与えられる。2つ頂点を選んで、そこからすべての頂点へ辺の向きに従って到達できるように辺の向きを変える。 変えなければいけない辺の数をコストとすると、最小のコストはいくら…

URL:http://www.codeforces.com/contest/238/problem/B 問題概要 ある数列が与えられる。 これを、2つの部分列に分ける（どちらかが空でも良い） ある2つの要素の間のコストを、2つが同じ部分列に分けられているならその和、そうでないなら和に+hしたもの(h…

これからボチボチCodeforcesの和訳＆解説＆コードとかを公開していくかもしれません 基本的に、自分が受けたコンテストを1日後ぐらいに公開する予定です URL: http://www.codeforces.com/contest/238/problem/A 問題概要 ある数列について、隣接した空でない…

USACOの最近2年ぐらいはジャッジに載ってないらしいので適当に使っているC++用のテスターをupします(需要あるのか・・・？) USACO,解こう！（勧誘） http://www.usaco.org/index.php?page=contests Main内は、グローバル変数も初期化が必要なので注意 ちょっ…

なんか大会中にちょくちょく書く予定でしたがかけなかったのでまとめて書きます Day0-移動 朝は成田のホテルで。オリセンよりおいしい 空港に入る。写真とか取る。飛行機乗る。特にトラブルなし 時間的に、飛行機内では起きているべきな気がしたのでずっと起…

適当に書きます 朝起きる。荷物の最後の詰め込みする 車で成田まで行く 着く。生徒・チューターではsemiexpさんしかまだいなかった だんだん人が集まる。おすしさんがルールの翻訳を解説するPhase.有難いけどねむい その後はチューターsがIOI系問題の解説 壮…

今年のIOIは9月23日から29日にかけて開催されます。 日本からは4人の代表が派遣されます。選手はsemiexpさん、hziwaraさん、tozangezanさんと僕です。 海外から出る強い人は、touristさん、yeputonsさん、sevenkplusさんなど。（RedCoder級でもごろごろいま…

http://www.ioi-jp.org/ioi/2011/tasks/day2/elephants_jpn.pdf書いた。むずかった 平方分割、と言われても自明に思いつく程簡単でもない＆実装もそこそこ （まあでも平方分割の実装としては標準的な気がする）象を最初の方からB個ずつ分ける。 それぞれの象…

Supercon 提出コード /******************************************************************* SuperCon12: Template for input output procedures file: sc12_template2E.cu by S.Kishimoto and O.Watanabe Aug. 17, 2012 ver.2 by T.Endo and A.Nukada Aug…

http://www.spoj.pl/OI/problems/QTREE3/ 問題概要 Nノードからなる重みなし・無向全域木がある。 ノードには黒・白の色がある。以下のクエリーに答えよ ノードiの色を変える（最初はすべて白） ノード1からノードvへのパスのうち、最もノード1に近くて、色…

http://d1yjytat4ps3ku.cloudfront.net/final-AeF9DxEp/apio2012-jpn.pdf たぶんここら辺に日本語の問題文があります 解法 10%：全探索にしてはオーダー大きいし謎 50%：整数計画＋多少の枝刈で通った。オーダーよく分からない 100%：変な貪欲+DP 別解多分あ…

名前のよくわからないデータ構造について紹介します。 そのデータ構造は、ある順列を受け取り、 深さ0ではその順列をそのまま配列にして、深さ1では中央mdで深さ0のときの配列を分け、ｍｄより小さいものはmdより小さいindex、mdより大きいものはmdより大き…

なんかPKUのコードあさると時々見るSPFAというアルゴリズムを紹介します。 SPFAは単一始点の最短経路アルゴリズムで、負辺があっても動作します。 shortest path faster algorithmとかいうたいそうな名前がついてますが、普通はダイクストラに比べ遅いです。…

みんな大好き永続赤黒木！！！！！！ 書いてみると、むちゃくちゃなほど実装重いというわけではないです。重いですが。 正直言って書くより何故赤黒木がうまくいくのかを理解したほうがいいとおもう(今更)赤黒木の実装の本質は、hosさんのスライドの解説とほ…

Day0 学校の終業式にちゃんと行き、その後NTTDataの研修センターへ行く 適当にプラクティスをやって、オリンピックセンターへ向かう 最初の講義はｈｏｓさんが担当で、決定不能・NP困難・多項式時間で解ける問題の紹介をやった 夜はjubeat板とかを使ったり、…

ほげほげしてたら代表になりました 詳細は後で書くかもしれません 明らかに成績4位でだいぶ恥ずかしい点数しかとれなかったんですが、代表は代表ですし、これからがんばってIOIでは金・一桁順位とります

O(N^2)アルゴリズムはやっぱり見つけられませんでした。ごめんなさい・・・ですが、なんとかATCODER上では通しました。 枝刈りは、 それぞれの星で写真を取れる最大の長さで、長さを固定してやるのですが、そのとき、その長さをとる星は必ず取らなければなら…

問題文はこちら http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270解説にあったみたいに永続を使いました。永続書くのは初めてです 二分探索木はこわいし建て方よくわかったなかったので、せぐつりー風にしました。 ノードごとにlogN個のノー…

とりあえず書きます 到着する 名刺とか配る・もらう。てふさん一目見ただけですごいでかかった ぺろりん投げるのおもしろい practiceはまともに練習しなかった気がする きゅうりの帽子は武器にしたりできておもしろい 講演去年よりだいぶよかった PKUの英語…