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

最初はopcharで読み込むコードを書いていて手元では正しく動作していたが、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

A - Still TBD

  • 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

B - Digital Gifts

  • 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

C - Synthetic Kadomatsu

  • 自力では解法が思いつかなかった
  • 合成魔法の使い方を全探索すればよい
  • 長さ0の竹を3本用意しておき、合成魔法を3本の竹のどれかに対して使うと考えると書きやすい
    • 初回の合成魔法をコスト0とすれば同じ結果になる(dfs関数内で返り値を-30しているのはこの処理)
    • 3本の初期竹に対して、少なくとも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)
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

  • stをソートしておく
  • x[i]よりも左にある神社・寺のうち最も右にあるものの添字(l, l2とした)を二分探索で求める
  • 最小の移動距離は次のうちのどれか
    • 左側にある神社・寺のうち遠い方までの距離 (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]))
  • stの左端と右端に遠い距離の神社・寺をいれておくと端の処理が楽
#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

A - Favorite Sound

  • B/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;
 
int main() {
  int A, B, C;
  cin >> A >> B >> C;
  cout << min(B / A, C) << endl;
}

B

B - K-th Common Divisor

  • 制約が緩いので何も考えずに公約数を全部求めて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

C - Unification

  • 01の個数のうち小さい方の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

D - Decayed Bridges

  • 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

A - Biscuit Generator

  • 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

B - Resale

  • 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

C - GCD on Blackboard

  • 左端から順・右端から順に最大公約数を取った配列を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 - Flipping Signs

  • 相変わらず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;
}

Submission #5163661 - AtCoder Beginner Contest 125

ABC 121

A

A - White Cells

  • 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

B - Can you solve this?

  • 問題文に書いてある条件を満たすかどうかを数える
#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

C - Energy Drink Collector

  • 価格が安いものから貪欲
#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
  • f(A, B) = f(0, A-1) ^ f(0, B)を利用するとO(1)で解ける
    • AからBまでのiビットの総和は(0からBまでのiビットの総和) - (0からA-1までのiビットの総和)であり、その偶奇は両者のXORを取れば求まる。
#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;
}

Submission #5134237 - AtCoder Beginner Contest 121

ABC 122

バイオインフォっぽかったがそんなことはなかった

A

A - Double Helix

  • 相補塩基を表示する
#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

B - ATCoder

  • 各位置から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

C - GeT AC

  • 一番左から数えたときに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

D - We Like AGC

  • 自力では解けなかった
  • 「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 点) - けんちょんの競プロ精進記録が詳しい。