hogloidのブログ

へなちょこ

GCJ multithread

GCJ

これは何? C++11以降で、GCJ形式(手元で複数ケースの計算をして提出するタイプの問題)の実行が数倍速くなる雛形 なんで速くなるの? 最近のコンピュータは大抵コアが複数個ついてるので、複数テストケース(=完全に独立に並列で動かせる)なら同時に動かした…

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…