AOJ 0109: Smart Calculator
ちまちま読んでいたThe Rust Programming Languageをようやく読み終わった。 Rustで再帰下降構文解析を書きたかったので構文解析のオーソドックスな問題を解くことにした。
いきなりRustで書くのは厳しいためまずはC++で解いた。 構文解析 Howto · GitHubを参考にした。
解析すべき構文は基本的に
<四則演算の式> ::= <乗算除算の式> (+ or -) <乗算除算の式> (+ or -) ... <乗算除算の式> ::= <括弧か数> (* or /) <括弧か数> (* or /) ... <括弧か数> ::= '(' <四則演算の式> ')' or <数> <数> ::= ...
である(この問題では式の終わりに=
が来ることが指定されているが、数字でも演算子でもカッコでもない文字が来たら終了するコードになっているのであまり考えていない)
これを解くプログラムは以下のようになる。
#include <bits/stdc++.h> using namespace std; typedef string::const_iterator State; int number(State &begin); int factor(State &begin); int term(State &begin); int expression(State &begin); int expression(State &begin) { int ret = term(begin); for (;;) { if (*begin == '+') { begin++; ret += term(begin); } else if (*begin == '-') { begin++; ret -= term(begin); } else { break; } } return ret; } int term(State &begin) { int ret = factor(begin); for (;;) { if (*begin == '*') { begin++; ret *= factor(begin); } else if (*begin == '/') { begin++; ret /= factor(begin); } else { break; } } return ret; } int factor(State &begin) { int ret = 0; if (*begin == '(') { begin++; ret = expression(begin); begin++; return ret; } else { ret = number(begin); } return ret; } int number(State &begin) { int ret = 0; while (isdigit(*begin)) { ret *= 10; ret += *begin - '0'; begin++; } return ret; } int main() { int N; cin >> N; cin.ignore(); for (int i = 0; i < N; i++) { string s; getline(cin, s); State begin = s.begin(); int ans = expression(begin); cout << ans << endl; } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4049138
このコードを素直にRustにしたらこうなった。
C++のstring::const_iterator
の代わりにstd::iter::Peekable<std::str::Chars>
を使っている。
use std::io; fn parse(input: &String) -> i32 { let mut it = input.chars().peekable(); expression(&mut it) } fn expression(it: &mut std::iter::Peekable<std::str::Chars>) -> i32 { let mut ret = term(&mut *it); loop { let c = it.peek().unwrap(); match c { '+' => { it.next(); ret += term(&mut *it); } '-' => { it.next(); ret -= term(&mut *it); } ')' | '=' => { break; } _ => { panic!("Invalid character: {}", c); } } } ret } fn term(it: &mut std::iter::Peekable<std::str::Chars>) -> i32 { let mut ret = factor(&mut *it); loop { let c = it.peek().unwrap(); match c { '*' => { it.next(); ret *= factor(&mut *it); } '/' => { it.next(); ret /= factor(&mut *it); } _ => { break; } } } ret } fn factor(it: &mut std::iter::Peekable<std::str::Chars>) -> i32 { let c = it.peek().unwrap(); match c { '(' => { it.next(); let ret = expression(&mut *it); it.next(); return ret; } '0'..='9' => { return number(&mut *it); } _ => { panic!("Invalid character: {}", c); } } } fn number(it: &mut std::iter::Peekable<std::str::Chars>) -> i32 { let mut ret = 0; while it.peek().unwrap().is_numeric() { ret *= 10; ret += it.peek().unwrap().to_digit(10).unwrap() as i32; it.next(); } ret } fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let n: i32 = buf.trim().parse().unwrap(); for _ in 0..n { let mut line = String::new(); io::stdin().read_line(&mut line).unwrap(); println!("{}", parse(&line)); } }
AOJのRustコンパイラが古いため、このコードはコンパイルが通らなかった。 古いRustの書き方を学ぶことが目的ではないのでテストケースを落としてきて、出力が一致することを確認したのでこれでよしとする。
AOJ ITP1 (Rust)
https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/all
1_A: Hello World
fn main() { println!("Hello world"); }
1_B: X Cubic
use std::io; fn main() { let mut x = String::new(); io::stdin().read_line(&mut x).unwrap(); let x: i32 = x.trim().parse().unwrap(); println!("{}", x.pow(3)); }
1_C: Rectangle
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let a: i32 = iter.next().unwrap().parse().unwrap(); let b: i32 = iter.next().unwrap().parse().unwrap(); println!("{} {}", a * b, 2 * (a + b)); }
1_D: Watch
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let S: i32 = buf.trim().parse().unwrap(); println!("{}:{}:{}", S / 3600, S % 3600 / 60, S % 60); }
2_A: Small, Large, or Equal
use std::cmp::Ordering; use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let a: i32 = iter.next().unwrap().parse().unwrap(); let b: i32 = iter.next().unwrap().parse().unwrap(); println!( "a {} b", match a.cmp(&b) { Ordering::Less => "<", Ordering::Greater => ">", Ordering::Equal => "==", } ); }
2_B: Range
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let a: i32 = iter.next().unwrap().parse().unwrap(); let b: i32 = iter.next().unwrap().parse().unwrap(); let c: i32 = iter.next().unwrap().parse().unwrap(); if a < b && b < c { println!("Yes"); } else { println!("No"); } }
2_C: Sorting Three Numbers
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let mut v = [0, 0, 0]; for i in 0..3 { v[i] = iter.next().unwrap().parse().unwrap(); } v.sort(); println!("{} {} {}", v[0], v[1], v[2]); }
2_D: Circle in a Rectangle
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let W: i32 = iter.next().unwrap().parse().unwrap(); let H: i32 = iter.next().unwrap().parse().unwrap(); let x: i32 = iter.next().unwrap().parse().unwrap(); let y: i32 = iter.next().unwrap().parse().unwrap(); let r: i32 = iter.next().unwrap().parse().unwrap(); if x >= r && x <= W - r && y >= r && y <= H - r { println!("Yes"); } else { println!("No"); } }
3_A: Print Many Hello World
fn main() { for _ in 0..1000 { println!("Hello World"); } }
3_B: Print Test Cases
use std::io; fn main() { let mut i = 1; loop { let mut buf = String::new(); io::stdin().read_line(&mut buf).ok(); let x: i32 = buf.trim().parse().unwrap(); if x == 0 { break; } println!("Case {}: {}", i, x); i += 1; } }
3_C: Swapping Two Numbers
use std::io; fn main() { loop { let mut buf = String::new(); io::stdin().read_line(&mut buf).ok(); let mut iter = buf.split_whitespace(); let x: i32 = iter.next().unwrap().parse().unwrap(); let y: i32 = iter.next().unwrap().parse().unwrap(); if x == 0 && y == 0 { break; } if x < y { println!("{} {}", x, y); } else { println!("{} {}", y, x); } } }
3_D: How Many Divisors?
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).ok(); let mut iter = buf.split_whitespace(); let a: i32 = iter.next().unwrap().parse().unwrap(); let b: i32 = iter.next().unwrap().parse().unwrap(); let c: i32 = iter.next().unwrap().parse().unwrap(); let mut ans = 0; for i in a..b + 1 { if c % i == 0 { ans += 1; } } println!("{}", ans); }
4_A: A / B Problem
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let a: i32 = iter.next().unwrap().parse().unwrap(); let b: i32 = iter.next().unwrap().parse().unwrap(); println!("{} {} {}", a / b, a % b, (a as f64) / (b as f64)); }
4_B: Circle
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let r: f64 = iter.next().unwrap().parse().unwrap(); let pi: f64 = std::f64::consts::PI; println!("{} {}", r * r * pi, 2.0 * r * pi); }
4_C: Simple Calculator
最初はop
をchar
で読み込むコードを書いていて手元では正しく動作していたが、AOJで使われているバージョンのRustではCompile ErrorだったのでStringを使うことにした。
use std::io; fn main() { loop { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let a: i32 = iter.next().unwrap().parse().unwrap(); let op: String = iter.next().unwrap().parse().unwrap(); let b: i32 = iter.next().unwrap().parse().unwrap(); println!( "{}", match op.as_ref() { "+" => a + b, "-" => a - b, "*" => a * b, "/" => a / b, "?" => break, _ => panic!("Invalid operation!"), } ); } }
4_D: Min, Max and Sum
n a_1 a_2 ... a_n
という形式の入力をどう受け取ればいいのかよく分からなかった。
調べると出てくるtanakhさんのマクロを参考にread_to_string()
を使ったらそれっぽい動作にすることができたが、ターミナルで実行するときに入力が終わったらCtrl+Dを押す必要があるのが気持ち悪い。
use std::io; use std::io::Read; fn main() { let mut buf = String::new(); io::stdin().read_to_string(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let n: usize = iter.next().unwrap().parse().unwrap(); let mut a: Vec<i32> = Vec::with_capacity(n); for _ in 0..n { let a_i: i32 = iter.next().unwrap().parse().unwrap(); a.push(a_i); } a.sort(); let mut sum: i64 = 0; for i in 0..n { sum += a[i] as i64; } println!("{} {} {}", a[0], a[n - 1], sum);}
for文を使ってるのにわざわざ添字を使っているのは、イテレータ経由でアクセスした要素をキャストするとコンパイラに怒られたからなのだが、いろいろやってたら
for i in a.iter() { sum += *i as i64; }
で動かすことができた。
(sum
の型がi32
のときはfor文の中身をsum += i
にしてもコンパイルが通ったが、これは&T
から*const T
への型強制が暗黙に行われたから?cf. 型間のキャスト)
5_A: Print a Rectangle
use std::io; use std::io::Read; fn main() { loop { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let H: i32 = iter.next().unwrap().parse().unwrap(); let W: i32 = iter.next().unwrap().parse().unwrap(); if H == 0 && W == 0 { break; } for _ in 0..H { for _ in 0..W { print!("#"); } println!(""); } println!(""); } }
5_B: Print a Frame
use std::io; use std::io::Read; fn main() { loop { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let H: i32 = iter.next().unwrap().parse().unwrap(); let W: i32 = iter.next().unwrap().parse().unwrap(); if H == 0 && W == 0 { break; } for _ in 0..W { print!("#"); } println!(""); for _ in 0..H-2 { print!("#"); for _ in 0..W-2 { print!("."); } println!("#"); } for _ in 0..W { print!("#"); } println!("\n"); } }
5_C: Print a Chessboard
use std::io; use std::io::Read; fn main() { loop { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let H: i32 = iter.next().unwrap().parse().unwrap(); let W: i32 = iter.next().unwrap().parse().unwrap(); if H == 0 && W == 0 { break; } for i in 0..H { for j in 0..W { if (i + j) % 2 == 0 { print!("#"); } else { print!("."); } } println!(""); } println!(""); } }
5_D: Structured Programming
同じ終了判定が2ヶ所にあるのが汚いが、これ以外にパッと書く方法が思い浮かばなかった。
use std::io; fn main() { let mut buf = String::new(); io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let n: i32 = iter.next().unwrap().parse().unwrap(); let mut i = 1; loop { let mut x = i; if x % 3 == 0 { print!(" {}", i); i += 1; if i <= n { continue; } else { break; } } loop { if x % 10 == 3 { print!(" {}", i); break; } x /= 10; if x == 0 { break; } } i += 1; if i <= n { continue; } else { break; } } println!(""); }
ABC 119
A
- 2019年より後か、2019年かつ5月以降なら
Heisei
を出力し、それ以外ならTBD
を出力する
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) using ll = long long int; using namespace std; int main() { string S; cin >> S; stringstream ss(S); int y, m, d; char c; ss >> y >> c >> m >> c >> d; if (y > 2019 || (y == 2019 && m >= 5)) cout << "TBD" << endl; else cout << "Heisei" << endl; }
Submission #5195221 - AtCoder Beginner Contest 119
B
JPY
ならそのまま、BTC
なら日本円に換算してから総和を取る
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) using ll = long long int; using namespace std; int main() { int N; cin >> N; double ans = 0.0; REP(i, N) { double x; string u; cin >> x >> u; if (u == "JPY") ans += x; else ans += x * 380000.0; } cout << ans << endl; }
Submission #5196369 - AtCoder Beginner Contest 119
C
- 自力では解法が思いつかなかった
- 合成魔法の使い方を全探索すればよい
- 長さ0の竹を3本用意しておき、合成魔法を3本の竹のどれかに対して使うと考えると書きやすい
- 初回の合成魔法をコスト0とすれば同じ結果になる(
dfs
関数内で返り値を-30
しているのはこの処理) - 3本の初期竹に対して、少なくとも1回は合成魔法を使う必要があることに注意
- 初回の合成魔法をコスト0とすれば同じ結果になる(
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) using ll = long long int; using namespace std; vector<int> l; int N, A, B, C; int dfs(int mp, int a, int b, int c, int n) { int tmp = numeric_limits<int>::max() >> 1; if (n == (int)l.size()) { if ((a == 0) || (b == 0) || (c == 0)) { return tmp; } else { return mp + abs(A - a) + abs(B - b) + abs(C - c) - 30; } } tmp = min(tmp, dfs(mp + 10, a + l[n], b, c, n + 1)); tmp = min(tmp, dfs(mp + 10, a, b + l[n], c, n + 1)); tmp = min(tmp, dfs(mp + 10, a, b, c + l[n], n + 1)); tmp = min(tmp, dfs(mp, a, b, c, n + 1)); return tmp; } int main() { cin >> N >> A >> B >> C; l.resize(N); REP(i, N) cin >> l[i]; cout << dfs(0, 0, 0, 0, 0) << endl; }
Submission #5220254 - AtCoder Beginner Contest 119
D
s
とt
をソートしておくx[i]
よりも左にある神社・寺のうち最も右にあるものの添字(l
,l2
とした)を二分探索で求める- めぐる式二分探索で書いたけど
std::upper_bound
使えば十分だった
- めぐる式二分探索で書いたけど
- 最小の移動距離は次のうちのどれか
- 左側にある神社・寺のうち遠い方までの距離 (
max(x[i] - t[l2], x[i] - s[l])
) - 左側の神社に行ってから右側の寺に行くまでの距離 (
(x[i] - s[l]) + (t[l2 + 1] - s[l])
) - 左側の寺に行ってから右側の神社に行くまでの距離 (
(x[i] - t[l2]) + (s[l + 1] - t[l2])
) - 右側の神社に行ってから左側の寺に行くまでの距離 (
(s[l + 1] - x[i]) + (s[l + 1] - t[l2])
) - 右側の寺に行ってから左側の神社に行くまでの距離 (
(t[l2 + 1] - x[i]) + (t[l2 + 1] - s[l])
) - 右側にある神社・寺のうち遠い方までの距離 (
max(s[l + 1] - x[i], t[l2 + 1] - x[i])
)
- 左側にある神社・寺のうち遠い方までの距離 (
s
とt
の左端と右端に遠い距離の神社・寺をいれておくと端の処理が楽
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) using ll = long long int; using namespace std; int main() { ll A, B, Q; cin >> A >> B >> Q; vector<ll> s(A + 2), t(B + 2), x(Q); s[0] = -1e12; s[A + 1] = 1e12; t[0] = -1e12; t[B + 1] = 1e12; REP(i, A) cin >> s[i + 1]; REP(i, B) cin >> t[i + 1]; REP(i, Q) cin >> x[i]; sort(s.begin(), s.end()); sort(t.begin(), t.end()); REP(i, Q) { int l = 0, r = A + 2; while (r - l > 1) { int mid = (l + r) / 2; if (s[mid] <= x[i]) l = mid; else r = mid; } int l2 = 0, r2 = B + 2; while (r2 - l2 > 1) { int mid = (l2 + r2) / 2; if (t[mid] <= x[i]) l2 = mid; else r2 = mid; } cout << min({max(x[i] - t[l2], x[i] - s[l]), (x[i] - s[l]) + (t[l2 + 1] - s[l]), (x[i] - t[l2]) + (s[l + 1] - t[l2]), (s[l + 1] - x[i]) + (s[l + 1] - t[l2]), (t[l2 + 1] - x[i]) + (t[l2 + 1] - s[l]), max(s[l + 1] - x[i], t[l2 + 1] - x[i])}) << endl; } }
ABC 120
本日の勝敗: int型の敗北
A
B/A
とC
の小さい方
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int A, B, C; cin >> A >> B >> C; cout << min(B / A, C) << endl; }
B
- 制約が緩いので何も考えずに公約数を全部求めて
K
番目に大きいものを出力した
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int A, B, K; cin >> A >> B >> K; vector<int> n; FOR(i, 1, min(A, B) + 1) { if (A % i == 0 && B % i == 0) n.push_back(i); } cout << n[n.size() - K] << endl; }
C
0
と1
の個数のうち小さい方の2倍- 片方が残っていたら必ずどこかで隣り合うので、片方が消滅するまで取り除くことができるから
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { string S; cin >> S; size_t cnt = 0; REP(i, S.size()) { if (S[i] == '0') cnt++; } cout << 2 * min(cnt, S.size() - cnt) << endl; }
D
- UnionFindを知っていますか?というだけの問題……のはずだった
- 終わりから考えて、最初バラバラだった島をつないでいく方針で考える
- 端が全て崩落しているときの不便さは
N*(N-1)/2
- 既に連結している島をつないでも不便さは変わらない
- 連結していない島をつなぐと、それぞれの島群の島数の積だけ不便さが減る
- 方針は一瞬で思いついたのだが、
N<=10^5
なのでN*(N-1)/2
はint型に収まらないのにN
をint型で宣言していたので切り捨てられてしまいWAを連発してしまった。他の人の解説ブログを見てN
の型をlong longに書き直しただけでACだった。
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; struct UnionFind { vector<int> par; vector<int> rank; UnionFind(int n) : par(n), rank(n, 1) { for (int i = 0; i < n; ++i) par[i] = i; } int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) swap(x, y); par[y] = x; rank[x] += rank[y]; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -rank[find(x)]; } }; int main() { ll N, M; cin >> N >> M; vector<int> A(M), B(M); vector<ll> ans(M); REP(i, M) { cin >> A[i] >> B[i]; A[i]--; B[i]--; } UnionFind uf(N); ans[M - 1] = N * (N - 1) / 2; for (int i = M - 1; i > 0; --i) { if (uf.same(A[i], B[i])) { ans[i - 1] = ans[i]; continue; } ans[i - 1] = ans[i] - uf.size(A[i]) * uf.size(B[i]); uf.unite(A[i], B[i]); } REP(i, M) cout << ans[i] << endl; }
ABC 125
A
B*T/A
が答え
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int A, B, T; cin >> A >> B >> T; cout << B * (T / A) << endl; }
Submission #5139315 - AtCoder Beginner Contest 125
B
V[i]-C[i] > 0
となるV[i]-C[i]
の総和
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int N; vector<int> V(N), C(N); cin >> N; REP(i, N) cin >> V[i]; REP(i, N) cin >> C[i]; int ans = 0; REP(i, N) { if (V[i] > C[i]) ans += V[i] - C[i]; } cout << ans << endl; }
Submission #5141279 - AtCoder Beginner Contest 125
C
- 左端から順・右端から順に最大公約数を取った配列を
L[i]
,R[i]
として持っておく - 左端を除いた最大公約数は
R[1]
, 右端を除いた最大公約数はL[N-2]
, 端以外のi
番目を除いた最大公約数はgcd(L[i-1], R[i+1])
になるので、この中から最大のものを選ぶ
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } int main() { int N; cin >> N; vector<int> A(N), L(N), R(N); REP(i, N) cin >> A[i]; L[0] = A[0]; R[N - 1] = A[N - 1]; FOR(i, 1, N) { L[i] = gcd(L[i - 1], A[i]); R[N - 1 - i] = gcd(R[N - i], A[N - 1 - i]); } ll ans = max(R[1], L[N - 2]); FOR(i, 1, N - 1) { ans = max(ans, gcd(L[i - 1], R[i + 1])); } cout << ans << endl; }
D
- 相変わらずDが解けない
dp[i][0]
をi
を選んで反転させない場合、dp[i][1]
をi
を選んで反転させた場合の最大値とする。- このとき
dp[i+1][0] = max(dp[i][0]+A[i], dp[i][1]-A[i])
,dp[i+1][1] = max(dp[i][0]-A[i], dp[i][1]+A[i])
になる。i
を選んで操作しないとき、i-1
を選んで操作していなかったらi
はそのままで、i-1
を操作していたらi
は反転している。i
を選んで操作するとき、i-1
を選んで操作していなかったらi
は反転していて、i-1
を操作していたらi
はそのまま。
- 答えは
dp[N][0]
(N
を選ぶことはできない)
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int N; ll dp[100001][2]; int main() { cin >> N; vector<ll> A(N); REP(i, N) { cin >> A[i]; } dp[0][0] = 0; dp[0][1] = numeric_limits<ll>::min() / 2; FOR(i, 1, N + 1) { dp[i][0] = max(dp[i - 1][0] + A[i - 1], dp[i - 1][1] - A[i - 1]); dp[i][1] = max(dp[i - 1][0] - A[i - 1], dp[i - 1][1] + A[i - 1]); } cout << dp[N][0] << endl; }
ABC 121
A
H * W - h * W - H * w + h * w
が答え
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int H, W, h, w; cin >> H >> W >> h >> w; cout << H * W - h * W - H * w + h * w << endl; }
Submission #5133607 - AtCoder Beginner Contest 121
B
- 問題文に書いてある条件を満たすかどうかを数える
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int N, M, C; int B[21]; int A[21][21]; cin >> N >> M >> C; REP(i, M) cin >> B[i]; REP(i, N) REP(j, M) cin >> A[i][j]; int cnt = 0; REP(i, N) { int sum = C; REP(j, M) sum += A[i][j] * B[j]; if (sum > 0) cnt++; } cout << cnt << endl; }
Submission #5133653 - AtCoder Beginner Contest 121
C
- 価格が安いものから貪欲
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int N, M; vector<pair<ll, ll>> price; ll A, B; cin >> N >> M; REP(i, N) { cin >> A >> B; price.push_back(make_pair(A, B)); } sort(price.begin(), price.end()); ll ans = 0; REP(i, N) { if (M <= price[i].second) { ans += price[i].first * M; break; } else { ans += price[i].first * price[i].second; M -= price[i].second; } } cout << ans << endl; }
D
- 解けなかった
- nが偶数のとき
n^(n-1)
が1であることを利用すると4で割った余りに応じてf(0, n)
は以下のようになる。- 0 →
n
- 1 →
1
- 2 →
n^1
- 3 →
0
- 0 →
f(A, B) = f(0, A-1) ^ f(0, B)
を利用するとO(1)
で解ける- AからBまでの
i
ビットの総和は(0からBまでのi
ビットの総和) - (0からA-1までのi
ビットの総和)であり、その偶奇は両者のXORを取れば求まる。
- AからBまでの
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; ll f(ll n) { int r = n % 4; if (r == 0) return n; else if (r == 1) return 1; else if (r == 2) return n ^ 1; else return 0; } int main() { ll A, B; cin >> A >> B; cout << (f(A - 1) ^ f(B)) << endl; }
ABC 122
バイオインフォっぽかったがそんなことはなかった
A
- 相補塩基を表示する
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { char b; cin >> b; if (b == 'A') cout << 'T' << endl; if (b == 'C') cout << 'G' << endl; if (b == 'G') cout << 'C' << endl; if (b == 'T') cout << 'A' << endl; }
Submission #5129616 - AtCoder Beginner Contest 122
B
- 各位置からACGTだけで書ける部分列の長さを求めて、その最大値
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { string S; cin >> S; int ans = 0; REP(i, S.size()) { int cnt = 0; FOR(j, i, S.size()) { if (S[j] == 'A' || S[j] == 'C' || S[j] == 'G' || S[j] == 'T') cnt++; else break; } ans = max(ans, cnt); } cout << ans << endl; }
Submission #5129638 - AtCoder Beginner Contest 122
C
- 一番左から数えたときに
AC
がいくつあるかを持っておく l
番目とr
番目の差が答え
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int t[100001]; int main() { int N, Q; string S; cin >> N >> Q >> S; int cnt = 0; FOR(i, 1, N) { if (S[i - 1] == 'A' && S[i] == 'C') cnt++; t[i] = cnt; } REP(i, Q) { int l, r; cin >> l >> r; cout << t[r - 1] - t[l - 1] << endl; } }
Submission #5129691 - AtCoder Beginner Contest 122
D
- 自力では解けなかった
- 「ABCのDはDPのD」という格言通りDPで解く
- 最後の3文字を持っておいて、禁止文字列になる場合は遷移しないみたいな感じ(ここまでは分かったが正しく実装できなかった)
- 解説に従ってメモ化再帰で実装
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; vector<map<string, int>> memo(101); int N; const int MOD = 1e9 + 7; bool ok(string s) { if (s[0] == 'A' && s[2] == 'G' && s[3] == 'C') return false; // A?GC if (s[0] == 'A' && s[1] == 'G' && s[3] == 'C') return false; // AG?C if (s[0] == 'A' && s[1] == 'G' && s[2] == 'C') return false; // AGC? if (s[1] == 'A' && s[2] == 'G' && s[3] == 'C') return false; // ?AGC if (s[0] == 'G' && s[1] == 'A' && s[2] == 'C') return false; // GAC? if (s[1] == 'G' && s[2] == 'A' && s[3] == 'C') return false; // ?GAC if (s[0] == 'A' && s[1] == 'C' && s[2] == 'G') return false; // ACG? if (s[1] == 'A' && s[2] == 'C' && s[3] == 'G') return false; // ?ACG return true; } int dfs(int cur, string last3) { if (memo[cur].count(last3) == 1) { return memo[cur][last3]; } if (cur == N) return 1; int ret = 0; char bases[] = {'A', 'C', 'G', 'T'}; for (char c : bases) { if (ok(last3 + c)) { string s = last3.substr(1); s += c; ret = (ret + dfs(cur + 1, s)) % MOD; } } memo[cur][last3] = ret; return ret; } int main() { cin >> N; cout << dfs(0, "TTT") << endl; }
Submission #5130760 - AtCoder Beginner Contest 122
DPによる解法はAtCoder ABC 122 D - We Like AGC (400 点) - けんちょんの競プロ精進記録が詳しい。