ここ数年のJAGの問題で最もひどいやつ。 問題の概念を理解するのが難しいだけ。説明なしにこんなこと書くのはどうかしてると思う。(本番では問題文が別の問題にすり替わっていてもっと酷かった) #include<stdio.h> #include<algorithm> #include<vector> using namespace std; vector<int>g[21</int></vector></algorithm></stdio.h>…

sigma425のソースコードが綺麗。 僕のはマジックナンバーでごり押し。 #include<stdio.h> #include<vector> #include<algorithm> using namespace std; char str[60][60]; int h[]={2,3,3,3,3,3,3,3,3,3,3}; int w[]={5,4,4,4,4,4,4,4,4,4,4}; char tkz[11][6][6]={ { "DLU..", "..FRB" }</algorithm></vector></stdio.h>…

ほそながかった...通過の順番をそれぞれ決めて後は到着時刻を合わせるようにずらすのを収束するまでやる。収束しなかったらそれは無理配置。 この問題は問題文を何度も読んだことがあるけど、読むたびに誤読している。 #include<stdio.h> #include<algorithm> using namespace st</algorithm></stdio.h>…

これは面白い。 向かいたい方向と逆に回らないといけない、すなわち遠回りを強要するブロック配置は、スタート付近とゴール付近にしかないことが容易に(ここが本質なんだけども)分かります。ということで赤い場所(50*50もない)は真面目にDPをして、白い場所…

Aho-Corasick + DP + メモリの定数倍 kuso.... #include<stdio.h> #include<map> #include<algorithm> #include<string> #include<vector> #include<queue> using namespace std; long long mod=1000000007; char in[30]; string table[600]; vector<int>g[600]; struct wolf{ int chi[26]; int mark; int par; int</int></queue></vector></string></algorithm></map></stdio.h>…

マッチングの最小化をする。 想定解法では変なことをしてO(N^2)であるが、見るからにMonge DPのDivide and Conquerテクなので、終了。 距離の和の計算で嵌った。 (そういえばDPの式ですが、dp[i][j]: i個目の余った点(サイズ1以上)でj個覆ったときの最小コス…

相当いろんな解法があるらしい。考えられる一番直感的な方法で解いた。動的確保の二種の和のsegtreeにpairをぶちこんでソートして後半のクエリで二分探索。動的確保で何個ノードが必要になるのかがよくわからない。計算量(特にソート部分)もよくわからない。…

iとtを間違えてハマった。典型的な防ぎようのないバグ #include<stdio.h> #include<algorithm> #include<string> using namespace std; typedef unsigned long long wolf; wolf mod=1000000007; char gly[26][20][20]; wolf Hash[26]; wolf revHash[26]; int gh[26]; int gw[26]; char in</string></algorithm></stdio.h>…

たまに見る二分探索トラップ。 嘘解法ごめんなさい……。 #include<stdio.h> #include<algorithm> using namespace std; int c[1100]; int d[1100]; int e[1100]; int fin[1100]; int next[1100]; int a,b; int can(int M){ for(int i=0;i</algorithm></stdio.h>

長い間AOJからは離れていたのですが、気が向いたので解きました。探索して盤面をつくり、後はたどるだけで頑張ればよいです。何でこれで探索パートが一瞬で実行できるのかはよくわかっていません。 座標を上手く持つ方法が強いて言えば難しいくらい？ #inclu…

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>…

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>…

しばらく諸事情で競技プログラミングができないので、記事を書いておくことにする。 非典型で良問だと思う。 二分探索をする 木を作る より多く必要な人数を木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>…