たまには競技プログラミングのブログも書こうと思います。面白かったのとか教育的なのとかをまとめる。ツイートする ■ Yandex 2016 round2 D 23:48 Ax+By = Cを満たす非負整数x,y全てに対して C(x+y,x)の総和を求めよ (A,B要するに「総和がCになるようにA,B…

■ 2016年の目標 18:23 今年も去年の形式と同じにします。 (累積和)合宿に行く: 1点 IMOに行く: 9点 IMOで銀メダル以上を取る: 10点 (累積和)合宿に行く: 1点 IOIに行く: 4点 IOIで銀メダル以上を取る: 5点 馬鉢優勝:5点 6棒優勝:5点 総合優勝:10点 iPad模試…

■ 2015年を振り返る(2回目) 20:08 2015年の目標( http://topcoder.g.hatena.ne.jp/Hiro180/20150101/1420076631 )の結果発表(?)です。ちなみに(2回目)とついてるのは http://hiro180.hatenablog.com/entry/2015/12/30/122054 を書いたからです。良かったらそ…

■ JOI 2015本選 参加記 21:35 (2/4) ノロウイルスに感染したと思わしき症状が現れる (2/6) 参加が危ぶまれたが、何とか受けさせてもらうことが出来た。 (2/7) 体調が悪いのでプラクティスのみ参加して一旦ホテルに帰る。 (2/8) 朝オリセンに行く。各位にあっ…

■ 2015年の目標 10:43 2014年のkagamizさんや今年のtozanさんの形式をお借りすることにします〜 (得点は累積和です) TopCoder Algorithmの最高レート 2300~2399 : 1点2400~2499 : 2点2500~2599 : 3点 2600~ : 4点 Codeforcesの最高レート 2500~2599 1点2600~…

■ 2014年を振り返る 19:55 http://topcoder.g.hatena.ne.jp/Hiro180/20131231/1388502726 に対する結果発表です ・絶対にIOI2014に行く。日本代表になる。(迫真) 行けてしまった。本当に行けると思ってたかと言われるとそんなことは決してないんだけど、ひた…

■ 天プロ2013本選D 18:34 あのあと1hくらい考えてわかった。何も考えないとN^D通りあって、そのなかに制約を満たさないものがあるからそれを取り除く。少なくともi種類の筋肉は制約を満たさず、それらのトレーニングでj日間を費やしているような場合の数を考…

■ 2012天プロ本選解いた 22:43 A:Greedyだなあ...と書くと通る int main() { vectorvec; vec.pb(1); vec.pb(1); while(vec[vec.size()-2] + vec[vec.size()-1] 1e10) { vec.pb(vec[vec.size()-2] + vec[vec.size()-1]); } ll n; cin >> n; int res = 0; whil…

■ ARC #026 && 101 Hack June'14 00:11 成し遂げたぜ。 ARC #026 A: 一種のGreedy B: やるだけ (10^10 = (5*10^9)^2とかいうひどい勘違いをしていた) C: segtreeした D: 時給きめうち-> MST (ただしコストが負の辺は無条件で追加) こういう問題は昔から好き…

■ IOI 2013 ArtClass 19:27 実験する過程で、全マスのR,G,Bの2乗和の平均と、隣接したマス同士のR,G,Bの差の2乗和の平均を求めると、隣接したマス同士のR,G,Bの差の2乗和の平均が極端にでかい->3隣接したマス同士のR,G,Bの差の2乗和の平均が極端に小さい->4…

■ SRM 625 22:23 記念すべき第50回目の出場。 偶奇わけしてCombinationをほげると通る mod 3で座標を見る時の同じタイプの隣り合ったやつまで行けなくするためのコストがすぐわかる。あとはこのグラフに対し最小カットを求める。フロー系の問題初めて通った…

■ IOI 2012 Rings 20:23 日本語の問題はJOIのホームページにあります概要: N頂点のグラフがある。はじめは辺が張られていない。Link(a,b) -> aとbに辺を結ぶcount()-> 「その頂点を取り除くと残りのグラフに直線状の鎖しかのこらない」ような頂点の個数を返…

■ IOI 2012 Day1 00:32 crayfishのほげてきと〜に木を作ってdoublingするparachuteのほげ20点(ブチ切れ) これだからvoltage20点なんだよなあ...odometerのほげ何だこの問題はwwwsubtask1,3は自明で4も書くだけで点が貰えます (45/100)やっぱり木はそこそこ出…

■ AOJ 2292 23:04 文字列強化週間なのでといてみた。APIO 2014の1問目の上位互換。解法: manacherのほげで適当に各場所を中心とする回文長を求める。次に長さlenの回文について考える。lenは奇数とする。(偶数も同様に処理できる。)場所i,jに対しiを中心とす…

■ IOI 2013 GAME 23:34 80点はJOIのapplesという問題をといたことがあるとかけます。100点はなんかすると取れます。(ノード内のデータ構造を平衡二分探索木っぽく書くととれるらしい)(ソース: https://gist.github.com/msg555/6025939) #include #include #i…

■ IOI 2004 Day1 12:57 Artemis:長方形内の樹の本数はO(log^2 N)で求められるしO(N^2 log^2 N)で常勝!! -> Nということで適当な枝狩りを入れたら通った。(よくわからない)Hermes:どうせ各場所に手紙を渡した瞬間にいる場所の候補は高々4000だからすべてDPし…

■ IOI 2013 Robots 00:57 考えたこと:weak robotsから処理しよう->明らかにsizeがでかいほうからやったらうれしい->"sizeが大きい順にみて、取れるなら最も重さlimitが厳しいやつでとる"というGreedy?->通った。 なんでこれでいいのかはわからない。たぶんkr…

■ SRM 616 02:20 Easy: LCMMed: 無理Hard: 無理challenge: 無理systest通る112th Rating 2091->2136(+45)1完でレート維持するの怖すぎるのでMedかHard解けるようになりたい人生であった(fin)ツイートする

■ SRM 615 22:00 BGMはPlan 8でした。 Easy:全部試してそれら/2のべき乗を試すだけ Med:むずかしい Hard:やるだけ challenge +0/-0systest 通る 20th 1934->2091(+157) あっというまにHighest付近に戻ってこられたのでよかったです。今度は跳ね返されません…

■ SRM 614 03:08 Easy: D1Easyらしい問題。こういうの好きです class MinimumSquare { public: long long minArea(vector int> x, vector int> y, int K) { int n=x.size(); ll res=1LL*9e18; for(int i=0;ifor(int ii=0;ii1; ll ay=y[ii]-1; vectord; for(i…

■ JOI 2014 春合宿 23:30 俺が!!!!!!5位だ!!!!!!!!!! 755/1300 Day1:荷物重すぎ。つらい。早めに会場についてうなうなしていた。practice全完した。adventure楽しい()自己紹介はてきと～にやった(何言ったか覚えてない。)大体の人は知っていたが、satosさん…

■ SRM 613 D1Med 22:33 dp[x]=GCDがx*kの倍数になるものとしてやれば適当にやるだけ。 #line 2 "RandomGCD.cpp" //Bokan ga bokka--nn!! //Daily Lunch Special Tanoshii !! // I'll become a member of IOI 2015 Japan team. #include #include #include #i…

■ JOI2014春合宿 21:12 100+100+100+100+10+100+10+100+15+20+0+0+100=755 (sun)(sun)(sun)ボーダーはいくつなんでしょうかね....ツイートする

■ JOI 2014 春合宿Day1 22:50 4h47mで全完しました。菜園難しすぎるBus: 嘘解法力growing: 気づけばやるだけhistorical: てきとーにsqrt-decompositionするだけ一応コード /* TASK: Historical Research LANG: C++ NAME: HIR180 JPN03 */ #include #include …

■ JOI春合宿 18:14 いよいよですね。僕自身は去年の12月頃から4ヶ月くらい代表目指して真剣に精進してきました。実際SRMやCFで実力の向上を感じられているのでやってきたことは無駄ではなかったんだな、という思ってます。なんか今はもう達観してる感じですw…

■ SRM 612 12:28 死んだ。1975->1790(-185)Easy: 最小値とり忘れた。クソMed: 嘘解法Hard: 無理challenge: -1(デデドン)Systest: 唐突な赤字先輩ちょっと浮かれてたのでまじめに精進しなおします。ツイートする

■ USACO March contest(Gold) 02:47 1: 45度回転してstarry-skyやるだけ2: にぶたん+dequeするだけ3: googleで"グラフ 次数 作成可能"と調べるだけツイートする ■ 解けるか分からない問題 01:14 まずはこちらをご覧ください: http://codeforces.com/contest/…

■ CF #127 div1 20:35 A: 糞問B: サンタさんがチョコレートケーキを配る問題に似てる。簡単C: 一筆書きなので奇点は0 or 2なので順にDPするだけツイートする ■ SRM 540 Div1 Med 18:06 550ptsですが3次元累積和を正しく書いて0除算しないようにすれば誰でも…

■ 無題 04:09 突然ですがどなたかCFでwriterやりませんか(唐突)ツイートする

■ CF #234 Div2 04:28 A: やるだけB: setを使うと簡潔にできます。問題文がちょっとおかしかったらしいですね...C: 普通に%4%2%4してやるだけ。JOIのdragonを思い出しましたD: コスト0をuniteしてやればYes/No判定はでき、コストを求めるのはWFでよい。E: bi…