POJ 1313 Booklet Printing
問題
略
やりかた
見開きのページ番号の和はどの見開きであっても一定（ページ数以上の最小の4の倍数+1になる）になるので片一方の番号がわかれば見開きのもう片方の番号は自動的に決まる。コード上では見開き上の若番の番号から老番のページ番号を求めて、それが与えられたページ数以上になる場合には老番の位置に"Blank"を出力しておけばいい。ただ若番もページ数以上になる場合があるのでその時は表示しないようにする。
以下ソース。
int main(int argc, char **argv){ int n; while(cin >> n, n){ int sheet = (n + 3) / 4; cout << "Printing order for " << n << " pages:" << endl; for(int i = 1; i <= sheet; i++){ int fr = 2 * i - 1; int bl = 2 * i; int fl = sheet * 4 + 1 - fr; int br = sheet * 4 + 1 - bl; cout << "Sheet " << i << ", front: "; if(fl > n) cout << "Blank, "; else cout << fl << ", "; cout << fr << endl; if(bl <= n){ cout << "Sheet " << i << ", back : "; cout << bl << ", "; if(br > n) cout << "Blank"; else cout << br; cout << endl; } } } return 0; }
POJ 1248 Safecracker
問題
やりかた
与えられる文字列の長さはせいぜい12文字なので、全探索でも1ケースあたり程度の計算でOKなので全探索で。
ただvectorやstringを引数に関数の値渡しをすると簡単にTLEしてしまった。参照渡しにしたら簡単に通った。
以下ソース。
vector<ll> c(5); ll calc(string &s){ for(int i = 0; i < 5; i++) c[i] = s[i] - 'A' + 1; return c[0] - c[1] * c[1] + c[2] * c[2] * c[2] - c[3] * c[3] * c[3] * c[3] + c[4] * c[4] * c[4] * c[4] * c[4]; } int main(int argc, char **argv){ ll d; string s; while(cin >> d >> s){ if(d == 0 && s == "END") break; sort(ALL(s)); int L = s.length(); string ans("AAAAA"); string str("AAAAA"); for(int S = 0; S < 1 << L; S++){ if(__builtin_popcount(S) != 5) continue; int idx = 0; for(int i = 0; i < L; i++) if(S >> i & 1) str[idx++] = s[i]; do{ if(calc(str) == d) ans = max(ans, str); }while(next_permutation(ALL(str))); } if(ans == "AAAAA") cout << "no solution" << endl; else cout << ans << endl; } return 0; }
POJ 3670 Eating Together
問題
1～3の数字からなる数列がある。この数列を単調非減少もしくは単調非増加にするために書き換える必要のある数字は最小でいくつか求めよ。なお数字は1～3にしか書き換えられない。
やりかた
DPでやった。
数列のうちの単調非減少なLISの長さをもとめると、それが書き換えなくて良い数字の数になる。なので数列の大きさからこの数を引くと書き換え無くてはならない数の個数になる。単調非増加についてももとめるため、数列をreverseしてもう一度同じことをやる。
TLEしないようO(NlogN)のやりかたでやる必要あり。
他の人のページを見るともっと良いやり方だった。。
using namespace std; int dp[30010]; int main(int argc, char **argv){ int N; scanf("%d", &N); vector<int> a(N); for(int i = 0; i < N; i++) scanf("%d", &a[i]); int ans = INF; for(int k = 0; k <= 1; k++){ FILL(dp, INF); for(int i = 0; i < N; i++) *upper_bound(dp, dp + N, a[i]) = a[i]; ans = min(ans, N - (int)(lower_bound(dp, dp + N, INF) - dp)); reverse(ALL(a)); } printf("%d\n", ans); return 0; }
POJ 3660 Cow Contest
問題
1からNまでのラベルが付いたノードが与えられる。このグラフの有効辺がM個与えられる。トポロジカル順序が厳密に決まっているノード数を返せ。
やりかた
トポロジカルソートできるグラフだとして、あるノードのトポロジカル順序が厳密に決まっている場合は、自分以外のノード全てで
- 自分からそのノードへ到達できる
- そのノードから自分へ到達できる
のどちらかに分類できる場合である。どちらも成立する場合はループが起きているのでNG。どちらも成立しない場合は2ノード間で順序が定まらないのでNG。これに適合するノードの数を数えればいい。
ワーシャルフロイドで接続関係を調べたのでO(V^3)。
以下ソース。
int main(int argc, char **argv){ int N, M; scanf("%d %d", &N, &M); vector<vector<bool> > E(N, vector<bool>(N, false)); for(int i = 0; i < M; i++){ int s, t; scanf("%d %d", &s, &t); E[t - 1][s - 1] = true; } for(int i = 0; i < N; i++) E[i][i] = true; for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) E[i][j] = E[i][j] | (E[i][k] && E[k][j]);//Warshall-Floyd int ans = 0; for(int i = 0; i < N; i++){ int cnt = 0; for(int j = 0; j < N; j++) if(i != j) cnt += (E[i][j] ^ E[j][i]);//i->jかj->iのどちらかのみが成立するケースを数える ans += (cnt == N - 1); } cout << ans << endl; return 0; }
POJ 3194 Equidivisions
問題
nxnのマスに1～nまでの数字がn個ずつ割り振られている。同じ数字が割り振られているマスがすべて4-連結しているか判定せよ。
入力形式が少しわかりにくくて、各テストケースのi行目が数字iを持つマスのy座標、x座標を連続で表している。テストケースはn-1行目までしかなく、nの数字を持つマスは1～n-1行目までに出てこないマスという考え方。
やりかた
単純にconnected component labelingして、あるラベルの連結している数を数えてきちんとn個になっているか調べればいい。
以下ソース。
int N; int f[101][101]; int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; void rec(int y, int x, int idx){ f[y][x] = -1; for(int i = 0; i < 4; i++){ int ny = y + dy[i], nx = x + dx[i]; if(0 <= nx && nx < N && 0 <= ny && ny < N && f[ny][nx] == idx) rec(ny, nx, idx); } } int main(int argc, char **argv){ while(cin >> N, N){ memset(f, -1, sizeof(f)); for(int i = 0; i < N - 1; i++){ for(int j = 0; j < N; j++){ int y, x; cin >> y >> x; f[y - 1][x - 1] = i; } } for(int i = 0; i < N * N; i++) if(f[i / N][i % N] == -1) f[i / N][i % N] = N - 1; for(int i = 0; i < N; i++){ for(int y = 0; y < N; y++) for(int x = 0; x < N; x++) if(f[y][x] == i){ rec(y, x, i); goto L1; } L1:; } bool good = true; for(int y = 0; y < N; y++) for(int x = 0; x < N; x++) if(f[y][x] != -1) good = false; cout << (good ? "good" : "wrong") << endl; } return 0; }
POJ 1308 Is It A Tree?
問題
グラフ上のノード番号が2つずつ入力される。前者から後者のノードへは有向辺が伸びているものとする。このグラフがひとつの木になっているか判定せよ。なお入力は複数のテストケースからなり、0 0がそのケースの入力の終わりを表し、2つとも負の数が与えられた場合はすべてのテストケースの入力の終わりを表す。
やりかた
有向グラフが木構造になるのはルートの入次数が0になり、それ以外のノードの入次数が1の時。なので入次数が0のノードが1つでない場合や入次数が2以上あるノードがあれば木にはならない。
ただこの方法だと連結でないグラフであるケースを検出できないので、UnionFindで入力をくっつけていってひとつの木になるか判定した。
なお、ノードがひとつもない場合は木であると判定するようだ。
以下ソース。
//UnionFindのコードは略 int deg[20001]; int main(int argc, char **argv){ int idx = 1; while(1){ int a, b; set<int> node; UnionFind uf; fill(deg, deg + 20000, 0); while(scanf("%d %d", &a, &b), a + b){ if(a <= -1 && b <= -1) goto L1; deg[b]++;//入次数をカウント node.insert(a); node.insert(b); uf.unite(a, b); } int root = 0; bool tree = true; for(set<int>::iterator it = node.begin(); it != node.end(); it++){ int c = *it; if(deg[c] >= 2) tree = false;//入次数が2より大きいのはダメ if(!uf.same(*(node.begin()), c)) tree = false;//連結でないグラフだったらダメ if(deg[c] == 0) root++; } if(root != 1 && !node.empty()) tree = false;//ルートがひとつ以上あるものはダメ printf("Case %d is %s\n", idx++, tree ? "a tree." : "not a tree."); } L1:; return 0; }
ノードが1から順になっていないのがうざい。
POJ 3364 Black and white painting
問題
n x mの市松模様が与えられる。右下が白の場合はc = 1、黒の場合はc = 0である。
8 x 8のチェスボードはこの中にいくつあるか返せ。
やりかた
チェスボードを模様の中で動かすことを想定すると、チェスボードの左上が動ける範囲は、模様の左上から(n - 7) * (m - 7)の中にある。この中にある白のマスの数を数えればいい。
cの値と(n - 7) * (m - 7)の偶奇によって答えが少し違うので注意。ただ絵を書いてみればすぐわかるはず。
以下ソース。
int main(int argc, char **argv){ int n, m, c; while(cin >> n >> m >> c, n + m + c){ n -= 7, m -= 7; if((n * m) & 1) cout << (n * m) / 2 + c << endl; else cout << n * m / 2 << endl; } }
Get up! 明日のSUPER ST@R!
