AOJ 0093 Leap Year
概要
a年からb年までの閏年を求めよ。
解法
is_uruuを実装する
コード
#include <iostream> using namespace std; bool is_uruu(int y) { return (y % 4 == 0 && y % 100 != 0 || y % 400 == 0) ? true : false; } int main() { int a, b, flag = 1; while (1) { cin >> a >> b; if (a == 0 && b == 0) break; if (flag == 0) { puts(""); flag = 1; } for (int i = a; i <= b; i++) { if (is_uruu(i)) { cout << i << endl; flag = 0; } } if (flag) cout << "NA" << endl; flag = 0; } return 0;
AOJ 0096 Sum of 4 Integers II
概要
nが与えられたとき、a + b + c + d = n
となる組み合わせ数を求めよ。
解法
全探索だと、1000^4 なので間に合わない。
DP[i個目][合計]で数え上げをする。
コード
#include <iostream> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) int main() { long long dp[4][4001] = {}; REP(i, 1001) dp[0][i] = 1; for (int i = 1; i < 4; i++) { for (int j = 4000; j >= 0; j--) { for (int k = 0; k <= 1000; k++) { if (j - k < 0) break; dp[i][j] += dp[i - 1][j - k]; } } } while (1) { int n; cin >> n; if (cin.eof()) break; cout << dp[3][n] << endl; } return 0; }
AOJ 0089 The Shortest Path on A Rhombic Path
概要
ひし形上に並べられた整数が与えられる。
一番上から左下か右下に移動していったとき、
通過した整数の和の最大値を出力せよ。
解法
動的計画法で解く。
コード
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <cstdlib> #include <string> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) vector<int> parse(string s, char c) { int pre = 0; vector<int> v; for (int i = 0; i < s.length(); i++) { if (s[i] == c) { v.push_back(atoi(s.substr(pre, i - pre).c_str())); pre = i + 1; } } v.push_back(atoi(s.substr(pre, s.length() - pre).c_str())); return v; } int main() { int m[100][100], mx, sz; string s; REP(i, 100) REP(j, 100) m[i][j] = -1; for (sz = 0; getline(cin, s); sz++) { vector<int> v = parse(s, ','); REP(i, v.size()) m[sz][i] = v[i]; } int dp[100][100] = { m[0][0] }; for (int i = 1; i < sz; i++) { if (i >= sz / 2) { for (int j = 0; j < i + 1; j++) { dp[i][j] = m[i][j] + max(dp[i - 1][j], dp[i - 1][j + 1]); } } else { for (int j = 0; j < sz - i; j++) { dp[i][j] = m[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j]); } } } cout << dp[sz - 1][0] << endl; return 0; }
AOJ 0069 Drawing Lots II
概要
あみだくじに、新しく1本線を引いてゴールに行けるか。
解法
左上から、線引けるところを全探索
コード
#include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; int n, m, g, d; int check(int line[30][10]) { int now = m-1; for (int i = 0; i < d; i++) { now += line[i][now]; } return (now == g - 1) ? 1 : 0; } int main() { while (1) { int line[30][10] = { 0 }; string s; int flag = 0; // 入力 cin >> n; if (n == 0) break; cin >> m >> g >> d; memset(line, 0, sizeof(line)); for (int i = 0; i < d; i++) { cin >> s; for (int j = 0; j < s.size(); j++) { if (line[i][j] != 0) continue; line[i][j] = s[j] - '0'; line[i][j+1] = -(s[j] - '0'); } } // 線を引かない if (check(line)) { puts("0"); continue; } // 線を引く for (int i = 0; i < d; i++) { for (int j = 0; j < n; j++) { if (line[i][j] != 0) continue; if (j > 0 && line[i][j - 1] == 1) continue; if (line[i][j + 1] != 0) continue; // 引く line[i][j + 1] = -1; line[i][j] = 1; // 調べる if (check(line)) { printf("%d %d\n", i + 1, j + 1); flag = 1; break; } // 戻す line[i][j + 1] = 0; line[i][j] = 0; } if (flag) break; } if (flag == 0) { puts("1"); } } return 0; }
AOJ 0057 The Number of Area
概要
領域をn本の線で分割する。
このとき、最大の領域の数を求めよ。
解法
n = 1のとき
どこに線を引いても領域は2つになります。
n = 2のとき
先ほど引いた線と交差させることで、4つの領域を作ることができます。
n = 3のとき
図のように線を引くと、3つの領域を二分割できるため、合計7
n = 4のとき
図のように線を引くことで、4つの領域を二分割できるため、合計11
7
このように、nのとき、領域を新たにnだけ増やすことができることが分かります。
つまり、n本のとき、2+3+4+・・・・+n 個の領域が作れることになります。
なのでΣn + 1で求めることができそうです。
Σnは、公式を用いて、Σn = n * (n + 1) / 2 で計算できます。
コード
#include <iostream> using namespace std; int main() { while (1) { int n; cin >> n; if (cin.eof()) break; cout << 1 + n * (n + 1) / 2 << endl; } return 0; }
AOJ 0056 Goldbach's Conjecture
概要
二つの素数の和がnとなる組み合わせの数を求めよ
コード
#include <iostream> #include <cstdio> #include <vector> using namespace std; vector<int> sieveOfEratosthenes(int n) { vector<int> arr(n + 1); vector<int> prime; for (int i = 0; i <= n; i++) arr[i] = 1; arr[0] = arr[1] = 0; for (int i = 2; i*i < n; i++) if (arr[i]) for (int j = i * i; j < n; j += i) arr[j] = 0; for (int i = 2; i <= n; i++) { if (arr[i] == 1) prime.push_back(i); } return prime; } int main() { vector<int> prime = sieveOfEratosthenes(60000); int ans[50001] = {0}; int n; int size = prime.size(); for (int i = 0; i < size; i++) { for (int j = i; j < size; j++) { if (prime[i] + prime[j] > 50000) continue; ans[prime[i] + prime[j]]++; } } while (1) { cin >> n; if (n == 0) break; cout << ans[n] << endl; } return 0; }
AOJ 0054 Sum of Nth decimal places
概要
a / b の小数点第1位から第n位までの値を足せ
解法
最初doubleでやっていたけど、精度で死んだ。
aを10倍しながら、bで割っていくと少数部分が計算できるらしい。
これは使える。
コード
#include <iostream> using namespace std; int main() { int a, b, n; while (1) { cin >> a >> b >> n; if (cin.eof()) break; int ans = 0; a %= b; for (int i = 0; i < n; i++) { a *= 10; ans += a / b; a %= b; } cout << ans << endl; } return 0; }
