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人参加予定です。皆さんの声援をお待ちしています。 本題に入ります。 概要 ボルダリングというのは壁にくっついた変なものを両手両足で…