2019-02-15

ABC 70 C

問題概要

N台の時計があり、i(1 ≤ i ≤ N)番目の時計の針は、ちょうど$T_i$秒で時計盤を１周する。
全ての時計の針はまっすぐ上に向いている時、全ての時計の針がもう一度まっすぐ上に向くのに要する時間を求めよ。

制約

1 ≤ N ≤ 100
1 ≤ $T_i$ ≤ 10¹⁸
答えは10¹⁸以内

考えたこと

明らかに時計の針のそれぞれの周回する時間の最小公倍数を求めれば良い。
この際に、Tに関する制約が厳しいので注意する(具体的にはオーバーフローを起こさないようにする)
C++ 14では、lcm(a,b) が未実装なので、(C++17以降なら存在する) $|ab| = gcd(a, b) * lcm(a, b)$ の関係式を用いて求める。
gcd(a, b) はユークリッドの互除法で求めれば良い

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
  if(b==0) return a;
  return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
  ll g = gcd(a,b);
  return a / b * b;
}

int main() {
  int n; cin >> n;
  ll ans = 1LL;
  for(int i = 0; i < n; ++i) {
    int t; cin >> t;
    ans = lcm(ans, t);
  }
  
  cout << ans << endl;
  return 0;
}

2019-02-15

ABC 61 C

問題概要

空の配列が１つあ理、この配列に整数を挿入する操作を$N$回行う。
$i(1 ≤ i ≤ N)$回目の操作では、配列に整数$a_i$を$b_i$個挿入する。
$N$回の挿入操作後の配列の中で$K$番目に小さい数を求めよ。

制約

$1 ≤ N ≤ $10⁵
$1 ≤ a_i, b_i ≤ $ 10⁵
$1 ≤ K ≤ b_1 ... + ... b_n$

考えたこと

$a_i$が昇順に入力されるとは限らないので昇順に並び替えてあげる必要がある。
$a_i$ がそれほど大きくないため、どの数字が何個出現したかを表現する配列を用意する( バケツソート )

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int AMAX=100000;
ll cnt[AMAX+1];

int main() {
  ll n, k; cin >> n >> k;
  for(ll i = 0; i < n; ++i) {
    ll a, b; cin >> a >> b;
    cnt[a] += b;
  }
  
  for(ll ans = 1; ans <= AMAX; ++ans) {
    if(k <= cnt[ans]) {
      cout << ans << endl;
      break;
    }
    k -= cnt[ans];
  }

  return 0;
}

2019-02-15

ABC 54 C問題

問題概要

自己ループと二重辺を含まない$N$頂点$M$辺の重み無し無向グラフが与えられる。
$i$番目の辺は頂点$a_i$と頂点$b_i$を結ぶ。
頂点1を始発として、全ての頂点を１度だけ訪れるパスは何通りあるか求めよ。

制約

$2 ≤ N ≤ 8$
$0 ≤ M ≤ N(N-1)/2$
$1 ≤ a_i ≤ b_i ≤ N$
与えられるグラフは自己ループと二重辺を含まない

考えたこと

$N ≤ 8$ なので、$O(N!)$十分計算可能
深さ優先探索で1から始まる全ての道を探索する。
全ての頂点を訪問済みであれば答えに1をたす

#include<bits/stdc++.h>
using namespace std;
const int nmax=8;
bool graph[nmax][nmax];

int dfs(int v, int n, bool visited[nmax]) {
  bool all_visited = true;
  for(int i = 0; i < n; ++i) {
    if(visited[i] == false) all_visited = false;
  }

  if(all_visited) return 1;

  int ret = 0;
  for(int i = 0; i < n; ++i) {
    // 入力によってはgraphが存在しないので、スキップ
    if(graph[v][i] == false) continue;
    if(visited[i]) continue;
    visited[i] = true;
    ret += dfs(i, n, visited);
    visited[i] = false;
  }

  return ret;
}

int main() {
  int n, m; cin >> n >> m;
  for(int i =0; i < m; ++i) {
    int a, b; cin >> a >> b;
    graph[a-1][b-1] = graph[b-1][a-1] = true;
  }
  
  bool visited[n];
  for(int i = 0; i < n; ++i){
    visited[i] = false;
  }
  // 1を出発点にする
  visited[0] = true;

  cout << dfs(0, n, visited) << endl;

  return 0;
}

2019-02-14

全国統一プログラミング王決定戦予選B

問題概要

3つの文字列$A, B, C$が与えられる。これらはそれぞれ、英小文字からなる長さ$N$の文字列である。

目標: これら３つの長さを等しくすること

操作: 文字列$A, B, C$のうち１つを選び、さらに$1$以上$N$以下の整数$i$を指定する。そして、選んだ文字列の先頭から$i$文字目を別のなんらかの英小文字に変更する。

この操作を行う最小回数を求めよ。

制約

$1 ≤ N ≤ 100$
$A, B, C$はそれぞれ長さ$N$の文字列
$A, B, C$の各文字列は英小文字である。

考えたこと

i番目の文字が全て等しければ、変更しない
i番目の文字が１つだけ異なれば、その異なる文字を変更
i番目の文字が全て異なれば、どれかに合わせるために、２つの文字列を変更

これをどう実装しようか考えると、setという数学的集合を表現できるライブラリを用いると良さそうだとわかる。

setを毎回宣言し、それの長さ-1文字を変更すれば良いので、以下のようなコードになる。

#include<bits/stdc++.h>
using namespace std;

int main() {
  int n; cin >> n;
  string a, b, c; cin >> a >> b >> c;
  int ans = 0;

  for(int i = 0; i < n; i++) {
    set<char> st;
    st.insert(a[i]);
    st.insert(b[i]);
    st.insert(c[i]);
    ans += st.size() - 1;
  }
  
  cout << ans << endl;
  return 0;
}

2019-02-14

CODE THANKS FES 2017(Parallel) B

問題概要

英小文字からなる文字列 S が与えられます。 S の後ろに英小文字からなる任意の文字列 T (空文字列も含む)を連結することで、回文にしたいです。条件を満たす文字列 T のうち、 T の最小の長さを求めてください。

制約

1 ≤ |S| ≤ 50
文字列Sは英小文字からなる。

考えたこと

Sの後ろにTをくっつける時、Tの長さは、0≤|T|≤|S|-1となる。
Tの長さを上の制約に基づいて変化させた時に、回文かどうかを判定すれば良い。
その際に、つける文字列は substr() と reverse() を活用すれば良い。(ここは復習ポイント)

#include<bits/stdc++.h>
using namespace std;

int main(){
  string s; cin >> s;
  int n = s.length();
  for(int i =0; i < n; i++) {
    string t = s.substr(0, i);
    reverse(t.begin(), t.end());
    t = s + t;
    string tt = t;
    reverse(tt.begin(), tt.end());
    if(t==tt) {
      cout << i << endl;
      return 0;
    }
  }

  return 0;
}

2019-01-16

ABC 108 C問題

問題概要

整数$N, K$ が与えられる。$N$以下の整数の組$(a, b, c)$であって、$a+b, b+c, c+a$ が全て$K$の倍数であるような物の個数を求めよ。ただし、$a, b, c$の順番を入れ替えただけの組も異なるものとする。また、$a, b, c$のなかに同じ数があっても良い。

制約

1 ≤ $N, K$ ≤ 2 $ \times $ 10⁵
$N, K$は整数である。

考えたこと

$a+b$は$K$の倍数

$b+c$は$K$の倍数

$c+a$は$K$の倍数

この３つの条件から、 $2a, 2b, 2c$ は全てKの倍数であることが導かれる。

$K$ が奇数の時

2と$K$は互いに素なので、$a, b, c$が全て$K$の倍数になれば良い。

$K$ が偶数の時

$K$が奇数の時と同じように、$a, b, c$が全て$K$の倍数になる場合の他に、

$$a, b, c \equiv \frac{K}{2} ( mod K ) $$

となる場合を追加する必要がある。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
  ll n, k; cin >> n >> k;
  ll cnt = 0;
  ll ans = 0;
  for(ll i = 1; i <= n; i++) {
    if(i % k == 0) cnt++;
  }
  ans += (ll)(cnt * cnt * cnt);
  if(k % 2 == 0) {
    cnt = 0;
    for(ll i = 1; i <= n; i++) {
      if(i % k == (k/2)) cnt++;
    }
    ans += (ll)(cnt * cnt * cnt);
  }
  cout << ans << endl;

  return 0;
}

2019-01-15

ABC 109 C問題

問題概要

数直線状に $N$ 個の都市があり、$i$ 番目の都市は、座標$x_i$ にある。座標 $X$ から出発し、全ての都市を訪れなければならない。移動方法は正整数Dを定めると次のとおりである。

座標 $y$ から座標 $y+D$ に移動する
座標 $y$ から座標 $y-D$ に移動する

全ての都市を１度以上訪れることのできるDの最大値を求めよ。

制約

入力は全て整数
1 ≤ $N$ ≤ 10⁵
1 ≤ $X$ ≤ 10⁹
1 ≤ $x_i$ ≤ 10⁹
$x_i$ はすべて異なり、$X$ とも異なる

考えたこと

全ての都市を訪問することのできる時の移動距離の最大値はどんな数かを考察すると、$X$ と $x_i$ との距離を考えた時に、その距離が $D$ の整数倍になる $D$ を求めることと一致する。

つまり、$X$と$x_i$の距離の最大公約数の最小値が$D$と一致する

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
  ll n, X; cin >> n >> X;
  vector<ll> x(n);
  for(ll i = 0; i < n; i++){
    cin >> x[i];
    x[i] = abs(x[i] - X);
  }
  ll ans = x[0];
  for(int i = 0; i < n-1; i++) {
    ans = min(ans, __gcd(x[i], x[i+1]));
  }
  cout << ans << endl;

  return 0;
}