hogloidのブログ

へなちょこ

Codeforces #148 div1A,div2C Not Wool Sequences

CF

これからボチボチ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内は、グローバル変数も初期化が必要なので注意 ちょっ…

IOI2012-適当に

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

直前合宿

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

IOI 2012に行ってきます

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

IOI 2011 Elephants

IOI

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…

SPOJ 2798 Query on a tree again!

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

APIO 2012 Guard

JOI

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

なんかのデータ構造の紹介(実はWavelet Treeだった)

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

SPFAの紹介

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

2012合宿Day4 Copy and Paste

JOI

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

JOI合宿・詳細

JOI

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

JOI 合宿さまりー

JOI

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

合宿 Starry Sky

JOI

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

The L-th Number

AOJ

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

2012年 JOI本選

JOI

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

PKU 3517 And Then There Was One

PKU

id:kyuridenamidaのところ(http://d.hatena.ne.jp/kyuridenamida/20110724/1311503122)にはシミュレーションでは間に合わないとか書いてありましたが間に合いました(漸化式とか知らない無知) ただ、普通にシミュレーションするんじゃなくて多少工夫しま…

マクロ・typedefについて

自分のコードを見てみると、マクロやtypedefをさも当然のように使っていてしかもその定義がないのは不親切だなあと思ったので書いておきます #include<stack> #include<queue> #include<deque> #include<numeric> #include<functional> #include<list> #include<cstdio> #include<cstring> #include<set> #include<map> #include<cstdlib> #include<cmath></cmath></cstdlib></map></set></cstring></cstdio></list></functional></numeric></deque></queue></stack>…

JAG 2011 Day3

感想:すっごい楽しかったです 大体自分のレベル〜それより上ぐらいの問題でやるだけ感もなく楽しめました 英語問題でしたがいつもより英語の不快感が無かった気がします。 Japanese English??? A N,Mが小さいので全パターン試します int main(){ int n,m;sc…

3250 BadHairDay

PKU

(id:Respect2Dさんの方が圧倒的に頭がいい解法です) なぜかsegtree解法しか思いつかなかった。最初はO(Nlog^2n)でやろうと思ったけど TLEで死亡しそうだったので多少工夫 もし左のノードみてあったらそれをすぐ返してしまえーというだけの話だけど struct …

JOI 合宿 abduction

JOI

DPでし。まず、証言から、どの向きにどういう順番で進んだかが割り出せる。 その後、X成分とY成分に分解。ごにょごにょ int w,h,n; char angle[10005]; int mod=10000000; int main(){ FILE* fp=fopen("out.txt","w"); scanf("%d%d%d",&w,&h,&n); vi yoko,ta…

JOI 合宿 Pyramid

JOI

DPでし。高い所からゴリゴリやります。 priority_queue使っても面白そうですがlogの分だけTimeLimitが危なそう vvi buf; vector<vp> top; int w,h,n; int main(){ FILE* fp=fopen("out.txt","w"); top.resize(3001); scanf("%d%d%d",&w,&h,&n); buf.resize(h,vi(</vp>…

PKU3092 Non-divisible 2-3 Power Sums

PKU

数N( 2^a*3^bの和で表せ。ただし2^a*3^bのどれかがどれかで割りきれてはいけない 探索します。メモ化しなくてもOKです まず、nが2で割りきれるとき、すべての2^a*3^bのaはa>=1なので、 n/2の場合に帰結できます。 nが2で割りきれないとき、2^a*3^bのうち一つ…

KUPC 2011

感想: 難しい!!! 正直5問は解けるだろうとタカをくくっていましたが見事に打ち砕かれました 10位目指すって言ってたのが懐かしいです Problem A やるだけです。KUPCの文字をそれぞれカウント int main(){ char s[305];scanf("%s",s); int len=strlen(s);…

JOI2009合宿 地域(Regions)

JOI

2分探索→葉っぱからできるだけ大きく切ります 分割した数+1が地域の数になります。 int n,m; vector<vp> g; int dived=0,maxlen; int dfs(int v,int p){ //most distant from root int son=g[v].size(); if(p!=-1) --son; if(son==0) return 0; vi dist;dist.res</vp>…

JOI2009合宿 DNAの合成

JOI

DP テストケース8〜10あたりだとTLEっぽくなるので想定解ではないはず O(20*LlogN) (fprintfになってるのは手動比較のため) char tmp[160000]; int main(){ FILE* fp=fopen("out.txt","w"); int n;scanf("%d",&n); scanf("%s",tmp); string make=tmp; int le…

PKU 2951 Cake cutting

PKU

w*hのケーキをm個の長方形に分割。 w,h,m まあDPやるだけです 3分探索を入れてかっこつけましたが普通に3分探索しなくても通ると思います (実は毎回計算しててTLEだったので無理やり3探いれましたごめんなさい) int main(){ REP(i,21) REP(j,21) REP(k,21)…

2831 Can we build this one?

PKU

http://poj.org/problem?id=2831 N村を結ぶM辺があり、最小全域木を作る そのとき、ある辺のコストがCならその辺は最小全域木に選ばれうるか、という クエリを処理する問題 id:semiexpさんの http://d.hatena.ne.jp/semiexp/20110107/1294381308 こちらの方…

PKU 2796 Feel Good

PKU

http://poj.org/problem?id=2796 N要素があって、その中の連続した要素の、 もっとも少ない数*その要素の合計 がもっとも大きいものを求める。ヒストグラムのアレです。 幅がありますが累積和でおk。 オーバーフローやすべての要素が0のときに注意。 typede…