AOJ 0042 A Thief

泥棒 | Aizu Online Judge

動的計画法の片鱗を味わった、二重for文でi番目の品物が重さjより軽ければ入れない場合と入れる場合で価値の高い方を選ぶ（dp[i-1][j-w[i]]≠0の時これまで入れた物との合計になる）

#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 1001

int dp[MAX][MAX];
int v[MAX], w[MAX];

int main() {
	int W, n, u = 0;
	char t;
	while (cin >> W) {
		if (W == 0) break;
		cin >> n;
		u++;

		for (int i = 0; i < n; i++) {
			cin >> v[i] >> t >> w[i];
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= W; j++) {
				if (w[i - 1] <= j) {
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
				} else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}

		int mv, mw;
		mv = mw = 0;
		for (int i = 0; i <= W; i++) {
			if (dp[n][i] > mv) {
				mv = dp[n][i];
				mw = i;
			}
		}

		cout << "Case " << u << ":" << endl;
		cout << mv << endl;
		cout << mw << endl;
	}
	return 0;
}

AOJ 0041 Expression

数式 | Aizu Online Judge

順列を作るのが一番悩んだ（低能）

#include <iostream>
#include <cstdio>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; i++)
#define REP(a, b) FOR(a, 0, b)

char opr[3] = { '+','-','*' };

int calc(int a, int b, int c) {
	if (c == 0) return a + b;
	if (c == 1) return a - b;
	return a * b;
}

void permutations(int a, int b, int c, int d) {
	int per[4] = {0};
	REP(i, 4) { REP(j, 4) { REP(k, 4) { REP(l, 4) {
		if (k == i || k == j || i == j || 
			l == i || l == j || l == k) continue;
						
		per[i] = a;
		per[j] = b;
		per[k] = c;
		per[l] = d;

		REP(f, 3) { REP(g, 3) { REP(h, 3) {
			if (calc(calc(per[0], per[1], f), calc(per[2], per[3], h), g) == 10) {
				printf("((%d %c %d) %c (%d %c %d))\n",per[0], opr[f], per[1], opr[g], per[2], opr[h], per[3]);
				return;
			}

			if (calc(calc(calc(per[0], per[1], f), per[2], g), per[3], h) == 10) {
				printf("(((%d %c %d) %c %d) %c %d)\n", per[0], opr[f], per[1], opr[g], per[2], opr[h], per[3]);
				return;
			}
		} } }
	} } } }
	cout << 0 << endl;
}

int main() {
	int a, b, c, d;

	while (cin >> a >> b >> c >> d) {
		if (a == 0 && b == 0 && c == 0 && d == 0) break;

		permutations(a, b, c, d);
	}
	return 0;
}

AOJ 0040 Affine Cipher

アフィン暗号 | Aizu Online Judge
αとβの値をα,β > 0の範囲で総当たりして解いた(今のテストケースだとαもβも27ぐらいまでに絞れる)

REPマクロ初めて書いた

#include <iostream>
#include <string>
using namespace std;

#define rep(a, b, i) for(int i = a; i < b; i++)

char ch(int a, int b, int c) {
	return (a * (c - 'a') + b) % 26 + 'a';
}

int main() {
	int n, a, b, c;
	cin >> n;
	cin.ignore();

	string str, res = "";
	for (; n > 0; n--) {
		getline(cin, str);

		rep(1, 27, a) {
			if (a == 2 || a == 13) continue;
			rep(1, 27, b) {
				res = str;
				c = 0;
				rep(0, str.size(), c) {
					if (res[c] == ' ') continue;

					res[c] = ch(a, b, res[c]);
				}
				if (res.find("this") != -1 || res.find("that") != -1) {
					cout << res << endl;
					a = 114514;
					b = 114514;
				}
			}
		}
	}
	return 0;
}

AOJ 0039 Roman Figure

ローマ数字 | Aizu Online Judge

何でもいい（何でもいいとは言っていない）ある程度大きな数を適当に決めるとき114514にする癖がついた、そのうちに治そう...

#include <iostream>
#include <string>
#include <map>
using namespace std;
 
int main() {
    map<char, int> m;
    m['I'] = 1;
    m['V'] = 5;
    m['X'] = 10;
    m['L'] = 50;
    m['C'] = 100;
    m['D'] = 500;
    m['M'] = 1000;
 
    string str = "";
    int sum, n;
    while (cin >> str) {
        sum = 0;
        n = 114514;
        for (int i = 0; i < str.size(); i++) {
            if (m[str[i]] <= n) {
                n = m[str[i]];
                sum += n;
            } else {
                sum += m[str[i]];
                sum -= (n * 2);
                n = 114514;
            }
        }
        cout << sum << endl;
    }
    return 0;
}

AOJ 0038 Poker Hand

ポーカー | Aizu Online Judge

分岐だけ、

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

string pairs[2][3] = { {"null","one pair","two pair"},
					  {"three card","full house",""} };

int main() {
	int n[5], c, three, two;
	while (scanf("%d,%d,%d,%d,%d",&n[0],&n[1],&n[2],&n[3],&n[4]) != EOF) {
		int card[13] = { 0 }, c = 0, three = 0, two = 0;
		for (int i = 0; i < 5; i++) {
			card[n[i] - 1]++;
		}

		for (int i = 0; i < 13; i++) {
			if (card[i] == 4) {
				c = 114514;
				break;
			} else if (card[i] == 3) {
				three++;
			} else if (card[i] == 2) {
				two++;
			} else if (card[i] == 1) {
				c++;
				if (c == 5) {
					break;
				}

				if (c == 4 && i == 12 && card[0] == 1) {
					c = 5;
					break;
				}
			} else if(card[i] == 0 && c != 0) {
				c = 0;
			}
		}

		if (c == 5) {
			cout << "straight" << endl;
		} else if (c == 114514) {
			cout << "four card" << endl;
		} else {
			cout << pairs[three][two] << endl;
		}
	}

	return 0;
}