この記事では自分の愛用しているデータ構造であるunion-find木の自分のつかいかたについて書きます。 あくまで「自分の」使い方なのでもっといい使い方があるかもしれません。この記事では、union-find木がどういうデータ構造かは知っているものとして話を進…

満点狙いで行ったけど多分バグって116点。1:やる #include<stdio.h> #include "stdafx.h" #include<algorithm> using namespace std; int main() { FILE *fr=fopen("2013-yo-t1-in5.txt","r"); FILE *fw=fopen("out5.txt","w"); int res,pa,pb,sa,sb; fscanf(fr,"%d%d%d%d%d",&re</algorithm></stdio.h>…

おなじみのダンジョン。各階ごとに、死にそうだったらそこまでで一番多く回復できるところで回復したことにして続ける。 そこで、「ある場所以降すべてにある値を足す」「ある場所以降の最大値を求める」というクエリが処理できればいいことがわかって、これ…

いちいち一個ずつ記事つくるの面倒なのでまとめる。一問目 http://codeforces.com/problemset/problem/253/E仕事がたくさん来て、優先度があって残ってる仕事の中で優先度が一番高いのから処理していく。で、一つ優先度が分からないのがあるから、それを求め…

11/10 起きる。東京駅に向かう。銀座線のホーム短い。 会場に行く。昼食をコンビニで買ったら駅のすぐ外においしそうな焼きそばが売ってて冷える。 会場につく。きゅうりがたくさん応援メッセージをもらっている。ペロリンに食べられたらしい。 開会式がてき…

週末のコンテスト3連発。 TC easyに時間かけすぎってそれ一番言われてるから(時間あったらmedはとけた)210位。屑。でもレートは上がる。rate:1330->1438(+108) ARC Dむずい。というか10^11くらいの解法しか思いつかない。CはOEISした(屑)14位。日本のコンテ…

夏季セミ中のDiv 2のE.解法は簡単(距離をsetに突っ込んでおく)だけどiterationがめちゃくちゃ難しい。デバッグ大変だった。よく一発ACしたなという感じ。以下ソース #include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; typedef pair<int,int>pii; int dist[20</int,int></set></algorithm></vector></stdio.h>…

ARC#8の参加記。 平成教育委員会を見ている。 8:00 家族がそのまま見ているので、見ながら始める。 A読む。サンプル読む。面倒なことは考えずにたこ焼き買う個数を動かそう。 00:02 AC. B読む。普段より実装少なそう。 ちょっとバグバグする。 すぐに治る。 …

JOI Ninja Contestの参加記。 とりあえず問題を全部読む。 C実装重そうだけどしっかり書けば満点は余裕そう かく。 とりあえずdijkstraを4つかく。 スーパー場合分けターイム！！ なんだかんだで場合分けしまくる バグバグバグ... バグバグバグバグ... バグ…

Codeforces #138(Div 1)の参加記。 コンテストが始まる。A読む。苦手な類の文字列操作。 わからない。 とりあえずわかった気になって書く。 バグる。どうしようもないことに気付く。 とりあえずあきらめてB読む。 すごく楽しそう。これは解きたい。 5分くら…

オンラインでゆるーく参加してました。 〜11:00 Codeforcesを解いている。 11:02 コンテストの存在に気付く。 JAGなのでどうせ解けないからやるだけ解くのはやめてむずかしめな問題を考えるだけ考えようと思う。 いろんな問題を開ける。 C座標圧縮+累積和し…

PCK予選にnullmineralさんと参加してました。 予選前に適当に環境構築をする。 終わったところでぬるみねらるさんが昼を食べに行く。 15分前くらいに戻ってくる。プリンタがつながらない。 プリンタがつながらない。 そのまま開始。 1:ぬるみねらるさんがか…

爆死したし大したコードがないので結果だけ。Codeforces: Aはさすがに通す。CをみてChineseと同じだと思ったので書いたらWA.円環じゃないことに気付き出す。Cがtest 25で原因不明のバグにより落ちる。出力の6000番目くらいの値が違うって知るか...rate:1779-…

おとといのDiv1 D.格子点を結んでできる面積が整数の三角形の個数を数える。 x座標とy座標の偶奇の組で点を4つに分け、3つの異なる組から取られたものはNGとする。 ABABABAB CDCDCDCD ABABABAB CDCDCDCD こんな感じ。A,B,DとかはNG,A,A,AやA,B,BはOK.その後…

8/20 家をでる。眠い。大岡山でKevinRobotさんに会う。 問題説明を聞く。 関西会場のお菓子が豪華すぎる。 適当に考えて、「フロー速い」ということに。ここら辺で時間が終わったので実装は明日。 8/21 nullmineral氏が実装してくれる。(やはり開発っぽいこ…

変なことができるデータ構造を作れという問題。コード中でpriority_queueにseとかいう名前がついてるのは定数倍改善のためにsetをpriority_queueに書き換えただけで特に深い意味はない。 #include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> #include<queue> #include<map> </map></queue></algorithm></vector></stdio.h>…

easy:やるだけ #include<stdio.h> #include "stdafx.h" #include<vector> #include<iostream> #include<algorithm> #include<string> using namespace std; int main() { string str; cin>>str; int hai[26]; fill(hai,hai+26,0); for(int i=0;i</string></algorithm></iostream></vector></stdio.h>

すごくJOIに出そうな問題。点がN個与えられて、縦方向でも横方向でもある2つの点に挟まれているところが新たに点になる。最終的な点の数を求めよ。 座標圧縮してBITに持っておいたりすると通る。初めから十字になっているところを最初にひいている。 3K書い…

A:フィボナッチ #include<stdio.h> #include "stdafx.h" int main() { int num; scanf("%d",&num); long long a=1,b=1; for(int i=0;i<num;i++) { long long c=a+b; a=b; b=c; } printf("%lld\n",a); } B:やるだけ。なのに2WA #include<stdio.h> #include "stdafx.h" int main() { char str[10000]; gets(str); int han=0; for(int i=0;;i…</num;i++)></stdio.h>

n整数からなる集合がm個与えられて、おのおのから1個ずつ選んでその和をとった時にそれが小さい組み合わせから順にn個列挙せよという問題。POJの鯖遅いしいくらなんでもO(mn^2log n)は通らないだろうなと思ってたら、怪しい二分探索のO(mnlog^2n)解を見つけ…

POJ200AC.一応メモ程度に。 期末とかいう何かで3週間中断されてたから妥当な速さかもしれない。

USACO U S Openの問題。数直線上に点がN点与えられ、それらの2点の間のコストが(その間の距離)*(2点の持つ値の大きい方)で定められているので、すべての2点間のコストの総和を求める。BITを2個持っておいてやって、"座標の合計"と"そこまでにある点の数"を持…

PCKの問題のはず。 普通に文字列のままやったらTLEして腹が立ったのでローリングハッシュ書いた。 結果、rank6位に。わーい。 http://poj.org/problemstatus?problem_id=3007 #include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef pa</iostream></string></algorithm></vector></stdio.h>…

題名は問題名なのであしからず。2-SATに見えて考えてたらわけがわからなくなり考え直したら無向グラフだったことが判明。 思い切りunion-findが役立つ。UFかわいいよUF。 #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> #include<string> #include<iostream> #include<stdlib.h> using namespace s</stdlib.h></iostream></string></math.h></vector></algorithm></stdio.h>…

良問だと思う。文字列の長さをL,文字列数をNとすると,O(N L^2 log N). TLEぎりぎりでAC. #include<stdio.h> #include<vector> #include<algorithm> #include<string> #include<iostream> using namespace std; typedef pair<string,int>psi; typedef pair<int,psi>pisi; int len[10000]; int frm[10000]; int main() { vector<string>zvec</string></int,psi></string,int></iostream></string></algorithm></vector></stdio.h>…

A,B:やるだけ。なのに低速submitC:わからないので飛ばす D:わかった気になったら嘘解法だった E:unopened結果:175位 rate:1793->1796(+3)

何でもいいから解を一つ求めればいいので、適当に山登り&登りきれなかったらrandom_shuffleで適当に書く。通る。(多分嘘解法じゃないはず)K #include<stdio.h> #include<vector> #include<algorithm> #include<stdlib.h> using namespace std; typedef pair<int,int>pii; int main() { int num; scanf("%d",&</int,int></stdlib.h></algorithm></vector></stdio.h>…

解いてる人が233人で難しそうとか思ったけど考えてみると普通にgreedyに選んでいけばいいだけということに気付く。なんでこんなに通してる人少ないんだろう。 #include<stdio.h> #include<vector> #include<algorithm> #include<set> #include<queue> using namespace std; #define mt(A,B,C) make_pa</queue></set></algorithm></vector></stdio.h>…

しばらく更新さぼってましたね。すみませんね。いつの間にかTCでDiv1に上がっていたのになぁ。さてこの問題。適度な数学ゲーで楽しい。 #include<stdio.h> #include "stdafx.h" #include<vector> #include<algorithm> using namespace std; int main() { for(;;) { int num,cho; scanf("%</algorithm></vector></stdio.h>…

POJ100ACを達成した。わーい。 POJ開始日は5/1だから、38日で100ACしたことに。遅い。