Bのうち最上位にある1の位置をat(0-origin)とすると 「atの場所は0」「at未満のところを好き放題いじる」という値はBより小さく、この値をCとすると A+Cは「(Aのat以上のbitの1の個数)+at」個の1がある。 これより大きくすることができることもある。ただし…

dp[i][j][k]: i番目のお菓子でkさんが始めてから先手の人がj得て終わるためには(先手の人のエネルギー)-(後手の人のエネルギー)が何以上/以下であればよいか見てのとおり遷移が複雑です。次の2通りの遷移があります。 i番目をkさんは選ぶ。相手のdpテーブル…

包除原理で数える。 answer = (3つおく全ての方法の数)-(2個同じ線上にある方法の数)+(3つがL字に置かれる方法の数)+(3つが同じ線上にある方法の数)*2あとはNオーバーフローに気をつけましょう。 #include<stdio.h> #include<algorithm> #include<set> #include<vector> using namespace std; </vector></set></algorithm></stdio.h>…

面倒そう面倒そうと言って毎回逃げていたのでそろそろ仕方なく埋めることにしました。 フローの辺たちを上手くDFSでいじるだけ。練習にはなる。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; const int D_MAX_V=1100; const int D_v_size=1100</queue></vector></algorithm></stdio.h>…

問題大量追加とAOJ-ICPCの整備された環境のおかげでここまでこれました。去年のこの季節に国内予選に落ちてから夏をTopCoderのDiv1Hardに全力を費やし、しばらくたってほとぼりが冷めたころにアジア地区予選があって悲しみを掘り返された勢いでひたすらAOJを…

ir5さんが解説をslideshareに上げている。本質は使う移動と移動するときのコストの基準点(1になるところ)の対応がGreedyというか両方同じ順であるということで、それが分かっていれば方向全探索O(N^3)、始点O(N)、内部でGreedyがO(N)で解けるという感じ。 4…

解説の記憶が薄れる前に解いておこうということで。*1・2w+1ビットを一つの頂点として、右に0か1を付け足したときに0,1の総数がどうなるかを計算して辺をはる。辺のコスト(1を付け足すと1がひとつ供給される)と頂点のコスト(オートマトンが1を吐くと1がひと…

存在がクソ解決不能不備問(出題ミス)。どの枝刈りが有効なのかまったくわからず思いついた順に枝刈りを足していくのでこういうのはめちゃくちゃ長くてややこしいコードになる。 #include<stdio.h> #include<algorithm> #include<set> #include<vector> #include<queue> using namespace std; char in[</queue></vector></set></algorithm></stdio.h>…

RUPC2015のセットの中で唯一頭を使う問題。 何か見た目がフローっぽかったり変なGreedyを併用するbitDPのようにも思えるが、どれもなんかしっくりこない。ここで3^N個の状態を持つことにして、dp[i][j]を下図のような状況での最小コストとするとすごくすっき…

解法にいたった経緯を時系列順に並べる。 小さいケースを確かめてみる。N=2、N=3、N=4…。 N=4、試すことすら困難。諦めざるを得ない。 ちょっとグラフの形を変える グラフが星だとxorで分かるのか。心底どうでもいい。は？ なにこれ n時間RucKyGAMESをしなが…

実質Typhoon。 いつまでたっても同じようなやるだけ典型が出題され続けるの、問題作成陣の(解く方の)練習不足を感じる…… #include<stdio.h> #include<algorithm> using namespace std; int c[110000]; int z[110000]; int ret[110000]; pair<int,pair<int,int> >ev[210000]; int bit[110000]; int s</int,pair<int,int></algorithm></stdio.h>…

7月になりました。今月もいろいろと頑張ります。今月の終わりごろには国際情報オリンピックがあり、日本からも高校生が4人参加予定です。皆さんの声援をお待ちしています。 本題に入ります。 概要 ボルダリングというのは壁にくっついた変なものを両手両足で…

久しぶりに参加しました。全問やるだけセットなんて初めて見た。A: やるだけ。 #include<stdio.h> #include<algorithm> using namespace std; int main(){ int a,b; scanf("%d%d",&a,&b); int v=0; for(int i=0;i</algorithm></stdio.h>

2011合宿のDragon原液1mlを1000倍に薄めて付属の計量カップ1杯とってきたくらい簡単。 これで本選5とは…(というか去年と一昨年が難しすぎるだけかも) #include<stdio.h> #include<set> #include<algorithm> #include<vector> using namespace std; bool t[4100][4100]; short ul[4100][4100]; </vector></algorithm></set></stdio.h>…

作りました。みなさんプレイしましょう。Japanese villages who has less than 1,000 peoplewww.sporcle.com

しばらく諸事情で競技プログラミングができないので、記事を書いておくことにする。 非典型で良問だと思う。 二分探索をする 木を作る より多く必要な人数を木DPする ということを気にすればOK。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; </queue></vector></algorithm></stdio.h>…

Suffix Array+Segment Tree。 Suffix Arrayでlower_boundってどうするんだっけとか一瞬思ってしまった。 #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; char str[210000]; char in[210000]; int q[910000]; int n; int sa_k; int rank[910000]; int tmp[</string.h></algorithm></stdio.h>…

左からi桁決めたときに次に挙げるもののうちどれにマッチするかの集合がどれか、でbitDP。 k個の整数が終了した k個目の整数の10の位まで終了した。1の位で可能なパターンは某(場合によるが3種類くらいある) 押し込むと最大18bit。遷移もやはり場合わけが必…

追記：えっとパスの長さだから本当は下の図の0～5のところは1個多いですね かなり解法が面白かったので解法を1枚の画像にしました。 #include<stdio.h> #include<algorithm> using namespace std; int l1[110000]; int r1[110000]; int l2[110000]; int r2[110000]; int segtree[</algorithm></stdio.h>…

構文解析要素、なし #include<stdio.h> #include<algorithm> using namespace std; char str[52][52]; int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; char com[1100]; int vis[52][52][4][1100]; int to[1100]; int last[1100]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int</algorithm></stdio.h>…

自炊が疎なときを思い浮かべるとやりやすい。 #include<stdio.h> #include<algorithm> using namespace std; long long d[510000]; pair<long long,int> e[510000]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i</long></algorithm></stdio.h>

これはかなり簡単だと思います。イベントをどうしてこうするだけ。 #include<stdio.h> #include<algorithm> #include<math.h> #include<vector> using namespace std; //略 Pt L[110]; Pt R[110]; Pt vec[110]; double t[110]; int main(){ int W,H,N; double r; while(scanf("%d%d%d%lf",&W,&H,&</vector></math.h></algorithm></stdio.h>…

wataさんがスライドで公開されている方法を使う。 といって使ってみたらTLEするし探索はやっぱり無理だった。(次数1の処理をしたら通った) #include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int>g[3100]; vector<int>ng[3100]; int deg[3100]; int use[3100]; </int></int></algorithm></vector></stdio.h>…

ちょっとライブラリ風になった。 過去問からコードひっぱってくるときは、210みたいな数をちゃんと見てバグらないようにコピペすることが大事。 というか最小有向全域木は結構厄介なのでライブラリ化しましょう。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> #incl</queue></vector></algorithm></stdio.h>…

ついに2011本選が追加され始めたので。0251: 要は各連結成分が直線かどうかを聞いている。 #include<stdio.h> #include<algorithm> #include<vector> using namespace std; int deg[110000]; int UF[110000]; int FIND(int a){ if(UF[a]<0)return a; return UF[a]=FIND(UF[a]); } void UN</vector></algorithm></stdio.h>…

ハードしたので自分がどう攻略したかをメモ。option: 正規1～17小節：はい18～25小節： 左皿は捨てます。 右皿は拾ってつなげます。26～41小節：はい この右皿を忘れがち。42～49小節： ほ ん へ 左の57は両方全部親指でやることを意識しました。 4連打もち…

"ambigious", "ambigous"の元ネタはこれではなくBroken Audio Signalのほう。 行列累乗して連立方程式するやつ。 #include<stdio.h> #include<algorithm> using namespace std; int b[510][510]; int c[510]; int tmp[510][510]; int A[510][510]; int main(){ int a; scanf("%d"</algorithm></stdio.h>…

久しぶりにPKUクオリティのオンラインジャッジ環境。(問題と呼べる条件を満たせない典型例)1日ごとに全部売るのが最善であることが結構わかりにくい。 データが修正されたと書いてあるのに未だにデータに不備がある。AOJは機能もついているし何も損しないん…

解説スライドの2ページ目の図を見るだけ。*1 #include<stdio.h> #include<algorithm> #include<queue> using namespace std; const int INF=999999999; int ver[510][510]; int hor[510][510]; char dir[6]="UDLR"; int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; char str[1100]; int dist</queue></algorithm></stdio.h>…

満点で7位でした。A: 英語を読むだけ。問題文いくらなんでも難しすぎると思う。解釈するのにかなり時間がかかった。 #include<stdio.h> #include<algorithm> using namespace std; int b[1100]; int main(){ int T; scanf("%d",&T); for(int t=1;t<=T;t++){ int a;scanf("%d",&a)</algorithm></stdio.h>…