AGC001 B - Mysterious Light
やり直し
B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder
正三角形中の光の経路の長さを求める問題。
解法
f(a, b) := 辺の長さがaとbの平行四辺形の中を光が、2回反射するまでに進む距離とする。
2回反射する時点でまた平行四辺形ができる。
a < bの時、
f(a, b) = f(a, b - a) + 2a
f(a, a) = a
を満たす。
再帰的に計算していけばOKだが辺の長さが≦1012なのでTLEしてしまう。
そこで式を、
a < bの時、
f(a, b) = f(a, b%a) + 2a * (b / a)
b % a == 0の時、
f(a, b) = 2a * (b / a) - a
とすればOK。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; ll f(ll a, ll b) { ll x = min(a, b); ll y = max(a, b); if(y % x == 0) return y / x * x * 2 - x; return 2 * x * (y / x) + f(x, y % x); } int main() { ios::sync_with_stdio(false); cin.tie(0); ll N, X; cin >> N >> X; cout << N + f(X, N - X) << endl; return 0; }
ABC075参加記録
100-200-300-400だったので全完できた！
実装がいつものABCより重い気がした。
A - One out of Three
A == BならCを出力
B == CならAを出力
C == AならBを出力
int main() { ios::sync_with_stdio(false); cin.tie(0); int a,b,c; cin >> a >> b >> c; if(a == b) cout << c << endl; if(b == c) cout << a << endl; if(a == c) cout << b << endl; return 0; }
B - Minesweeper
'.'の周りの8マスの'#'の個数を数える。
int main() { ios::sync_with_stdio(false); cin.tie(0); int H, W; cin >> H >> W; vector<string> vs(H); FOR(i,0,H) cin >> vs[i]; int vy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int vx[8] = {0, 1, 1, 1, 0, -1, -1, -1}; FOR(h,0,H) { FOR(w,0,W) { if(vs[h][w] == '.') { int cnt = 0; FOR(i,0,8) { int y = h + vy[i]; int x = w + vx[i]; if(y >= 0 && y < H && x >= 0 && x < W && vs[y][x] == '#') cnt++; } vs[h][w] = char('0' + cnt); } } } FOR(i,0,H) cout << vs[i] << endl; return 0; }
C - Bridge
辺を1本ずつ取り除いてワーシャルフロイドを使った。
ある辺を取り除いてワーシャルフロイドし、全ての頂点間で移動可能かどうか判定し、不可能な頂点の組みがあったらans++する。
const int inf = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(0); // ワーシャルフロイド int n,m;// 頂点、辺 cin >> n >> m; int a[100], b[100], c[100], dist[100][100]; CLR(a);CLR(b);CLR(c); FOR(i,0,m){ cin >> a[i] >> b[i]; a[i]--;b[i]--; c[i] = 1; } int ans = 0; FOR(t,0,m) { FOR(i,0,n){ FOR(j,0,n){ if(i==j) dist[i][j] = 0; else dist[i][j] = inf; } } // 連結してるとこはcを代入 FOR(i,0,m){ if(i == t) continue; dist[a[i]][b[i]] = min(dist[a[i]][b[i]], c[i]); dist[b[i]][a[i]] = min(dist[b[i]][a[i]], c[i]); } FOR(k,0,n) FOR(i,0,n) FOR(j,0,n) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } bool brk = false; FOR(i,0,n) { FOR(j,0,n) { if(dist[i][j] == inf) { ans++; brk = true; break; } } if(brk) break; } } cout << ans << endl; return 0; }
普通にDFSで到達可能か調べればよかった。
D - Axis-Parallel Rectangle
長方形は無限に作れるが、同じ点を含む長方形で面積が一番小さい長方形は、4辺に点がある(角に点がある場合は2辺に点があると考える)長方形である。よって考える長方形は4辺に点がある長方形だけで良い。
x軸に平行な辺上の2点と、y軸に平行な辺上の2点を全探索。
int main() { ios::sync_with_stdio(false); cin.tie(0); int N, K; cin >> N >> K; ll x[N], y[N]; FOR(i,0,N) cin >> x[i] >> y[i]; ll ans = 4e18; // x方向2つの点 FOR(i,0,N) { FOR(j,0,N) { if(i == j || x[i] >= x[j]) continue; // y方向2つの点 FOR(k,0,N) { FOR(l,0,N) { if(k == l || y[k] <= y[l]) continue; if(x[i] <= x[k] && x[j] >= x[k] && x[i] <= x[l] && x[j] >= x[l]) { if(y[i] <= y[k] && y[i] >= y[l] && y[j] <= y[k] && y[j] >= y[l]) { int cnt = 0; FOR(c,0,N) { if(x[c] >= x[i] && x[c] <= x[j] && y[c] <= y[k] && y[c] >= y[l]) cnt++; } if(cnt >= K) { ans = min(ans, (x[j] - x[i]) * (y[k] - y[l])); } } } } } } } cout << ans << endl; return 0; }
ABC023 D - 射撃王
D: 射撃王 - AtCoder Beginner Contest 023 | AtCoder
解説
最小値をx[m]以下にできるかどうかで二分探索。
tを風船iがx[m]を超えない時間とすると、
H_i + t * S_i = xより、
t = (x - H_i) / S_i
となる。これが風船iを割らなければいけない制限時間である。全ての風船の制限時間を求め、制限時間の小さい方から0秒から割っていく。制限時間を超えてしまう風船があったらx[m]以下にできない。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int N; ll H[100005], S[100005]; // x[m]以下にできるかどうか bool calc(ll x) { int T[N]; FOR(i,0,N) { if(x - H[i] < 0) return false; T[i] = min((ll)111110, (x - H[i]) / S[i]); } sort(T, T + N); FOR(i,0,N) if(T[i] < i) return false; return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N; FOR(i,0,N) cin >> H[i] >> S[i]; ll l = 0, r = 1e16; while(r - l > 1) { ll m = (r + l) / 2; if(calc(m)) r = m; else l = m; } if(!calc(r)) r = l; cout << r << endl; return 0; }
AGC019 B - Reverse and Compare
やり直し B: Reverse and Compare - AtCoder Grand Contest 019 | AtCoder
問題概要
- 英小文字からなる文字列A(|A|≦200,000)が与えられる
- Aの英小文字2つを選んでそれを両端とする文字列を反転させることを1回まで行う
- 何通りの文字列ができるか
解法
A = abcdbの時
両端の組み合わせは5C2あるが、
bcdb を反転させた文字列と cd を反転させた文字列は同じである。
両端が同じ英小文字を選ぶ場合は重複してカウントしてしまうので5C2から1引く必要がある。
aが何個あるか、bが何個あるか、cが...zが何個あるか数えて重複する部分を引けば良い。
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); string A; cin >> A; ll len = A.length(); ll cnt[26]; CLR(cnt); FOR(i,0,len) cnt[A[i]-'a']++; ll ans = len * (len - 1) / 2; FOR(i,0,26) { if(cnt[i] >= 2) { ans -= cnt[i] * (cnt[i] - 1) / 2; } } cout << ans + 1 << endl; return 0; }
AOJ 2199 - Differential Pulse Code Modulation
Differential Pulse Code Modulation | Aizu Online Judge
解説
dp[i][j] := i個目の信号まででyがjのときの最小値
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; ll dp[20004][256]; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; while(cin>>N>>M,N||M) { int c[M]; FOR(i,0,M) cin >> c[i]; int x[N]; FOR(i,0,N) cin >> x[i]; FOR(i,0,N+1) FOR(j,0,256) dp[i][j] = 1e18; dp[0][128] = 0; FOR(i,0,N) { FOR(j,0,256) { if(dp[i][j] == 1e18) continue; FOR(k,0,M) { int y = max(0, min(255, j + c[k])); dp[i+1][y] = min(dp[i+1][y], dp[i][j] + (ll)(x[i]-y) * (ll)(x[i]-y)); } } } ll ans = 1e18; FOR(i,0,256) ans = min(ans, dp[N][i]); cout << ans << endl; } return 0; }
ARC064 D - An Ordinary Game
やり直し
D: An Ordinary Game - AtCoder Regular Contest 064 | AtCoder
解説
ゲームが終了する直前に文字列がどうなっているか考えると良い。(頭いいな〜)
- 両端が同じ時
abab...a
->直前は奇数個
よって与えられた文字列が奇数の時はSecondの勝ち（firstとsecondが文字をとるときの文字列の奇遇は変わらないので）
- 両端が異なる時
abab...b
->直前は偶数個
よって与えられた文字列が偶数の時はSecondの勝ち
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { string s; cin >> s; if(s[0] == s[s.length()-1]) { if(s.length() % 2 == 1) puts("Second"); else puts("First"); } else { if(s.length() % 2 == 0) puts("Second"); else puts("First"); } return 0; }
DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 参加記録
DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 - AtCoder
ABCの3完、Dは方針はあってたっぽいけど実装が詰められなくて死亡。234位。19年卒じゃない枠で100位以内は本戦だけどきついな〜。
A - DDCC型文字列
やるだけ。
int main() { ios::sync_with_stdio(false); cin.tie(0); string s; cin >> s; if(s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
B - 鉛筆
これもやるだけ。
int main() { ios::sync_with_stdio(false); cin.tie(0); ll A, B, C, D; cin >>A >>B>>C>>D; cout << A * 1728 + B * 144 + C * 12 + D << endl; return 0; }
C - 収納
昇順にソートして、貪欲に、箱に入れてない一番大きい棒と一番小さい棒を一緒に入れられたら入れる、入れられないなら大きいのだけ入れる。
int main() { ios::sync_with_stdio(false); cin.tie(0); int N, C; cin >> N >> C; vector<int> L(N); FOR(i,0,N) cin >> L[i]; sort(L.begin(), L.end()); int l = 0, r = N - 1; int ans = 0; while(1) { if(l == r) { ans++; break; } if(l > r) break; if(L[l] + L[r] + 1 <= C) { ans++; r--; l++; } else { ans++; r--; } } cout << ans << endl; return 0; }
D - 石
南北、東西どちらも対称ではない状態ー＞どちらかが対称の状態ー＞どちらも対称の状態になるように取っていくのが良い。
int main() { int H, W, A, B; cin >> H >> W >> A >> B; vector<string> vs(H); FOR(i,0,H) cin >> vs[i]; int s = 0; FOR(i,0,H) FOR(j,0,W) s += vs[i][j] == 'S'; int ch = 0, cw = 0, chw = 0; FOR(i,0,H/2) { FOR(j,0,W/2) { int cnt = 0; if(vs[i][j] == 'S' && vs[i][W-j-1] == 'S') cw++, cnt++;; if(vs[i][W-j-1] == 'S' && vs[H-i-1][W-j-1] == 'S') ch++, cnt++; if(vs[H-i-1][W-j-1] == 'S' && vs[H-i-1][j] == 'S') cw++, cnt++; if(vs[H-i-1][j] == 'S' && vs[i][j] == 'S') ch++, cnt++; if(cnt == 4) { chw ++; ch -= 2; cw -= 2; } } } //cout << ch << cw << chw << endl; int ans1 = 0, ans2 = 0; // 南北 if(ch > 0 && ch * 2 + chw * 4 != s) ans1 += A; ans1 += max(0, (ch - 1)) * A; if(chw > 0 && chw * 4 != s) ans1 += A + B; ans1 += max(0, (chw - 1)) * (A + B); ans1 += chw * max(A, B); ans1 += A + B; // 東西 if(cw > 0 && cw * 2 + chw * 4 != s) ans2 += B; ans2 += max(0, (cw - 1)) * B; if(chw > 0 && chw * 4 != s) ans2 += A + B; ans2 += max(0, (chw - 1)) * (A + B); ans2 += chw * max(A, B); ans2 += A + B; cout << max(ans1, ans2) << endl; return 0; }
ごめんなさい↓
