2018-02-23

KUPC2012 J - 刺身

問題ページ
J: 刺身 - 京都大学プログラミングコンテスト2012 | AtCoder

概要

魚が1匹いてこの魚のi番目(1<=i<=n)の部分の重さはw[i]である。この魚をn個に切り分けたい。区間[l,r]がつながっている部分を一つ選びそのうち一箇所を切断するという操作を繰り返す。この操作には区間[l,r]のw[i]の和のコストがかかる。コストを最小化しろ。

解法

dp[i][j] = ([i,j]を切るのに必要なコスト)としたDPを考える。s番目(i<=s<j)で分割するときのうちもっともよいものを選ぶと考えると、DPの漸化式は dp[i][j] = min_{i<=s<j} (dp[i][s]+dp[s][j]) + sum_{k=i}^{j} w[k] となる。これを愚直に実装するとO(n^3)でTLEだが、コスト関数の部分が単調でQIなのでKnuth-Yao speedupを使うことができO(n^2)で解ける。
MLが結構ぎりぎりなので要注意

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

ll a[4010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) cin >> a[i];

  // Knuth-Yao speedup：X(i,j) = min_{i<=s<j} {X(i,s)+X(s,j)} + W(i,j)
  // time: O(n^2)
  // K(i,j) = argmin_{i<=s<j} (X(i,s) + X(s,j))
  vector<ll> W(n, 0);
  vector<vector<ll>> X(n+1, vector<ll>(n+1, 0));
  VVI K(n+1, VI(n+1, 0));
  W[0] = a[0];
  FOR(i, 1, n) W[i] += W[i-1] + a[i];
  REP(i, n+1) REP(j, n+1) {
    X[i][j] = (i==j ? 0 : LLINF);
    K[i][j] = (i==j ? i : 0);
  }
  for(int w=1; w<=n; ++w) {
    for(int i=0, j=i+w; (j=i+w) < n; ++i) {
      // K(i,j)の単調性から範囲が限定できる
      for(int r = K[i][j-1]; r <= K[i+1][j]; ++r) {
        ll c = X[i][r] + X[r+1][j] + W[j] - (i==0?0:W[i-1]);
        if(X[i][j] > c) { X[i][j] = c; K[i][j] = r; }
      }
    }
  }
  cout << X[0][n-1] << endl;

  return 0;
}

2018-02-22

Codeforces Round #189 (Div. 1) C. Kalila and Dimna in the Logging Industry

競技プログラミング Codeforces

問題ページ Problem - C - Codeforces

解法

n本目の木を切ったあとはチャージし放題なのでコスト0で全ての木を切れる。したがってn本目の木を切るのに必要なコストを求めればよい。また、j本目の木を切った後にj本目より前の木を切ったとしてもチャージに使う木はjから変わらないので得することはない。
dp[i] = (i本目の木を切るのにかかるコスト) とすると漸化式は
dp[i] = min(dp[j]+b[j]*a[i] | j<i), dp[0] = 0
となる。このまま愚直に計算するとO(N^2)でTLEだが傾きb[j]、切片dp[j]の直線群に対するconvexHullTrickとして解くことでO(N)で求めることができる。
注意点としてCHTでいらない直線かどうかの判断をする部分(下の実装ではcheck())でよくある書き方をしていると積の結果が64bitに収まらず落ちるパターンがある。別に一回落ちてもいいので誤差死を気にせず多分通るだろうと思いlong doubleで投げたら通ったけどフルフィードバックでない本番だったら多分多倍長整数を使ってると思う。

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

// 直線の傾きに単調性があるときのCHT O(n)
// 最大なら <= になる
class ConvexHullTrick {
public:
  deque<PII> que;
  // ax + b を追加
  void add(int a, int b) {
    PII p(a, b);
    while(que.size() >= 2 && check(que[que.size()-2], que.back(), p)) {
      que.pop_back();
    }
    que.push_back(p);
  }
  // 単調性がある xの位置での最小のy
  int incl_query(int x) {
    assert(que.size());
    while(que.size() >= 2 && f(que[0],x) >= f(que[1],x)) {
      que.pop_front();
    }
    return f(que[0],x);
  }
  // 単調性なし
  int query(int x) {
    int lb = -1, ub = que.size()-1;
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(isright(que[mid], que[mid+1], x)) lb = mid;
      else ub = mid;
    }
    return f(que[ub], x);
  }

  bool isright(const PII &p1, const PII &p2, int x) {
    return (p1.second-p2.second) >= x * (p2.first-p1.first);
  }
  bool check(const PII &a, const PII &b, const PII &c) {
    return (long double)(b.first-a.first)/(b.second-a.second)>=(long double)(c.first-b.first)/(c.second-b.second);
  }
  int f(const PII &p, int x) {
    return p.first * x + p.second;
  }
};
ConvexHullTrick cht;

int a[100010], b[100010], dp[100010];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];

  dp[0] = 0;
  cht.add(b[0], dp[0]);
  FOR(i, 1, n) {
    dp[i] = cht.query(a[i]);
    cht.add(b[i], dp[i]);
  }
  cout << dp[n-1] << endl;

  return 0;
}

2018-02-22

Codeforces Round #185 (Div. 1) B. Cats Transport

競技プログラミング Codeforces

問題ページ Problem - B - Codeforces

${}$

解法

猫が止まる時間や丘までの距離など色々あって扱いにくいのでまずは処理しやすいように言い換える。丘に到達してから猫が待つ時間は猫と飼育員が丘0を出発する時間の差に等しい。したがって各猫が丘0を出発する時間がわかっていればこの時間との差だけを考えればいいので丘の距離などを考える必要がなくなった。t[i] = (猫iが丘0を出発した時間) として数列tはソートしたものとする。

dp[i][j] = (i人の飼育家が猫jに合わせて出発したときの待ち時間の合計の最小) としてDPをすることを考える。 \begin{align} dp[i][j] = {\rm min}_{k<j} \{dp[i-1][k] + (猫k+1から猫jを待たせる時間)\} \end{align} \begin{align} dp[i][j] = {\rm min}_{k<j} \{dp[i-1][k] + \sum_{l=k+1}^{j} (t[j]-t[l])\} \end{align} \begin{align} dp[i][j] = {\rm min}_{k<j} \{dp[i-1][k] + (j-k)t[j] - \sum_{l=k+1}^{j} t[l]\} \end{align} 数列の区間和を累積和で表す。Tを数列tの累積和を取ったものとすると、 \begin{align} dp[i][j] = {\rm min}_{k<j} \{dp[i-1][k] + (j-k)t[j] - (T[j] - T[k])\} \end{align} dp[i][j] = min_{k<j} {-kt[j] + dp[i-1][k] + T[k]} + jt[j] - T[j]
（最後の行だけどうがんばっても数式が反映されなかったのでこうなりました）
ここでminの中に注目すると傾き-k、切片dp[i-1][k]+T[k]の直線でx=t[j]のときのminを求めていることに等しい。したがってconvexHullTrickを用いることができO(PM)で解くことができた。傾きには単調性がありt[j]にも単調性があるので二分探索などを使う必要はない。

公式editorialが理解不能で無限に時間を溶かしてしまった

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

// 直線の傾きに単調性があるときのCHT O(n)
// 最大なら <= になる
class ConvexHullTrick {
public:
  deque<PII> que;
  // ax + b を追加
  void add(int a, int b) {
    PII p(a, b);
    while(que.size() >= 2 && check(que[que.size()-2], que.back(), p)) {
      que.pop_back();
    }
    que.PB(p);
  }
  // 単調性がある xの位置での最小のy
  int incl_query(int x) {
    assert(que.size());
    while(que.size() >= 2 && f(que[0],x) >= f(que[1],x)) {
      que.pop_front();
    }
    return f(que[0], x);
  }
  // 単調性なし
  int query(int x) {
    int lb = -1, ub = que.size()-2;
    while(ub-lb > 1) {
      int mid = (lb+ub)/2;
      if(isright(que[mid], que[mid+1], x)) lb = mid;
      else ub = mid;
    }
    return f(que[ub], x);
  }

  bool isright(const PII &p1, const PII &p2, int x) {
    return (p1.second-p2.second) >= x * (p2.first-p1.first);
  }
  bool check(const PII &a, const PII &b, const PII &c) {
    return (b.first-a.first)*(c.second-b.second)>=(b.second-a.second)*(c.first-b.first);
  }
  int f(const PII &p, int x) { return p.first * x + p.second; }
};
ConvexHullTrick cht;

int d[100010], t[100010], T[100010], dp[105][100010];
signed main(void)
{
  int n, m, p;
  cin >> n >> m >> p;
  REP(i, n-1) cin >> d[i+1];
  REP(i, n-1) d[i+1] += d[i];
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    t[i] = (b-d[a-1]);
  }
  sort(t, t+m);
  T[0] = t[0];
  REP(i, m-1) T[i+1] += T[i] + t[i+1];

  REP(i, m) dp[0][i] = (i+1)*t[i] - T[i];
  FOR(i, 1, p) {
    cht.que.clear();
    dp[i][0] = t[0] - T[0];
    cht.add(0, dp[i-1][0] + T[0]);
    FOR(j, 1, m) {
      dp[i][j] = cht.incl_query(t[j]) + t[j]*j - T[j];
      cht.add(-j, dp[i-1][j] + T[j]);
    }
  }

  cout << dp[p-1][m-1] << endl;

  return 0;
}

2018-02-21

SRM730 div2 med ExpectedMinimumPowerDiv2

競技プログラミング SRM

概要

1~nまでの数からx個をランダムに選ぶ。このとき選んだx個のうち最小のものをSとし2^Sをその集合のスコアとする。スコアの期待値を求めろ。

考えたこと

数mが最小の数Sになるのはどんなときか
x個にmが含まれていてm未満の数が含まれていない
したがってm以上の数であるn-m個の中からx-1個を選んだ時Sはmになる
SがmになるのはC(n-m, x-1)通り
n個からx個を選ぶのは全部でC(n,x)通りなので 2^S * C(n-m,x-1) / C(n,x) を求めればいい
n,x<=50なのでパスカルの三角形でコンビネーションを求められる
オーバーフローにだけ気をつけて計算する

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

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 dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll c[55][55] = {};
void init_comb(int n) {
  REP(i, n) {
    c[i][0] = c[i][i] = 1;
    FOR(j, 1, i) c[i][j] = c[i-1][j] + c[i-1][j-1];
  }
}
ll C(int n, int r) {
  return c[n][r];
}

class ExpectedMinimumPowerDiv2 {
   public:
   double findExp(int n, int x)
  {
    init_comb(n+5);
    double ret = 0;
    double all = C(n, x);
    cout << all << endl;
    FOR(i, 1, n+1) {
      ret += (1LL<<i) / all * C(n-i, x-1);
    }

    return ret;
  }
};

2018-02-20

SRM730 div2 easy IntervalIntersections

競技プログラミング SRM

概要

区間[x1,y1]、[x2,y2]が与えられる。この区間どちらとも共通部分を持つような最小の区間の長さを求めろ。

考えたこと

間の区間を取るかそもそも区間が被っているかのどっちか
x1 < x2 と x2 > x1 で場合分けすればいいね
x1の方が右ならx1-y2かすでに区間を共通していて0
x1の方が左ならx2-y1かすでに区間を共通していて0
場合分けして求める

class IntervalIntersections {
   public:
   int minLength(int x1, int y1, int x2, int y2)
  {
    if(x1 < x2) {
      return max(x2-y1, 0);
    } else {
      return max(0, x1-y2);
    }
  }
};

2018-02-20

SRM730 div1 easy StonesOnATree

競技プログラミング SRM

概要

各頂点iに重みw[i]が設定されているn頂点の木が与えられる。ある頂点に1つ石を置くか、石を一つ取り除く操作を繰り返すゲームをする。ある頂点に石を置くとき、その頂点の子全てに石が置かれている必要がある。ゲーム中に取りうる、石が置かれている頂点の重みの和の最大を最小化しろ。

n <= 1000 各頂点の子は2以下頂点の親は自分より番号が小さい, w[i] <= w[i+1]

考えたこと

ドワコンのディスクの節約で既出では？
制約が n <= 1000
2分木なのとかをうまく使うんだろうなあと思いながら考える
ある頂点に石を置く時に子2つに置かれてないといけない
片方の子に石を置くために根に近づけている最中にもう片方の子に向けて同時に近づけていった方がいい場合があるか？
単調性でドワコンの想定誤答みたいなケースを作れる気がしないのでないと思い込む
子v1,v2を持つ頂点vに石を置くためには下のパターンになりそう max(min(a,b), c)
- v1に石を置くためにw[v1]、v2以下の部分木でもう片方の子に置くために必要な最大の瞬間 (a)
- v2に石を置くためにw[v2]、v2以下の部分木でもう片方の子に置くために必要な最大の瞬間 (b)
- w[v1] + w[v2] + w[v] (c)
子が一つとか葉の場合は特に場合分けせずに適当に渡せばよさそう
再帰的に探索していって出す
やばいケースがあるのか不安だったけど通った

するめで証明なしで投げるの怖い
遅かったけどちゃんと通せてよかった

解法

dp[v] = (頂点vを根とする部分木で取りうる最大の重み) dp[v] = (min(w[v1]+dp[v2], w[v2]+dp[v1]), w[v1] + w[v2] + w[v]) みたいな感じになるように探索する

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#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 IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

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 dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

VI g[1010];
ll dp[1010];
class StonesOnATree {
   public:
   int minStones(vector <int> p, vector <int> w)
  {
    int n = p.size()+1;
    memset(g, 0, sizeof(dp));
    REP(i, n) g[i].clear();
    REP(i, n-1) g[p[i]].PB(i+1);

    // v以下の部分木で取りうる瞬間的な最大
    function<ll(int)> dfs = [&](int v) -> int {
      ll ret = 0;
      if(g[v].size() == 0) return dp[v] = w[v];
      if(g[v].size() == 1) {
        chmax(ret, dfs(g[v][0]));
        dp[v] = w[v] + w[g[v][0]];
        chmax(ret, dp[v]);
        return ret;
      }
      ll vl = dfs(g[v][0]), vr = dfs(g[v][1]);
      dp[v] = max(min(vl + (ll)w[g[v][1]], vr + (ll)w[g[v][0]]), (ll)w[g[v][0]] + w[g[v][1]] + w[v]);
      chmax(ret, vl); chmax(ret, vr); chmax(ret, dp[v]);
      return ret;
    };

    dfs(0);

    ll ret = 0;
    REP(i, n) chmax(ret, dp[i]);
    return ret;
  }
};

2018-02-20

「みんなのプロコン」本選 2017 C - 倍数クエリ

競技プログラミング AtCoder

問題ページ C - 倍数クエリ

平方分割はじめてだったので練習として書いた

考えたこと

mod m で考えてよさそう
平方分割なことは知ってたので考察をすると各バケツが数字が現れる頻度をもっておくとよさそう
まとめてバケツに加算する配列lazを用意しておけば各クエリO(sqrt(n))でいけそう
[l,r]がそのバケツの区間を完全に覆っているならlazに+d、はみ出ているなら１つずつ+dしていく平方分割をかく
区間の包含を逆に書いたり、境界の+1を間違えたり、バケツの数を間違えたりとにかくバグらせまくってつらかったけど通った

実装慣れないと厳しい気持ちになった
頻度を数えるのにセグ木だとbitで数えられる範囲とかじゃないとマージにINF時間かかって終了するので平方分割を使う機会がありそう

学び

平方分割の実装

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

const int sz = 512;
int dat[200][100010], laz[200], a[100010];
signed main(void)
{
  int n, m, q;
  cin >> n >> m >> q;
  REP(i, n) cin >> a[i], a[i] %= m;

  REP(i, 196) {
    REP(j, sz) {
      if(i*sz+j<n) dat[i][a[i*sz+j]]++;
    }
  }

  REP(i, q) {
    int l, r, d;
    cin >> l >> r >> d;
    l--, r--;
    int ret = 0;
    // [j*sz, (j+1)*sz)
    for(int j=l/sz; j<=r/sz; ++j) {
      // 完全に覆ってる
      if(l <= j*sz && (j+1)*sz <= r) {
        (laz[j] += d) %= m;
        ret += dat[j][((-laz[j]%m)+m)%m];
      // 1つずつ足していくパターン
      } else if(j*sz <= l && r < (j+1)*sz) {
        FOR(k, l, r+1) {
          dat[j][a[k]]--;
          (a[k] += d) %= m;
          dat[j][a[k]]++;
          ret += ((a[k]+laz[j])%m==0);
        }
      } else if(j*sz <= l) {
        FOR(k, l, (j+1)*sz) if(IN(0LL, n, k)) {
          dat[j][a[k]]--;
          (a[k] += d) %= m;
          dat[j][a[k]]++;
          ret += ((a[k]+laz[j])%m==0);
        }
      } else if(r < (j+1)*sz) {
        FOR(k, j*sz, r+1) if(IN(0LL, n, k)) {
          dat[j][a[k]]--;
          (a[k] += d) %= m;
          dat[j][a[k]]++;
          ret += ((a[k]+laz[j])%m==0);
        }
      } else {
        assert(false);
      }
    }
    cout << ret << endl;
  }

  return 0;
}

ferinの競プロ帳

競プロについてのメモ

KUPC2012 J - 刺身

概要

解法

Codeforces Round #189 (Div. 1) C. Kalila and Dimna in the Logging Industry

解法

Codeforces Round #185 (Div. 1) B. Cats Transport

解法

SRM730 div2 med ExpectedMinimumPowerDiv2

概要

考えたこと

SRM730 div2 easy IntervalIntersections

概要

考えたこと

SRM730 div1 easy StonesOnATree

概要

考えたこと

解法

「みんなのプロコン」本選 2017 C - 倍数クエリ

考えたこと

学び