幅優先探索 及び全探索 以下のコードはPKUではTLE static const int dx[] = {0, 0, 1, -1}; static const int dy[] = {1, -1, 0, 0}; int main() { for (int w, h; cin >> w >> h && (w || h); ) { char maze[32][32]; memset(maze, 'x', sizeof(maze)); vec…

拡張ダイクストラ法 [最後に訪れた頂点][使用したチケットの集合]でダイクストラ 又は[最後に訪れた頂点][何枚目のチケット化]を外側でチケットの順番を回しても良い 以下の回答はPKUではTLE struct State { double cost; int node; int nextTicket; State(d…

やるだけ int table[0x80]; string encode(int n) { static const string letters = "ixcm"; static const string digits = "0123456789"; string s; for (int i = 0; i < 4; ++i) { int value = n % 10; n /= 10; if (value) { s = letters.substr(i, 1) + …

幾何 図形を何らかの形で正規化して比較する ここでは始点から各点への長さと角度で正規化している typedef complex<double> P; typedef vector<pair<double, double> > Normalized; bool equals(const Normalized& first, const Normalized& second) { if (first.size() != second.size()</pair<double,></double>…

やるだけ int main() { int m; cin >> m; REP(caseIndex, m) { int money, year, n; cin >> money >> year >> n; int bestAnswer = 0; REP(typeIndex, n) { int type, cost; double ratio; cin >> type >> ratio >> cost; if (type) { // 複利 int m = money…

以前公開していた焼きなましライブラリが古くなったので、新しく公開します。そして、以前の記事を編集しようとしたところ、誤って削除してしまいました。もとには戻せないようです・・・。 typedef long long ll; #define REP(i,n) for(int i=0;i<(int)n;++…

間にsshトンネル経由で自宅サーバーのファイルシステムがマウントできたらなぁと思っていたのだが、sshfsというそのまんまのソフトが有ることを知った。早速試してみようと思ったのだが、FUSEが必要となるらしく、いつも使っているWindows+Cygwinでは動かす…

ダイクストラ法 [x座標][y座標][右足/左足]でコストを持たせる [左足x座標][左足y座標][右足x座標][右足y座標]だとTLEだった const int dx[] = {1, 1, 1, 1, 1, 2, 2, 2, 3}; const int dy[] = {2, 1, 0, -1, -2, 1, 0, -1, 0}; static int dp[32][64][2]; s…

やるだけ ケーキに番号を振るやり方を間違えてREを連発してしまった struct Piece { int x, y; Piece() { } Piece(int x, int y) : x(x), y(y) { } }; int main() { for (int n, w, d; cin >> n >> w >> d && (n || w || d); ) { vector<Piece> ps; ps.push_back(Pi</piece>…

やるだけ 時間の分だけ配列を取って塗りつぶしていく方法と、数直線状で扱う方法がある この解答は後者 int main() { for (int N, M; cin >> N >> M && (N || M); ) { int r; cin >> r; vector<vector<pair<int, int> > > loginout(M + 1); REP(i, r) { int t, n, m, s; cin >> t ></vector<pair<int,>…

深さ優先探索 幅優先探索と見せかけておいて、実は最大10手まで 4^10=2^20で通ってしまう const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; int maze[32][32]; int w, h; int answer; bool in(int x, int y) { return 0 <= x && x < w && 0 …

素数 TLEがきついためおそらくエラトステネスの篩が必須 int main() { #define MAX (1024*1024) static bool flag[MAX]; memset(flag, -1, sizeof(flag)); flag[0] = flag[1] = false; for (int i = 2; i * i < MAX; ++i){ if (!flag[i]){ continue; } for (…