kについて二分探索した後、その判定を頑張ってO(n)で出来るようにする。 #include <stdio.h> #include <utility> #include <set> #include <algorithm> #include <vector> #define MAX_V 1000100 using namespace std; int n; int ai[MAX_V],can[MAX_V],bi2ai[MAX_V]; pair<int,int> bi[MAX_V]; int ok(int k) { </int,int></vector></algorithm></set></utility></stdio.h>…

２０１１年８月２２日(月) 〜 ２６日(金)にかけて大阪大学豊中キャンパスで SuperCon2011にチームMKとして参加してきました。 今回の課題は「https://www.cp.cmc.osaka-u.ac.jp/supercon/naklon.html」。 リンクをクリックして表示されるのはSIZE＝８のもの…

使い方 :load で読み込んだ後 myEquation "1+2*3" import Text.ParserCombinators.Parsec myDigit :: Parser Char myDigit = oneOf ['0'..'9'] myNumberString :: Parser String myNumberString = do c<-myDigit do cs <- myNumberString return (c:cs) <|> …

使い方 hoge.hsに下のコードを保存する。 runghc "hoge.hs" "target.html" ※ダブルクオーテーションは必要 このままでは空行が大量に含まれているので runghc "hoge.hs" "target.html" | sed '/^ *$/d' すると良い --sed '/^ *$/d' import Text.ParserCombin…

環境：xubuntu11.04+canon mp600キヤノン：ダウンロード｜ScanGear MP Ver.1.00 for Linux ここから共通ファイルとmp600用のファイルをrpm形式でダウンロードして キヤノンよりダウンロードした２つのファイルを~/canonに置いた。 sudo apt-get install alie…

JavaScriptの実行されるタイミングがよく分からない。

PriorityQueueを使って全ての地点までのk最短路を求めた後にメモ化再帰。 ソースコードの後半は指定されていたテンプレート＋入力データのコピーだけ。 /* SuperCon 2011 予選問題Ｃ用テンプレート ・解答プログラムはこのテンプレートに従って作成すること…

通信範囲を１づつ大きくしながらメモ化再帰。 #include <algorithm> #include <vector> using namespace std; class ConnectTheCities { public: int n,dist,range; vector<int> pos; int cache[105][55]; int rec(int bP,int k) { //printf("bP=%d k=%d\n",bP,k); int &r=cache[bP][</int></vector></algorithm>…

ややこしすぎて、なんで通ったのか分からない。 #include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <map> #include <climits> #include <cfloat> using namespace std; int K,gN; int E[40]; int G[16][16]; dou…</cfloat></climits></map></set></cmath></cstring></cstdio></sstream></iostream></vector></string></algorithm>

2^10は使わなかった。 #include <algorithm> #include <vector> using namespace std; class Shopping { public: int minNumber(int X, vector <int> values) { sort(values.begin(),values.end()); if(values[0]!=1) { return -1; } else { int r=1; int s; for(s=1;s</int></vector></algorithm>

ALGORITHM NOTE ヒストグラム中の最大の長方形の面積 または Amazon.co.jp： プログラミングコンテストチャレンジブック: 秋葉 拓哉, 岩田 陽一, 北川 宜稔: 本 の280ページ、スタックの利用を参照。 #include <vector> #include <stack> using namespace std; typedef long</stack></vector>…

問題概要 あるデバイスに送らななければならないデータがその始まりのアドレスと大きさの形で渡される。 データはパケットに分けて送らなければならない。 そのパケットはメインデータとオーバーヘッド部分から成る。 このとき送らなければならない最小のバ…

問題要約 ーーーーーーーーーーーー n人の人が円形に並んでいて、 時計回りの順にボールを任意の他の人に向かって投げる。 ボールがあたった人は円から離脱し、 番号iの人が投げたボールが当たる確率はprobably[i]である。 この時円形に並んでいる人が１人に…

k乗和の公式を使う。 求め方は数学Bの教科書に載っている。 #include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <map> #include <climits> using namespace std; typedef long long LL; static const LL MOD=10000000…</climits></map></set></cmath></cstring></cstdio></sstream></iostream></vector></string></algorithm>

なにそれオイシーの？

使うギターを全探索するだけ。 #include <algorithm> #include <string> #include <vector> #include <set> using namespace std; class GuitarConcert { public: vector<string> comp(vector<string> vs1,vector<string> vs2) { if(vs1.size()==vs2.size()) return (vs1</string></string></string></set></vector></string></algorithm>

分からなかった。 ビットを使って部分集合を求めると結構速いらしい。 このDPの計算量はそれぞれのビットについて (mask:0,sub:0),(mask:1,sub:0),(mask:1,sub:1) の場合があるので3^nなんだって。 2^n*2^nしか思いつかなかった。 #include <vector> using namespace</vector>…

凸な図形＝三角形の集まりなので rec(どの座標を使ったか(=mask)、今どの座標か(=k))は kを含む三角形を(i,j,k)の面積をsとすると s+rec(maskにi,j,kを追加した物,k+1) の内最小化のものを返せば良い。あとはそれをメモ化再帰して終わり。 三角形の面積を求…

最大値の最小化なのでセオリー通りに二分探索。 #include <algorithm> #include <string> #include <vector> #include <sstream> using namespace std; class LogCutter { public: int n; vector<int> canCut; bool check(int L,int C,int mid) { int beforeCut=0; while(mid</int></sstream></vector></string></algorithm>

#include <algorithm> #include <vector> #include <cstdio> #include <cstring> #include <climits> using namespace std; typedef long long LL; int n; LL k; int range[55][55][2][2]; LL cache[55][55][2]; class ContiguousCache { public: LL intersect(int a1,int a2,int b1,int b2) { if(a1<=b1 &</climits></cstring></cstdio></vector></algorithm>…

メモ化再帰。 難しくて解説みた。 #include <string> #include <vector> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; LL DP[(1<<13)][2][15][15]; class PalindromePhrases { public: int n; vector<string> words; bool isPalindome(string s) { for(int i=0;i</string></cstring></cstdio></vector></string>

満点で予選通過した。 Round1は中間テストの真っ最中だけど、頑張って出るかもしれない。

二部探索＋ダイクストラ。 #include <algorithm> #include <string> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; typedef long long LL; int n; LL limit; LL INF=((LL)1<<LL(50)); LL visited[500]; vector<int> F[500]; vector<int> T[500]; vector<int> P[500]; vector<int> D[…</int></int></int></ll(50));></utility></queue></sstream></vector></string></algorithm>

二部探索＋２SATらしい。 #include <vector> #include <cstdio> #include <cstring> using namespace std; class ColorfulDecoration { public: int n; int len; int dist[110][110]; int G[110][110]; int ABS(int n) { return (n<0)?-n:n; } bool check() { memset(G,0,sizeof(G)); </cstring></cstdio></vector>…

眠い！ どの行とどの列をひっくり返したかと位置を状態としてBFS。 #include <string> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; int mv[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int dist[(1<<15)][10][10]; class TurningMaze { public: bool can</utility></queue></sstream></vector></string>…

貪欲でOK。 #include <string> #include <vector> using namespace std; class StringInterspersal { public: string minimum(vector <string> W) { string ans; int n=W.size(); int s=0; for(int i=0;i<n;i++) s+=W[i].size(); vector<int> used(n,0); while(ans.size()</n;i++)></string></vector></string>

calc(n)をn以下のjumpyNumを求める関数とする 答えはcalc(high)-calc(low-1) ーーーーーーーーーーーーcalc(n)の説明ーーーーーーーーーーーー 数字を文字列にして考える n=123456789のとき m=12345....なら、mはnにpos=4(0-indexed)までマッチしているとい…

二つの列に一箇所でも共通点があれば片方でしか分かっていない情報も分かるようななる。 行についても同様。 #include <string> #include <vector> using namespace std; class RectangleArea { public: int h,w; vector<string> vs; void check() { for(int i=0;i</string></vector></string>

OXX 1457→1590

自転車で亀岡まで行った。 保津川下りっていうイベント(？)をやっていた。