hogloidのブログ

へなちょこ

GCJ 2017 R3

GCJ

ちょっとうれしいので大雑把なコンテスト経過をメモ: 始まる前 昼に起きた。あまり頭は使いたくないので、家の掃除をして、東方のなろうを少し読む なんか頭が明らかに動いてないので10分横になって紅茶を飲む 直前にsigmaがク☆バンバードを視聴完了していた…

解いたものリスト

個人的良問リスト - hogloidのブログ ←4年ぶりに戻ってきました 今回は、主観的面白さでoを0個〜3個つけています。 ☆は自力では解けなかった問題です。 月間更新予定。2017年1月は簡単めのSRMばかりやってたので簡単めのSRMばっかりです。 個人的備忘録のお…

ICPC Bangkok '16

ICPC バンコク大会に行ってきました.とても楽しかったです(小並感)久しぶりに更新。 1日目 午前中に荷造りをして夕方成田から飛んだ. 現地23時ごろに空港に着いた.自力ホテルまで移動を想定していたら,大会の迎えが来てくれた.ありがたい 会津のチーム…

カプセルホテル宿泊記

情報オリンピック本選で1日目と2日目の間に家に帰るのが面倒だったので新宿でカプセルホテルを取りました。これからカプセルホテルに泊まる予定のある人は参考になることがあるかもしれません。 2015/2/7 に 新宿区役所前カプセルホテル に泊まっていました…

今までに作った問題たち

そろそろ作った問題たちが増えてきそうなので、それらをまとめて感想を書いておきます。 まとめるのも面倒になるほどたくさん問題を作るぞ:punch: Codeforces #162 Div1C/Div2E Choosing Balls 初めて放出した問題。最初はa,b>=0だったり、クエリーじゃなく…

今年の目標

必須 人間的に成長する意思を持ち続ける そろそろこれやらないと社会的死が待ってる CF IGM +29するだけでいいしヘーキヘーキ インフレしてるし TC 2700 こっちはあんまり伸びる気がしないんだよなあ できたら 国際少人数onsite(TCO,GCJ,Yandex,顔本杯)に…

今年の目標を振り返る

恒例。放ったらかしでは意味がないんじゃ。 今年の目標 - hogloidのブログ 必須目標 CF Rating で2350をつける つきました TC Rating で2550をつける つきました 進級 まだよくわかんない これぐらいは 上の状態で年越し はい 上+100ぐらいはつける(どっち…

AOJ 2374 RabbitLunch

AOJ

概要 日本語なので読んでね RabbitLunch | Aizu Online Judge 解法 O(NlogN),O(Nlog^2N) のやり方もいくつかありますが、O(N) で解くことをオススメします ヒントはフロー(僕はこれをsnukeに教えてもらった) かなり面白いので、すぐに見ないほうがいいかも。…

g++拡張・tree

g++拡張にpb_ds(policy based data structure)というのがあって、その中に便利なtreeというのがあります。 細かい使い方まとめみたいなページは見つかりませんでしたが、コンテストでの主な用法をまとめておきます。c++のsetの上位互換みたいな感じで使えま…

Codeforces Round #230 (Div. 1) E. Deleting Substrings

CF

暗黒時代のCFなのはわかるがEditorialぐらい復活させてくれ :@ http://codeforces.com/contest/392/problem/E 概要 N要素からなる数列{w}がある。以下の操作を繰り返して、スコアを最大化せよ 数列の連続する部分を取り除き、その長さをLとすると、v[L]点稼…

Codeforces Round #259 E. Little Pony and Lord Tirek

CF

http://codeforces.com/contest/453/problem/E 問題概要: ポニーがN匹一列に並んでいる。ポニーiは最初siのManaを持っており、毎時間riのペースでManaを増やすが、Manaはmiまでしか持てない(それ以上になるとmiで止まる)クエリがM回ある。それぞれのクエリ…

Codeforces Round #FF D. DZY Loves Games

CF

http://codeforces.com/contest/446/problem/D 概要 N頂点M辺の無向連結グラフ(多重辺もたまにある)があり、ある頂点にいるときはつながっている辺を等しい確率で選んでその先に進む。 頂点にはtrapがあるかどうかが決まっている。 初め頂点1にいる。頂点1に…

ICPC Japan Domestic 2014

初ICPC&実質初チームコンテスト!!! 藤原さん、phiさんと出た。UTouto@Kyoto(京都でウトウト、生成メソッド式ダジャレ) 始まる前 東大結構チームがあっていろんな人がいる wakabaが直前になっても1人しかいない(tozanは間に合ったけどevimaさんは本当に…

トップ競技プログラマー年代まとめ

世界の競技プログラマーの中でもトップに入る人々を年ごとにまとめます。資格のある最後のIOIの年を基準にしています(僕にとって分かりやすいから) もちろん出ているとは限りません。 かなりcontroversialなトピックだと思うのでまあ誰が入ってて誰が入っ…

ジャッジシェルスクリプト

ジャッジできるサーバーがないときでも、手元にテストデータさえあればWA/TLE/ACを判定してくれるシェルスクリプトを書きました。テストしたいコードと同じフォルダに以下のスクリプトを書いた hoge.sh 、inフォルダ、 outフォルダ、 tmp フォルダを作って、…

IOI系ページまとめ

OI系の問題はなかなかジャッジに搭載されてくれないので、探すのは意外と大変です。そこでIOI対策に役に立つページたちをまとめます。 情報オリンピック日本委員会(http://www.ioi-jp.org/) 言わずと知れたJOIのサイト。これがないと予選に出れません。 ht…

今年の目標

そういえば作ってなかったので。 必須目標 CF Rating で2350をつける TC Rating で2550をつける 進級 これぐらいは 上の状態で年越し 上+100ぐらいはつける(どっちも) (あれば)国内コンテストで5位以内 ex.天プロ 不可を出さない やりたいなあ 国際オン…

XIX OI Festival

POI

問題分はこちら http://wikiwiki.jp/poiwiki/?%CC%E4%C2%EA%B0%EC%CD%F7%2F%C2%E819%B2%F3%2FFestival%20%CC%E4%C2%EA 人iの到着時刻をCiとおくと、 aはbより1秒早い、という条件は Ca=Cb-1 つまり、 Ca-Cb Cb-Ca と表せる。cはdより早い、という条件は、 Cc…

PCK2013 予選 9

PCK

幾何ライブラリなくて焦ったけど大丈Vだった。左端の取る点を固定して、反時計回りに取っていく。 dp[今までの頂点数][二つ前の頂点][一つ前の頂点]=面積最小値 とすると頑張って更新できる。O(N^5) この値から、すべての答えをあらかじめ求めておく。 出力…

個人的良問リスト

少し前から始めていた、良問だなーと思った問題をひたすらリストしていったものを上げます 良問、というより解く価値のある問題、といった方が正確かもしれません 2ヶ月ごとぐらいにアップデートする予定です 問題のリンクが貼ってあり、右に白い文字で解法…

Codeforces #165 div1-D Maximum Waterfall

CF

http://www.codeforces.com/contest/269/problem/D 問題概要 高さ、左端、右端の決まった棚がN個ある。 i番目の棚の高さ、左端、右端をそれぞれhi,li,riとおく。ある棚iから、ある棚jに水を流せる時、 max(li,lj)<min(ri,rj) つまり棚iと棚jが上から見た時…

Codeforces #165 div1-C,div2-E Flawed Flow

CF

http://www.codeforces.com/contest/269/problem/C 問題概要 N頂点、M辺のグラフが与えられ、頂点1がソース、Nがシンクである ソースからシンクへの最大フローを流した時の、辺に流れた流量が辺ごとに与えられる(向きは与えられない) フローが成り立つように…

Codeforces #165 div1-A,div2-C Magical Boxes

CF

http://www.codeforces.com/contest/269/problem/A 問題概要 N種類の大きさの箱がある。 i番目の箱の大きさは2^k(i)で、a(i)個ある。新しく2^pの大きさの箱を作って、それにすべての元の箱を詰めたい。 ある箱には、それより小さい大きさの箱を、半分の大き…

POJ Solved Graph

PKUのアカウントのsolvedを横軸時間、縦軸solvedのグラフにして表示します。 複数アカウントに対応しています。名前を入れるところに、コロン(',')区切りで空白などを入れずに複数のアカウントを入力してください ボタンを押すと、その時のウィンドウのサイ…

セグメント木 問題集

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

Codeforces #157 div1E Little Elephant and Tree

CF

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

Codeforces #152 div1C,div2E Piglet's Birthday

CF

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

Codeforces#148 div1C,div2E World Eater Brothers

CF

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

Codeforces#148 div1B,div2D Boring Partition

CF

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

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 …