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;
}

ごめんなさい↓ f:id:nenuon61:20171008014339p:plain

ARC043 B - 難易度

やり直し

B: 難易度 - AtCoder Regular Contest 043 | AtCoder

問題概要

  • 難易度Diの問題がN個ある
  • 以下の条件を満たす4問を選ぶ選び方は何通りか
    • 2 問目の難易度は 1 問目の難易度の 2 倍以上である
    • 3 問目の難易度は 2 問目の難易度の 2 倍以上である
    • 4 問目の難易度は 3 問目の難易度の 2 倍以上である

部分点

4≦N≦3000

満点

4≦N≦105

解法

選ぶ問題を難易度順にa,b,c,dとする。

  • 部分点解法

b,c(b * 2 ≦ c)を固定して考える。

この時aはb/2以下のDiの個数(x個とする)、dは2c以上のDiの個数(y個とする)通りあるのでb,cを固定した時はxy通りある。

これを全てのb,cの組み合わせについて計算して足せばO(N2)で解くことができる。

  • 満点解法

D_iを昇順にソートしておき、二分探索で、 部分点解法と同様に全てのD_iについてそれの半分以下のD_jの個数と2倍以上のD_jの個数を保存しておく。

満点解法ではbを固定して考える。

aは部分点と同じ方法で何通りあるかわかっている。

c,dの組み合わせが何通りあるか。

c=D_iの時、dはD_i * 2 ≦ D_j を満たすD_jである。

例えば、cがD_i以上の時、c,dの組み合わせは、

D_iの2倍以上のD_jの個数+D(i+1)の2倍以上のDjの個数+D(i+2)の2倍以上のDjの個数+・・・

通りある。これは累積和を用いれば高速に求めることができる。

bごとに最小のcを求め累積和でc,dの組み合わせの数を求めaの個数と掛け算すれば良い。

O(Nlog(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>
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 int MOD = 1000000007;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;cin >> N;
  vector<int> D(N); FOR(i,0,N) cin >> D[i];
  sort(D.begin(), D.end());
  int high[N]; CLR(high);
  int low[N]; CLR(low);
  FOR(i,0,N) {
    high[i] = N - (lower_bound(D.begin(), D.end(), D[i] * 2) - D.begin());
    low[i] = upper_bound(D.begin(), D.end(), D[i] / 2) - D.begin();
  }
  int sum[N+1];
  sum[0] = 0;
  FOR(i,0,N) sum[i+1] = (sum[i] + high[i]) % MOD;
  ll ans = 0;
  FOR(i,0,N) {
    int j = lower_bound(D.begin(), D.end(), D[i] * 2) - D.begin();
    ans += (ll)low[i] * (ll)(sum[N]-sum[j]);
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}

ARC009 C - 高橋君、24歳

やり直し

C - 高橋君、24歳

問題概要

N人に手紙をそれぞれの人の宛名で出そうとしたが、K人は自分の宛名ではない手紙がきてしまった。手紙の渡し方は何通りあるか。1,777,777,777で割った余りを求めよ。

2≦N≦777,777,777,777,777,777
2≦K≦777,777

解法

Nがめちゃくちゃ大きい

自分宛ではない手紙が来る人はN_C_Kパターン。これはフェルマーの小定理を用いて求める。

自分の宛名でない手紙が来るK人について、そのK人の手紙の受け取り方のパターンは、 1~nの数列a_1,a_2,...,a_nがあったとしてa_i = iにならないように数列を並び替えるパターンの数(モンモール数というらしい)に等しい。

これは漸化式->f_k = (k-1)*(f(k-1)+f(k-2))で求めることができる。(f_1 = 0, f_2 = 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>
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 = 1777777777;
// bの逆元求める
ll IE(ll b) {
  ll ret = 1;
  ll M = MOD - 2;
  for (; M; b = (b * b) % MOD, M >>= 1) {
    if(M & 1) ret = (ret * b) % MOD;
  }
  return ret % MOD;
}
// 組み合わせO(r)
ll C(ll n, ll r) {
  r = min(r, n - r);
  ll ret = 1;
  ll rr = r;
  for (ll i = n; i >= n - r + 1; i--) {
    ret = (ret * (i % MOD)) % MOD;
    ret = (ret * IE(rr)) % MOD;
    rr--;
  }
  return ret % MOD;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, K; cin >> N >> K;
  ll ans = C(N, K);
  // aは1~nの数字を並び替えた数列 a_i != iを満たす数列は何通りあるか 漸化式->f_k = (k-1)*(f_(k-1)+f_(k-2))
  ll f[K+1];
  f[1] = 0;
  f[2] = 1;
  FOR(i,3,K+1) f[i] = (ll)(i-1) * (f[i-1]+f[i-2]) % MOD;
  cout << ans * f[K] % MOD << endl;
  return 0;
}

モンモール数知らなかった