AOJ2510 双子の読書感想文

問題ページ
Twin book report | Aizu Online Judge

考えたこと

• まず本を読む時間を最小化することを考える
• 感想を書く時間を無視して読書にかかる時間の方だけ考える
• とりあえずソートしたい気持ちになる
• いろいろ試してると大体 sum(r) で読書が終わりそう
• sum(r)でできないのはsampleのように max(r) > sum(r) - max(r) となるときだけっぽい
• rを降順ソートしたとする
• max(r) <= sum(r)-max(r) ならば 亜美がr[0],r[1],…,r[n-1]、真美がr[1],r[2],…,r[n-1],r[0]と読めばsum(r)で読書ができる
• max(r) > sum(r)-max(r) ならば 問題文中のサンプルのようにmax(r)の本を読んでいる間に残りの本を全部読むとしてmax(r)*2となる
• 感想を書く時間について考える
• max(r) <= sum(r)-max(r) ならば sum(r) で読書が完了しているので sum(w) で感想を書けばよくこれが最適解
• max(r) > sum(r)-max(r) ならば問題文中のサンプルのように読書中の空いた時間に感想を書いておきたい
• したがってmax(r)*2 + sum(w) - (読書中に感想を書いた分) になる
• 読書中に感想を書ける時間は max(r)*2 - sum(r) が最大
• 最大にできるだけ近づけられるようなwの部分集合の取り方を知りたい
• これは部分和DPをすれば求まる
• O(nsum(w))の状態を取るとだめだが冷静に考えると部分和の最大はO(max(r))なのでO(nmax(r))で求められる

解法

max(r) <= sum(r)-max(r) ならば sum(r) + sum(w)
max(r) > sum(r)-max(r) ならば max(r)*2 + sum(w) - (部分和DPで求めた値)
部分和DPはO(nmax(r))でできる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dp[1010][3010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    VI r(n), w(n);
    int sumr = 0, sumw = 0;
    int ma=0, idx=-1;
    REP(i, n) {
      cin >> r[i] >> w[i];
      if(ma < r[i]) {
        ma = r[i];
        idx = i;
      }
      sumr += r[i];
      sumw += w[i];
    }

    if(ma <= sumr - ma) {
      cout << sumr + sumw << endl;
    } else {
      memset(dp, 0, sizeof(dp));
      dp[0][0] = 1;
      REP(i, n) REP(j, 2*ma-sumr+1) {
        dp[i+1][j] |= dp[i][j];
        if(j+w[i] <= 2*ma-sumr && i != idx) dp[i+1][j+w[i]] |= dp[i][j];
      }

      int tmp = -1;
      REP(i, 2*ma-sumr+1) if(dp[n][i]==1) chmax(tmp, i);

      cout << ma*2 + sumw - tmp << endl;
    }
  }

  return 0;
}

AOJ1318 long distance taxi

問題ページ
Long Distance Taxi | Aizu Online Judge

解法

拡張dijkstraをする。ガソリン量を10倍して1km/Lと考えると楽。
d[都市][残っているガソリン量] としてdijkstraをする。頂点がO(都市数*ガソリン量)で遷移がO(都市数)なので解ける。

入力が面倒だったり10km/Lだったり面倒だけど典型的な拡張dijkstra

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

vector<PII> g[6010];
int d[6010][2010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n, m, cap;
    cin >> n >> m >> cap; cap *= 10;
    if(!n) break;
    string src, dst;
    cin >> src >> dst;
    int V = 0;
    map<string,int> mp;
    REP(i, 6010) g[i].clear();
    REP(i, n) {
      int l;
      string s, t;
      cin >> s >> t >> l;
      if(mp.find(s) == mp.end()) {
        mp[s] = V++;
      }
      if(mp.find(t) == mp.end()) {
        mp[t] = V++;
      }
      g[mp[s]].PB({mp[t], l});
      g[mp[t]].PB({mp[s], l});
      // cout << mp[s] << " " << mp[t] << " " << l << endl;
    }
    VI exist(V, 0);
    REP(i, m) {
      string s;
      cin >> s;
      exist[mp[s]] = 1;
    }
    int start = mp[src], goal = mp[dst];
    // cout << V << endl;

    REP(i, V) REP(j, cap+1) d[i][j] = LLINF;
    d[start][cap] = 0;
    priority_queue<VI, VVI, greater<VI>> que;
    que.push({d[start][cap], start, cap});

    while(que.size()) {
      VI v = que.top(); que.pop();
      // cout << v << endl;
      int dist = v[0], place = v[1], gas = v[2];
      if(dist > d[place][gas]) continue;
      for(PII &p: g[place]) {
        int rest = exist[p.first]?cap:gas-p.second;
        if(gas >= p.second && d[p.first][rest] > d[place][gas] + p.second) {
          d[p.first][rest] = d[place][gas] + p.second;
          que.push({d[p.first][rest], p.first, rest});
        }
      }
    }

    int ans = LLINF;
    REP(i, cap+1) chmin(ans, d[goal][i]);
    if(ans==LLINF) cout << -1 << endl;
    else cout << ans << endl;
  }

  return 0;
}

AOJ0343 プログラミングコンテスト II

問題ページ
Programming Contest II | Aizu Online Judge

解法

(点数、チーム番号)のペアの集合についてある順序が定められている。この集合に対する更新クエリとk番目の要素を探すクエリが飛んでくる。k番目の要素を探すクエリは平衡二分探索木 or 座圧してBIT上での二分探索を用いることでできる。

k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita
pb_ds木について
BITについて
類題

ソースコード

平衡二分探索木

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<typename T>
using btree = tree<T,null_type,greater<T>,rb_tree_tag,tree_order_statistics_node_update>;

ll sc[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, c;
  cin >> n >> c;
  btree<PII> tr;
  FOR(i, 1, n+1) tr.insert({0, -i});
  REP(i, c) {
    int type;
    cin >> type;
    if(type == 0) {
      ll t, p; cin >> t >> p;
      tr.erase({sc[t], -t});
      sc[t] += p;
      tr.insert({sc[t], -t});
    } else {
      ll m; cin >> m; m--;
      cout << -tr.find_by_order(m)->second << " " << tr.find_by_order(m)->first << endl;
    }
  }

  return 0;
}

BIT

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

// Binary Indexed Tree
// 0-indexed
template <typename T>
struct BIT {
  vector<T> bit;
  int neutral = 0, n;
  // 更新クエリ, 区間クエリ
  function<T(T,T)> f = [](const T l, const T r) -> T { return l+r; },
                   g = [](const T l, const T r) -> T { return l+r; };

  // 初期化
  BIT(int n_ = 1e5) { init(n_); }
  void init(int n_ = 1e5) { n = n_+1; bit.assign(n_+1, neutral); }
  // iに対する点更新クエリ
  void update(int i, T w) {
    for(int x = i+1; x < n; x += x&-x) bit[x] = f(bit[x], w);
  }
  // [0,i)に対する区間クエリ
  T query(int i) {
    T ret = neutral;
    for(int x = i+1; x > 0; x -= x & -x) ret = g(ret, bit[x]);
    return ret;
  }
  // 合計がw以上の最小の位置 O(log^2 n)
  int lower_bound(T w) {
    int lb = -1, ub = n;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      if(query(mid) >= w) ub = mid;
      else lb = mid;
    }
    return ub;
  }
};

ll type[100010], a[100010], b[100010], sc[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, c;
  cin >> n >> c;
  vector<pair<ll,ll>> v;
  for(int i=0; i<c; ++i) {
    cin >> type[i];
    if(type[i] == 0) {
      cin >> a[i] >> b[i];
      sc[a[i]] += b[i];
      v.push_back({sc[a[i]], -a[i]});
    } else {
      cin >> a[i];
    }
  }

  // (点数、チーム番号)のpairを番号つける
  for(int i=1; i<=n; ++i) v.push_back({0, -i});
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  reverse(v.begin(), v.end());

  map<pair<ll,ll>,ll> p2n;
  vector<pair<ll,ll>> n2p;
  int idx = 0;
  for(auto i: v) {
    p2n[i] = idx++;
    n2p.push_back(i);
  }

  BIT<ll> bit(n2p.size());
  for(int i=1; i<=n; ++i) bit.update(p2n[{0, -i}], 1);

  memset(sc, 0, sizeof(sc));
  for(int i=0; i<c; ++i) {
    if(type[i] == 0) {
      bit.update(p2n[{sc[a[i]], -a[i]}], -1);
      sc[a[i]] += b[i];
      bit.update(p2n[{sc[a[i]], -a[i]}], 1);
    } else {
      int ret = bit.lower_bound(a[i]);
      cout << -n2p[ret].second << " " << n2p[ret].first << endl;
    }
  }

  return 0;
}

AOJ0570 ジグザグ数

問題ページ
ジグザグ数 | Aizu Online Judge

考えたこと

• 桁DPなのは知ってたので桁DPを考える
• dp[i桁目][B以下が確定か][mod M][最後に選んだ数][ジグザグ数になってないか上昇か下降か] を書く
• mod Mを上の桁から取るのが面倒そうだけどよくよく考えると mo[i] = 10^i mod m を前計算しておけばいいだけ
• 最後の数と比較して上昇か下降かを調べることで最後のフラグがどうなってるか
• 与えられたA、Bが1桁の場合上昇も下降もないので別に場合分けする
• Aより大きいではなくA以上なので ans(B以下) - ans(A以下) とするとだめ
• 10^500とか飛んでくるのでA-1を計算するのも面倒
• Aがジグザグ数かつmの倍数なら答えに+1することにする
• 実装するとサンプルで落ちる
• leading-zeroで057みたいなのを上昇→上昇と判定している
• dp配列にleading-zeroか判定するフラグを一次元増やす
• 0ならまだleading-zero、1なら1桁目、2なら2桁目以降なことを表す
• 投げると通る

実装がたいへん

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

const int MOD = 10000;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dp[505][2][505][10][3][3];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string a, b;
  int m;
  cin >> a >> b >> m;

  int n = b.size();
  if(n != 1) {
    VI mo(n); mo[0] = 1%m;
    FOR(i, 1, n) mo[i] = mo[i-1]*10%m;
    // B以下の数を求める桁DP
    dp[0][0][0][0][0][0] = 1;
    REP(i, n) REP(j, 2) REP(k, m) REP(l, 10) REP(x, 3) REP(y, 3) {
      if(!dp[i][j][k][l][x][y]) continue;
      // cout << i << "," << j << "," << k << "," << l << "," << x << "," << y << " ";
      // cout << dp[i][j][k][l][x][y] << endl;
      int lim = j?9:b[i]-'0';
      REP(d, lim+1) {
        // 上昇か下降か
        int cond = 0;
        if(y==1) {
          if(l < d) cond = 1;
          else if(l > d) cond = 2;
        } else if(x == 1) {
          if(l > d) cond = 2;
        } else if(x == 2) {
          if(l < d) cond = 1;
        }
        // leading-zero
        int cond2 = 0;
        if(y==0) {
          if(d) cond2 = 1;
        } else if(y==1) {
          cond2 = 2;
        } else {
          cond2 = 2;
        }
        (dp[i+1][j||d<lim][(k+mo[n-1-i]*d)%m][d][cond][cond2] += dp[i][j][k][l][x][y]) %= MOD;
      }
    }
  }

  int ans = 0;
  if(n != 1) {
    REP(i, 2) REP(j, 10) FOR(k, 1, 3) REP(l, 3) {
      if(!dp[n][i][0][j][k][l]) continue;
      // cout << n << "," << i << "," << 0 << "," << j << "," << k << "," << l << " ";
      // cout << dp[n][i][0][j][k][l] << endl;
      (ans += dp[n][i][0][j][k][l]) %= MOD;
    }
    REP(i, 9) {
      ans += (i+1)%m==0;
    }
  } else {
    REP(i, b[0]-'0') {
      ans += (i+1)%m==0;
    }
  }

  // cout << ans << endl;

  n = a.size();
  if(n != 1) {
    VI mo(n); mo[0] = 1%m;
    FOR(i, 1, n) mo[i] = mo[i-1]*10%m;
    // A以下の数を求める桁DP
    memset(dp, 0, sizeof(dp));
    dp[0][0][0][0][0][0] = 1;
    REP(i, n) REP(j, 2) REP(k, m) REP(l, 10) REP(x, 3) REP(y, 3) {
      if(!dp[i][j][k][l][x][y]) continue;
      // cout << i << "," << j << "," << k << "," << l << "," << x << "," << y << " ";
      // cout << dp[i][j][k][l][x][y] << endl;
      int lim = j?9:a[i]-'0';
      REP(d, lim+1) {
        int cond = 0;
        if(y==1) {
          if(l < d) cond = 1;
          else if(l > d) cond = 2;
        } else if(x == 1) {
          if(l > d) cond = 2;
        } else if(x == 2) {
          if(l < d) cond = 1;
        }
        int cond2 = 0;
        if(y==0) {
          if(d) cond2 = 1;
        } else if(y==1) {
          cond2 = 2;
        } else {
          cond2 = 2;
        }
        (dp[i+1][j||d<lim][(k+mo[n-1-i]*d)%m][d][cond][cond2] += dp[i][j][k][l][x][y]) %= MOD;
      }
    }
  }

  if(n != 1) {
    REP(i, 2) REP(j, 10) FOR(k, 1, 3) REP(l, 3) {
      if(!dp[n][i][0][j][k][l]) continue;
      // cout << n << "," << i << "," << 0 << "," << j << "," << k << "," << l << " ";
      // cout << dp[n][i][0][j][k][l] << endl;
      (ans -= dp[n][i][0][j][k][l] + MOD) %= MOD;
    }
    REP(i, 9) ans -= (i+1)%m==0;
    ans = (ans%MOD+MOD)%MOD;
  } else {
    REP(i, a[0]-'0') {
      ans -= (i+1)%m==0;
    }
  }

  // aがmの倍数かつジグザグ数ならansに+1する
  bool can = a[0]!=a[1];
  bool flag = a[0]<a[1];
  FOR(i, 2, n) {
    if(flag) {
      if(a[i-1]>a[i]) {
        flag = false;
      } else {
        can = false;
        break;
      }
    } else {
      if(a[i-1]<a[i]) {
        flag = true;
      } else {
        can = false;
        break;
      }
    }
  }
  int now = 0;
  for(int i=n-1; i>=0; --i) now = (now*10 + (a[i]-'0')) % m;
  if(now) can = false;
  if(can) ans++;

  cout << ans%MOD << endl;

  return 0;
}

ARC094 D - Worst Case

問題ページ
D - Worst Case

考えたこと

• よくわからないのでとりあえず実験する
• A<=Bとか仮定しておくと便利そう
• 一回目、二回目に小さい順位を取った人が条件を満たすようにしたい
• A=8,B=9 みたいなのが来たら下のように構成できて14個

1,71 71,1
2,35 35,2
3,23 23,2
4,17 17,4
5,14 14,5
6,11 11,6
7,10 10,7

• x*(x+1) < ABとなるような最大のxを見つけると下のような構成ができる気持ちになる yは単調減少な列

1,y_1
2,y_2
 …
x,y_x

• なので大体2x-2人になりそう
• 問題として A[i] <= x のときや y_j = B[i] のときをどう判定するか
• B[i] = y_x みたいなときは B[i] = y_x - 1 とすれば条件を満たせそうな気がしたがy_(x-1) = y_x - 1みたいなときとかいろいろまずいケースがありそう
• 場合分けを頑張ったりするのかなあと思いいろいろ実験するがよくわからない -----(解説)http://kmjp.hatenablog.jp/entry/2018/04/07/0900を見た-----
• 2A-2人分は必ず達成できる
• 以下のように構成すればよい

1,A+B-1
2,A+B-2
  …
A-1,B+1

B+1,A-1
  …
A+B-2,2
A+B-1,1

• A<=Bなので (A-x)(B+x) = AB + (A-B)x + x^2 < AB を満たす
• 上の構成の間である一回目で[A+1,B]位を取り二回目で[A,B-1]位を取る人の組で条件を満たす人が何人いるか
• 一回目で小さい順位を取った人にできるだけ大きな順位を当てた方がよさそう
• したがって(A+1,A+x-1)(A+2,A+x-2)(A+3,A+x-3)…(A+x,A)みたいな組み合わせをしたい
• x人全員のスコアがAB未満の条件を満たすような最大のxを求めたい
• 単調性がありそうなので二分探索をする
• xの範囲は[0,B-A]
• x人全員について判定をすると二分探索の判定部分の計算量がやばそう
• 冷静になって考えると (A+1)(A+x-1) が (A+x/2)^2 より大きくなることはなさそう
• 真ん中の部分だけ考えればいいので判定がO(1)でできる
• まとめると 2A-2 + (二分探索で求めた人数) となる

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int q;
  cin >> q;
  VI a(q), b(q);
  REP(i, q) {
    cin >> a[i] >> b[i];
    if(a[i] > b[i]) swap(a[i], b[i]);
  }

  REP(i, q) {
    // [lb, ub)
    int lb = 0, ub = b[i]-a[i]+1;
    auto check = [&](int mid) -> bool {
      for(int j=mid/2-2; j<=mid/2+2; ++j) {
        if(j<0 || b[i]-a[i]<j) continue;
        if((a[i]+j)*(a[i]+mid-j) >= a[i]*b[i]) return false;
      }
      return true;
    };
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(check(mid)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    cout << a[i]*2-2 + lb << endl;
  }

  return 0;
}

ARC095 E - Symmetric Grid

問題ページ
E - Symmetric Grid

考えたこと

• 行、列全体をswapするような操作をしてもその行、列に含まれる文字の集合は変わらない

• 行と列独立に考えたくなる

• 行を交換する操作について考える

• ある行を二つ取り出してきたときにその二つの行の組み合わせで点対称になるように出来るか
• s[i],s[j]に対して(s[i][k],s[j][k]) (0<=k<w) のような組の個数を数える
• 文字c,dに対して (c,d)の個数 = (d,c)の個数 ならok
• 例としてs[i]="abcb"、s[j]="cdad"みたいな文字列の組に対して判定をしてみる
• (a,c)(d,b)(c,a)(b,d)みたいな組ができる
• (a,c)の個数=(c,a)の個数=1、(b,d)の個数=(d,b)の個数=1 なのでこれはok
• 注意としてWが奇数だと一つ真ん中に何でもおける場所が存在する
• 対応を取るのが不可能な行があったら"NO"
• これで対応させるべき行がわかったので点対称になるような位置に置く

0 aabbzz
1 bbaazz
2 cdefgg
3 efcdgg

みたいなのがきたら(0,1)、(2,3)が対応するので

0 aabbzz
2 cdefgg
3 efcdgg
1 bbaazz

にする。Hが奇数のときに注意

• 列を交換する操作について考える
• 点対称にするときに対応させられる2列の組について考える
• もう行の入れ替えは適切なものになってるので気にしない
• するとi列目とj列目が対応する条件は i列目 = j列目の反転 になる
• 行の交換操作と同様に対応させる列がわかる
• 対応を取るのが不可能な列があったら"NO"
• Hが奇数の場合1行対応が取れていなくてもいい行があることに注意
• 行に関しても列に関しても対応が取れたら"YES"

H,Wが奇数のときに注意

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int h, w;
  cin >> h >> w;
  vector<string> s(h);
  REP(i, h) {
    cin >> s[i];
  }

  VI can(h, -1);
  REP(i, h) {
    if(can[i] != -1) continue;
    FOR(j, i+1, h) {
      if(can[j] != -1) continue;
      // s[i]とs[j]を組み合わせて点対称を作れるか
      vector<pair<char, char>> v(w);
      map<pair<char, char>, int> mp;
      REP(k, w) {
        v[k] = {s[i][k], s[j][k]};
        mp[{s[i][k], s[j][k]}]++;
      }
      bool flag = true, able = w%2==1;
      for(auto k: mp) {
        cout << k << endl;
        pair<char, char> p = k.first;
        if(mp.find({p.second, p.first}) == mp.end()) {
          flag = false;
          break;
        }
        // ok
        if(mp[{p.second, p.first}] == k.second) continue;
        // ng
        if(abs(mp[{p.second, p.first}] - k.second) == 1) {
          if(able) able = false;
          else {
            flag = false;
            break;
          }
        }
        if(abs(mp[{p.second, p.first}] - k.second) > 1) {
          flag = false;
          break;
        }
      }
      if(flag) {
        // s[i]とs[j]がok
        can[i] = j;
        can[j] = i;
        break;
      }
    }
  }
  // cout << can << endl;

  vector<string> t1, t2;
  string center;
  vector<bool> used(h, false);
  bool able = h%2==1;
  REP(i, h) {
    if(used[i]) continue;
    if(can[i] == -1) {
      if(able) {
        able = false;
        continue;
      } else {
        cout << "NO" << endl;
        return 0;
      }
    }
    t1.PB(s[i]);
    used[i] = true;
    t2.PB(s[can[i]]);
    used[can[i]] = true;
  }
  reverse(ALL(t2));
  if(h%2) {
    REP(i, h) if(!used[i]) center = s[i];
  }

  vector<string> t(t1);
  if(h%2) t.PB(center);
  REP(i, t2.size()) t.PB(t2[i]);

  // REP(i, t.size()) cout << t[i] << endl;

  able = w%2 == 1;
  used.assign(w, false);
  REP(i, w) {
    if(used[i]) continue;
    // i列目と対応する列を見つける
    int idx = -1;
    REP(j, w) {
      if(i==j || used[i] || used[j]) continue;
      string tmp1 = "", tmp2 = "";
      REP(k, h) tmp1 += t[k][i], tmp2 += t[k][j];
      reverse(ALL(tmp1));
      if(tmp1 == tmp2) {
        idx = j;
        used[i] = used[j] = true;
        break;
      }
    }
    if(idx == -1) {
      if(able) {
        able = false;
      } else {
        cout << "NO" << endl;
        return 0;
      }
    }
  }

  cout << "YES" << endl;

  return 0;
}

ARC095 D - Binomial Coefficients

問題ページ D - Binomial Coefficients

考えたこと

• C(x,y)はxが大きければ大きいほどよさそう
• x = max(a) で固定
• O(n)でC(a[n-1],a[i])を全部求めればいい気持ちになるがa<=10^9で無理
• よくよく考えるとC(x,y)のyはx/2に近い方がいい
• パスカルの三角形を考えると真ん中の方がいいのは証明できそう
• C(x,y) = C(x,x-y) なので max(min(a[i],a[n-1]-a[i])) を求める

（二項係数慣れてれば）Cよりこっちのほうが簡単そう

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;
  VI a(n);
  REP(i, n) cin >> a[i];

  sort(ALL(a));
  int ma = -1;
  REP(i, n-1) {
    if(min(a[i], a[n-1]-a[i]) > ma) {
      ma = a[i];
    }
  }
  cout << a[n-1] << " " << ma << endl;

  return 0;
}