ARC046 B - 石取り大作戦

解法

N <= Aの時

絶対に先行が勝つ

N > Aの時
  • A > Bの時

N > A > Bであるため先攻が1個だけとる戦法をとると絶対にN > Bにできる。N <= Aになったら全部取れば良い。よって先攻が勝つ。

  • A < Bの時

N > B > Aである。A > Bの時と同様に考えると、後攻が絶対勝つ。

  • A == Bの時

A + 1個にされると絶対勝てない

2(A + 1)個にされると絶対勝てない

.

.

.

x(A+1)にされると絶対に勝てない。

つまりN % (A + 1) = 0なら後攻が勝ち、そうでないなら先攻が勝ちとなる。

#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>
#include <deque>
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;
void f() {cout << "Takahashi" << endl;}
void s() {cout << "Aoki" << endl;}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, A, B; cin >> N >> A >> B;
  if(N <= A) f();
  else {
    if(A > B) f();
    else if(A < B) s();
    else {
      if(N % (A + 1) == 0) s();
      else f();
    }
  }
  return 0;
}

ゲーム系は苦手だな〜。

ARC051 C - 掛け算

解法

愚直にシミュレーションするとB≦109なのでTLEしてしまう。

操作を十分な回数行うと、一番小さい数にAをかけると一番大きな数になる状態ができる。

この状態になれば周期性を利用してとくことができる。

この状態になった時の数列が{a'}で残りの操作回数がB'回の時、

i = B' % N とすると、

a'_0 ~ a'_{i-1} は B' / N + 1 回、

a'_i ~ a'_{N-1} は B' / N 回

Aをかける。

愚直にAをかけるとTLEなのでダブリングを用いる。

出力は a'_i, ..., a'_{N-1}, a'_0, ... , a'_{i-1}の順ですれば良い。

コード

#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>
#include <deque>
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;
const ll MOD = 1000000007;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, A, B; cin >> N >> A >> B;
  ll a[N];
  priority_queue<ll, vector<ll>, greater<ll> > Q;
  FOR(i,0,N) {
    cin >> a[i];
    Q.push(a[i]);
  }
  sort(a, a + N);
  if(A == 1) {
    FOR(i,0,N) cout << a[i] % MOD << endl;
    return 0;
  }
  while(Q.top() < a[N-1]) {
    B--;
    ll q = Q.top(); Q.pop();
    Q.push(q * A);
    if(B == 0) break;
  }
  FOR(i,0,N) {
    a[i] = Q.top();
    Q.pop();
  }
  if(B == 0) {
    FOR(i,0,N) cout << a[i] % MOD << endl;
    return 0;
  }
  // 残りB回N回周期
  FOR(i,0,N) {
    int j = (i + B % N) % N;
    ll x = a[j] % MOD;
    ll t = j < B % N ? B / N + 1 : B / N;
    ll AA = A % MOD;
    // ダブリング
    while(t) {
      if(t & 1) x = (x * AA) % MOD;
      AA = (AA * AA) % MOD;
      t >>= 1;
    }
    cout << x << endl;
  }
  return 0;
}

SRM609 div2 Med PackingBallsDiv2

解法

variety setを何個売るか決まれば、同じ色のパッケージを何個売らないといけないか決まる。

variety setを何個売るかで全探索。

コード

class PackingBallsDiv2 {
public:
  int minPacks(int R, int G, int B) {
    int ans = 1e9;
    // variety set
    for(int i = 0; i < 101; i++) {
      int cnt = i;
      int RR = max(0, R-i);
      int GG = max(0, G-i);
      int BB = max(0, B-i);
      cnt += (RR + 2) / 3 + (GG + 2) / 3 + (BB + 2) / 3;
      ans = min(ans, cnt);
    }
    return ans;
  }
};

ある値を固定して全探索系の問題たまに忘れてしまう。。。

ARC071 E - TrBBnsformBBtion

解法

どんな文字列でも"A"or"B"or""の3種類のどれかにすることができる。そのため無限にある文字列を"A"にできる文字列、"B"にできる文字列、""にできる文字列の3つのグループに分けることができる。"A"にできる文字列は逆に"A"から作ることができる。"B"、""にできるグループについても同様である。

よってクエリで与えられる文字列SとTが"A"、"B"、""のどれにできるかわかれば良い。同じ時YES、そうでない時NOを出力すれば良い。

"AB"->"","AAA"->"","BBB"->"","AA"->"B","BB"->"A"なので"A"の個数と"B"の個数を3で割った数を求め、どのグループに属するか求める。

(解説によるとA=1, B=2として和を3で割った値でグループ判定すれば楽だった)

コード

#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>
#include <deque>
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 S, T;
  cin >> S >> T;
  int slen = S.length();
  int tlen = T.length();
  int SA[slen+1], SB[slen+1];
  int TA[tlen+1], TB[tlen+1];
  SA[0] = SB[0] = 0;
  TA[0] = TB[0] = 0;
  FOR(i,0,slen) SA[i+1] = SA[i] + (S[i] == 'A');
  FOR(i,0,slen) SB[i+1] = SB[i] + (S[i] == 'B');
  FOR(i,0,tlen) TA[i+1] = TA[i] + (T[i] == 'A');
  FOR(i,0,tlen) TB[i+1] = TB[i] + (T[i] == 'B');
  int q; cin >> q;
  FOR(i,0,q) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int sa = (SA[b] - SA[a-1]) % 3; // Aの数
    int sb = (SB[b] - SB[a-1]) % 3; // Bの数
    int ta = (TA[d] - TA[c-1]) % 3; // Aの数
    int tb = (TB[d] - TB[c-1]) % 3; // Bの数
    int check_a, check_b;
    if(sa == sb) check_a = 0;
    if(sa == 2 && sb == 1) check_a = 1;
    if(sa == 0 && sb == 2) check_a = 1;
    if(sa == 1 && sb == 0) check_a = 1;
    if(sa == 1 && sb == 2) check_a = 2;
    if(sa == 2 && sb == 0) check_a = 2;
    if(sa == 0 && sb == 1) check_a = 2;
    if(ta == tb) check_b = 0;
    if(ta == 2 && tb == 1) check_b = 1;
    if(ta == 0 && tb == 2) check_b = 1;
    if(ta == 1 && tb == 0) check_b = 1;
    if(ta == 1 && tb == 2) check_b = 2;
    if(ta == 2 && tb == 0) check_b = 2;
    if(ta == 0 && tb == 1) check_b = 2;
    cout << (check_a == check_b ? "YES" : "NO") << endl;
  }
}

CODE THANKS FESTIVAL 2017(Parallel)

A - Time Penalty

最大値出力。

#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>
#include <deque>
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);
  int ans = 0;
  FOR(i,0,8) {
    int in; cin >> in;
    ans = max(ans, in);
  }
  cout << ans << endl;
  return 0;
}

B - Concatenated Palindrome

sの最後の文字を含む最長の回文を求める。回文でない部分の文字数がTの文字数となる。

#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>
#include <deque>
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 s; cin >> s;
  int len = s.length();
  int ans = len - 1;
  // 中心1つ
  FOR(i,0,len) {
    int r = i, l = i;
    while(r < len && l >= 0 && s[l] == s[r]) {
      l--;
      r++;
    }
    if(r == len) {
      ans = min(ans, l + 1);
    }
  }
 
  // 中心二つ
  FOR(i,0,len-1) {
    int r = i + 1, l = i;
    while(r < len && l >= 0 && s[l] == s[r]) {
      l--;
      r++;
    }
    if(r == len) {
      ans = min(ans, l + 1);
    }
  }
  cout << ans << endl;
  return 0;
}

C - Factory

次にi番目の機械を使うときにかかる時間とiをpriority_queueに保存。

#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>
#include <deque>
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;
typedef pair<ll, int> P;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, K; cin >> N >> K;
  ll a[N], b[N];
  FOR(i,0,N) cin >> a[i] >> b[i];
  priority_queue<P, vector<P>, greater<P> > Q;
  FOR(i,0,N) Q.push(P(a[i], i));
  ll ans = 0;
  FOR(i,0,K) {
    P p = Q.top(); Q.pop();
    ans += p.first;
    Q.push(P(p.first + b[p.second], p.second));
  }
  cout << ans << endl;
  return 0;
}

D - Bus Tour

証明はできないけどM - gcd(N, 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>
#include <deque>
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 gcd(int a, int b) {
  while (a && b) {
    if (a >= b) a %= b;
    else b %= a;
  }
  return a + b;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M; cin >> N >> M;
  int g = gcd(N, M);
  cout << M - g << endl;
  return 0;
}

E - Coin Authentication

インタラクティブ問題

袋が最大50個で10回まで質問できる。つまり5個ずつ質問できる。この5個の袋について1,10,100,1000,10000枚秤に乗せることで、8,9,10,11,12を区別できる。

秤に乗せたコインの合計の重さがsumの時、

重さxのコインを1枚乗せている場合 (sum - x ) % 10 == 0となる。

次に10枚乗せたコインの重さを調べる場合sum = (sum - x) / 10として、1枚乗せている場合と同じ方法で重さを求める。

#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>
#include <deque>
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 sum;
bool f() {
  bool ret = 0;
  if((sum - 8) % 10 == 0) {
    sum -= 8;
    ret = 0;
  }
  else if((sum - 9) % 10 == 0) {
    sum -= 9;
    ret = 1;
  }
  else if((sum - 10) % 10 == 0) {
    sum -= 10;
    ret = 0;
  }
  else if((sum - 11) % 10 == 0) {
    sum -= 11;
    ret = 1;
  }
  else if((sum - 12) % 10 == 0) {
    sum -= 12;
    ret = 0;
  }
  return ret;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  int s = 0;
  vector<int> ans;
  while(s < N) {
    
    cout << "? ";
    FOR(i,0,s) cout << "0 ";
    cout << "1 ";
    s++;
    if(s < N) cout << "10 ";
    s++;
    if(s < N) cout << "100 ";
    s++;
    if(s < N) cout << "1000 ";
    s++;
    if(s < N) cout << "10000 ";
    s++;
    FOR(i,s,N) cout << "0 ";
    cout << endl;
 
    cin >> sum;
    while(sum) {
      if(f()) ans.push_back(1);
      else ans.push_back(0);
      sum /= 10;
    }
  }
  cout << "! ";
  FOR(i,0,ans.size()) printf("%d%c", ans[i], (i == ans.size() - 1 ? '\n' : ' '));
  return 0;
}

ARC070 D - No Need

解説

wa = a_iを含む良い集合の和の最小値とすると、

wa - a_i ≧ K <=> a_i は不必要

wa - a_i < K <=> a_i は必要

となる。

全てのカードiについて、カードiを含まないカードで作れる和をdpで調べる。

dp[j][k] = カードjまで調べたときに和kを作れるかどうかとする。

wa は (dp[j][k] = trueかつk≧K-a_i) となる最小のk + a_iである。

カードの数は最大109だが、K以上の数をKとしても必要かどうかの判定には影響しないので計算量はO(NK)となる。

よって全体でO(N2 K)で部分点が取れる。

満点解法は、カードiが不必要ならa_i ≧ a_jであるカードjも不必要であることを用いる。

aをソートしておいて、不必要なカードと必要なカードの境界を二分探索で求めれば良い。

計算量はO(NKlogN)となる。

#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>
#include <deque>
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, K;
vector<int> a;
bool dp[5050][5050];
// 不必要ならtrue
bool calc(int i) {
  vector<int> b;
  FOR(j,0,N) if(i != j) b.push_back(a[j]);
  CLR(dp);
  dp[0][0] = true;
  FOR(j,0,N-1) {
    FOR(k,0,K+1) {
      if(!dp[j][k]) continue;
      // b[j]を使う
      if(k+b[j] <= K) dp[j+1][k+b[j]] = true;
      // b[j]を使わない
      dp[j+1][k] = true;
    }
  }
  int wa = 0;
  FOR(j,0,K+1) {
    if(dp[N-1][j]) {
      wa = a[i] + j;
      if(wa >= K) break;
    }
  }
  return (wa < K) || (wa - a[i] >= K);
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> K;
  a.resize(N);
  FOR(i,0,N) {
    int in; cin >> in;
    in = min(in, K);
    a[i] = in;
  }
  sort(a.begin(), a.end());
  int l = -1, r = N + 1;
  while(r - l > 1) {
    int m = (r + l) / 2;
    if(calc(m)) l = m;
    else r = m;
  }
  cout << min(r, N) << endl;
  return 0;
}

コメント

部分点はできたが、二分探索に気づけなかった。

KUPC2017 C - Best Password

解説

できるだけ一文字目の方に大きい文字(z,y,x,...,a)を作っていく。繰り上げしていくイメージ。

Ai C[S_i] + Ai+1 C[S_(i+1)] => Ai (C[S_i] + A) + Ai+1 * (C[S_(i+1)] - 1)。

N文字目から繰り上げできるだけしていく。

コード

#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>
#include <deque>
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);
  int A; cin >> A;
  string s; cin >> s;
  int N = s.length();
  int C[N];
  FOR(i,0,N) C[i] = s[i] - 'a' + 1;
  FOR(i,0,N) {
    for(int j = N - 1; j > 0; j--) {
      // j -> j - 1にできるだけ繰り上げする
      while(C[j-1] + A <= 26 && C[j] > 0) {
        C[j-1] += A;
        C[j]--;
      }
    }
  }
  FOR(i,0,N) {
    if(C[i] == 0) break;
    cout << char(C[i]-1+'a');
  }
  cout << endl;
  return 0;
}