ARC 085 F

http://arc085.contest.atcoder.jp/tasks/arc085_d

愚直な DP 解を示す。DP の値には一致した文字数を格納してあり、状態は(位置、最後に使った区間番号)としている。0 番目に番兵として区間 [-1,-1] を入れている。

int dp[100][101];

void to(int &x, int y) {
  x = max(x, y);
}

int main() {
  int n;
  cin >> n;

  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }

  int q;
  cin >> q;

  vector<int> l(q + 1), r(q + 1);
  l[0] = -1;
  r[0] = -1;
  for (int i = 1; i <= q; i++) {
    cin >> l[i] >> r[i];
    l[i]--;
    r[i]--;
  }
  q++;

  fill_n(*dp, 100 * 101, -1e9);
  dp[0][0] = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < q; j++) {
      for (int k = 0; k < q; k++) {
        if (l[k] == i && r[j] <= r[k]) {
          to(dp[i + 1][k], dp[i][j] + b[i]);
        }
      }
      if (i <= r[j]) {
        to(dp[i + 1][j], dp[i][j] + b[i]);
      } else {
        to(dp[i + 1][j], dp[i][j] + !b[i]);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < q; i++) {
    ans = max(ans, dp[n][i]);
  }
  cout << n - ans << endl;
}

区間を右端でソートすることで、DP の性質が良くなる。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
const int N = 1 << 18;
const int inf = 1.01e9;
int dat[N * 2];
int lz[N * 2];
 
void apply(int k, int v) {
  dat[k] += v;
  lz[k] += v;
}
 
void push(int k) {
  apply(k * 2 + 0, lz[k]);
  apply(k * 2 + 1, lz[k]);
  lz[k] = 0;
}
 
void setval(int y, int v, int k = 1, int ll = 0, int rr = N) {
  if (rr - ll == 1) {
    dat[k] = v;
    lz[k] = 0;
    return;
  }
  push(k);
  int mm = ll + rr >> 1;
  if (y < mm) {
    setval(y, v, k * 2 + 0, ll, mm);
  } else {
    setval(y, v, k * 2 + 1, mm, rr);
  }
  dat[k] = max(dat[k * 2], dat[k * 2 + 1]);
}
 
void update(int l, int r, int v, int k = 1, int ll = 0, int rr = N) {
  if (rr <= l || r <= ll) return;
  if (l <= ll && rr <= r) {
    apply(k, v);
    return;
  }
  push(k);
  update(l, r, v, k * 2 + 0, ll, ll + rr >> 1);
  update(l, r, v, k * 2 + 1, ll + rr >> 1, rr);
  dat[k] = max(dat[k * 2], dat[k * 2 + 1]);
}
 
int query(int l, int r, int k = 1, int ll = 0, int rr = N) {
  if (rr <= l || r <= ll) return -inf;
  if (l <= ll && rr <= r) return dat[k];
  push(k);
  return max(query(l, r, k * 2, ll, ll + rr >> 1), query(l, r, k * 2 + 1, ll + rr >> 1, rr));
}
 
int main() {
  int n;
  cin >> n;
 
  vector<int> b(n);
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }
 
  int q;
  cin >> q;
 
  vector<pair<int, int>> rl(q + 1);
  rl[0].first = 0;
  rl[0].second = 0;
  for (int i = 1; i <= q; i++) {
    cin >> rl[i].second >> rl[i].first;
  }
  sort(rl.begin(), rl.end());
  q++;
 
  vector<int> l(q), r(q);
  vector<vector<int>> foo(n);
  for (int i = 0; i < q; i++) {
    l[i] = rl[i].second - 1;
    r[i] = rl[i].first - 1;
    if (l[i] >= 0) 
      foo[l[i]].push_back(i);
  }
 
  update(1, q, -inf);
 
  int u = 0;
 
  for (int i = 0; i < n; i++) {
    vector<int> hoge;
    for (int j = 0; j < foo[i].size(); j++) {
      // r[t] > r[k]
      int t = upper_bound(r.begin(), r.end(), r[foo[i][j]]) - r.begin();
      hoge.push_back(query(0, t));
    }
 
    for (int j = 0; j < foo[i].size(); j++) {
      setval(foo[i][j], hoge[j]);
    }
    while (u < q && r[u] < i) {
      u++;
    }
    update(0, u, !b[i]);
    update(u, q, b[i]);
  }
 
  int ans = query(0, q);
  cout << n - ans << endl;
}

ARC 084 F XorShift

http://arc084.contest.atcoder.jp/tasks/arc084_d

多項式への言い換えが気持ちがいい問題だった。多項式は気持ちがいい。

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;

const long long mod = 998244353;

string gcd(string a, string b) {
  while (true) {
    if (a.size() < b.size()) swap(a, b);
    for (int i = 0; i < b.size(); i++) {
      a[i] ^= b[i];
    }
    int pos = a.find(1);
    if (pos == string::npos) return b;
    a.erase(0, pos);
  }
}

string input() {
  string s;
  cin >> s;
  for (char &c : s) c -= '0';
  return s;
}

long long modpow(long long x, long long y) {
  long long ret = 1;
  while (y > 0) {
    if (y & 1) ret = ret * x % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ret;
}

int main() {
  int n;
  cin >> n;
  string x = input();
  string g = input();
  for (int i = 1; i < n; i++) {
    g = gcd(g, input());
  }

  long long ans = 0;
  string curr(x.size(), 0);
  for (int i = 0; i + g.size() <= x.size(); i++) {
    if (curr[i] == 0 && x[i] == 0) {
      // can't use
    } else if (curr[i] == 1 && x[i] == 0) {
      for (int j = 0; j < g.size(); j++) {
        curr[i + j] ^= g[j];
      }
    } else if (curr[i] == 0 && x[i] == 1) {
      for (int j = 0; j < g.size(); j++) {
        curr[i + j] ^= g[j];
      }
      ans += modpow(2, x.size() - i - g.size());
      ans %= mod;
    } else if (curr[i] == 1 && x[i] == 1) {
      ans += modpow(2, x.size() - i - g.size());
      ans %= mod;
    }
  }
  if (curr <= x) {
    ans++;
    ans %= mod;
  }
  
  cout << ans << endl;
}

yukicoder No.590 Replacement

実装が結構大変。

https://yukicoder.me/problems/no/590

解法

順列なので辺 $ i \to A_i$ のグラフを考えよう。このようなグラフはサイクルの集まりになることに注意したい。

\( (x,y) \to (i,i) \) と考えるのではなく、逆向きの操作を考えて、\( (i,i) \to (x,y) \) となる対 \( (x,y) \) の数を数えることにする。

もし \( (i,i) \to (j,j) \) となるような \(j\) が存在しなければ、\( (i,i) \to (x,y) \) となる対 \((x,y)\) の個数はサイクル長の LCM である。個数が $n$ ならコストは $n(n-1)/2$ であるから、個数を求めることが本質である。存在するときが難しい。

まず問題になるのは \( (i,i) \) と \( (j,j) \) の連結性判定である。よって次は連結性判定について考える。

辺 $A_i \to i$ で構成されたグラフを $A$、辺 $B_i \to i$ で構成されたグラフを $B$ とする。グラフ $G$ において、頂点 $i$ が属する連結成分の代表頂点を $[i]_G$ と書くことにすると、少なくとも連結であるためには $([i]_A,[i]_B) = ([j]_A,[j]_B)$ である必要がある。$(i,i)$ と $(j,j)$ が連結である条件はもう一つある。各サイクルに 0 から順に通し番号を割り振る。$(i)_G$ を頂点 $i$ に振られた番号だとすると $(i)_B-(i)_A \equiv (j)_B-(j)_A \pmod{\gcd(n, m)}$ が必要である。ここで $n$, $ m $ はそれぞれ頂点 $i$, $j$ が属する連結成分の頂点数である。理由は図を見よ。

動かしていく様子

$(A,A)\to(B,B)\to(C,C)\to(A,A)\to\cdots$ となり、ラベル差が不変になっていることが分かる。またラベル差が等しい組は、一方から一方へ必ず到達できることも確認できる（大きなグループでみると互いに素であるため）。

条件をまとめると、

• $([i]_A,[i]_B) = ([j]_A,[j]_B)$
• $(i)_B-(i)_A \equiv (j)_B-(j)_A \pmod{\gcd(n, m)}$

となる。まずこの条件を用いて $(i,i)$ を分類する。

次に $(i,i) \to (j,j)$ に何手で到達できるかを求める。いま $(x_1,x_1), (x_2,x_2), \ldots, (x_s, x_s)$ が連結だったとする。中国剰余定理により $(x_i, x_i)$ に対応する $z_i$ が存在し、$z_i$ でソートすることで、$(x_k,x_k)$ の次の頂点対が分かる。さらに $z$ の差を見ることで距離も同時に分かる。以上より解くことが出来た。

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>

using namespace std;

const long long mod = 1e9 + 7;

long long gcd(long long x, long long y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}

long long lcm(long long x, long long y) {
  return x / gcd(x, y) * y;
}

vector<vector<int>> cycle(vector<int> a) {
  const int n = a.size();
  vector<vector<int>> ret(n);
  vector<bool> vis(n);
  for (int i = 0; i < n; i++) {
    if (vis[i]) continue;
    for (int k = i; !vis[k]; k = a[k]) {
      ret[i].push_back(k);
      vis[k] = true;
    }
  }
  return ret;
}

long long modinv(long long a, long long m) {
  long long b = m, x = 1, y = 0;
  while (b != 0) {
    long long q = a / b;
    a -= b * q;
    x -= y * q;
    std::swap(a, b);
    std::swap(x, y);
  }
  return x < 0 ? x + m : x;
}

long long crt(long long a1, long long m1, long long a2, long long m2) {
  long long v = (a2 - a1) * modinv(m1, m2) % m2;
  if (v < 0) v += m2;
  return a1 + v * m1;
}

map<long long, int> factors(long long n) {
  map<long long, int> ret;
  for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

int power(int a, int b) {
  int ret = 1;
  for (int i = 0; i < b; i++) {
    ret *= a;
  }
  return ret;
}

long long crt_g(long long a1, long long m1, long long a2, long long m2) {
  auto f1 = factors(m1);
  auto f2 = factors(m2);
  int M1 = 1;
  int M2 = 1;
  set<int> st;
  for (auto kv : f1) st.insert(kv.first);
  for (auto kv : f2) st.insert(kv.first);
  for (int k : st) {
    if (f1[k] >= f2[k]) {
      M1 *= power(k, f1[k]);
    } else {
      M2 *= power(k, f2[k]);
    }
  }
  return crt(a1 % M1, M1, a2 % M2, M2);
}

int main() {
  int n;
  cin >> n;

  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    a[i]--;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &b[i]);
    b[i]--;
  }
  vector<vector<int>> cycleA = cycle(a);
  vector<vector<int>> cycleB = cycle(b);

  vector<int> rootA(n), rootB(n);
  vector<int> xa(n), xb(n);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < cycleA[i].size(); j++) {
      xa[cycleA[i][j]] = j;
      rootA[cycleA[i][j]] = i;
    }
    for (int j = 0; j < cycleB[i].size(); j++) {
      xb[cycleB[i][j]] = j;
      rootB[cycleB[i][j]] = i;
    }
  }

  map<pair<int, int>, vector<int>> mp;
  for (int i = 0; i < n; i++) {
    mp[make_pair(rootA[i], rootB[i])].push_back(i);
  }
  long long ans = 0;
  for (auto kv : mp) {
    int A = kv.first.first;
    int B = kv.first.second;
    int lenA = cycleA[A].size();
    int lenB = cycleB[B].size();
    long long G = gcd(lenA, lenB);
    long long L = lcm(lenA, lenB);

    map<int, vector<int>> mp2;
    for (int i : kv.second) {
      int d = (xb[i] - xa[i]) % G;
      if (d < 0) d += G;
      mp2[d].push_back(i);
    }

    for (auto kv2 : mp2) {
      vector<long long> xs;
      for (int i : kv2.second) {
        int x = xa[i];
        int y = xb[i] - kv2.first;
        if (y < 0) y += lenB;
        xs.push_back(crt_g(x, lenA, y, lenB));
      }
      sort(xs.begin(), xs.end());
      xs.push_back(xs[0] + L);
      for (int i = 0; i + 1 < xs.size(); i++) {
        long long d = (xs[i + 1] - xs[i]) % mod;
        ans += d * (d + mod - 1) % mod * ((mod + 1) / 2);
        ans %= mod;
      }
    }
  }

  cout << ans << endl;
}

2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest

A 問題

尺取法をベースに解法を設計した。等差側とそうでない側、それぞれ p, q を尺取ポインタとして、うまく２つを動かしていく。もし \( ap+d < t_q \) なら、\(ap,a(p+1),a(p+2),\ldots\) をまとめて取れば良い。そうでないときは愚直にすすめる。

実装の工夫としては、m 側に番兵を設置し条件を緩やかにした。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

int main() {
  long long n, m, a, d;
  cin >> n >> m >> a >> d;

  vector<long long> t(m + 1);
  for (int i = 0; i < m; i++) {
    scanf("%lld", &t[i]);
  }
  m++;
  t.back() = 4e18;

  long long cnt = d / a + 1;

  long long p = 1;
  long long q = 0;

  long long ans = 0;
  while (p <= n) {
    if (a*p + d < t[q]) {
      long long k = (t[q] - 1 - a*p - d) / (cnt*a) + 1;
      k = min(k, (n - p)/cnt + 1);
      ans += k;
      p += k*cnt;
    } else {
      long long start = min(a*p, t[q]);
      while (q < m && t[q] - start <= d) {
        q++;
      }
      p = (start + d) / a + 1;
      ans++;
    }
  }

  while (q < m) {
    long long start = t[q];
    while (q < m && t[q] - start <= d) {
      q++;
    }
    ans++;
  }

  cout << ans - 1 << endl;
}

E 問題

まず読解に苦しんだわけだけど、なんとかして問題文を理解したと思ったら WA で誤読で辛い問題だった。

F 問題

\(u o \to ou,\, o o \to u,\, k h \to h \) という書き換え規則が完備になるのは容易にわかるので、適当に正規形を求めて set に突っ込めば良い。

よく考えると \( u \to o o, k h \to h\) の方が自然。

#include <iostream>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

string reduce(string s) {
  for (int i = 0; i + 1 < s.size(); i++) {
    if (s.substr(i, 2) == "uo") {
      s.erase(i, 2);
      s.insert(i, "ou");
      return reduce(s);
    }
    if (s.substr(i, 2) == "oo") {
      s.erase(i, 2);
      s.insert(i, "u");
      return reduce(s);
    }
    if (s.substr(i, 2) == "kh") {
      s.erase(i, 2);
      s.insert(i, "h");
      return reduce(s);
    }
  }
  return s;
}

int main() {
  int n;
  cin >> n;

  set<string> st;
  while (n--) {
    string s;
    cin >> s;
    st.insert(reduce(s));
  }

  cout << st.size() << endl;
}

G 問題

コードが雑でごめん。

最小：まず有向辺だけを使って到達できる範囲を求める。実はこれが答えで、無向辺に対して（到達できない）→（到達できる）という向き付けをすれば良い。

最大：こちらも有向辺だけを使って到達できる範囲をうまく使う。まず到達可能範囲を求める。（到達できる）と（到達できない）を結ぶ辺に関しては、明らかに（到達できる）→（到達できない）の向き付けをすれば良い。問題サイズが小さくなって上手くいく。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

void solve_min(int n, int m, vector<int> us, vector<int> vs, vector<int> ds, vector<vector<int>> g, int s) {
  queue<int> q;
  q.push(s);

  vector<bool> vis(n);
  vis[s] = true;

  int cnt = 0;

  while (!q.empty()) {
    int u = q.front(); q.pop();
    cnt++;

    for (int i : g[u]) if (i % 2 == 0 && ds[i >> 1]) {
      int v = vs[i >> 1];

      if (!vis[v]) {
        q.push(v);
        vis[v] = true;
      }
    }
  }

  vector<int> ans(m);

  for (int i = 0; i < n; i++) {
    for (int ii : g[i]) if (!ds[ii >> 1]) {
      int v = ii % 2 == 0 ? vs[ii >> 1] : us[ii >> 1];
      if (!vis[i] && vis[v]) {
        ans[ii >> 1] = ii % 2 == 1;
      }
    }
  }

  cout << cnt << endl;
  for (int i = 0; i < m; i++) {
    if (!ds[i]) {
      putchar(ans[i] ? '-' : '+');
    }
  }
  cout << endl;
}

void solve_max(int n, int m, vector<int> us, vector<int> vs, vector<int> ds, vector<vector<int>> g, int s) {
  priority_queue<pair<int, int>> q;
  q.emplace(1, s);
  q.emplace(0, s);

  vector<bool> vis(n);
  vis[s] = true;

  int cnt = 0;

  vector<int> ans(m);

  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();
    cnt += d;

    if (d) {
      for (int i : g[u]) if (ds[i >> 1]) {
        int v = vs[i >> 1];
        if (!vis[v]) {
          q.emplace(0, v);
          q.emplace(1, v);
          vis[v] = true;
        }
      }
    } else {
      for (int i : g[u]) if (!ds[i >> 1]) {
        int v = i % 2 == 0 ? vs[i >> 1] : us[i >> 1];
        if (!vis[v]) {
          q.emplace(0, v);
          q.emplace(1, v);
          ans[i >> 1] = i % 2 == 1;
          vis[v] = true;
        }
      }
    }
  }

  cout << cnt << endl;
  for (int i = 0; i < m; i++) {
    if (!ds[i]) {
      putchar(ans[i] ? '-' : '+');
    }
  }
  cout << endl;
}

int main() {
  int n, m, s;
  cin >> n >> m >> s;
  s--;

  vector<int> us(m), vs(m), ds(m);
  vector<vector<int>> g(n);

  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &ds[i], &us[i], &vs[i]);
    ds[i] = ds[i] == 1;
    us[i]--;
    vs[i]--;

    if (ds[i]) {
      g[us[i]].push_back(i * 2);
    } else {
      g[us[i]].push_back(i * 2);
      g[vs[i]].push_back(i * 2 + 1);
    }
  }

  solve_max(n, m, us, vs, ds, g, s);
  solve_min(n, m, us, vs, ds, g, s);
}

H 問題

どの文字も偶数回ずつ現れているならば、答えは 1 である。そうでないとき、奇数回現れている文字があるなら、それらは全て奇数長回文の中心となるはずである。まず回文の個数を \(k\) 個と仮定して構成できるかを判定する。判定は単純な計算式で表せるため、容易なフェーズである。もし構成できないのであれば \(k \to k+2\) として再度チェックする。\(k+1\) が不可能なのはまあ分かると思う。これを繰り返すだけで良い。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int cnt[128];

int main() {
  int n;
  cin >> n;

  string s;
  cin >> s;

  for (char c : s) {
    cnt[c]++;
  }

  vector<char> center;
  int sum = 0;

  for (int i = 0; i < 128; i++) {
    if (cnt[i] % 2 == 1) {
      center.push_back(i);
      cnt[i]--;
    }
    sum += cnt[i] / 2;
  }

  if (center.empty()) {
    cout << 1 << endl;
    string ans(sum * 2, '\0');
    for (int i = 0; i < sum; i++) {
      for (int j = 0; j < 128; j++) {
        if (cnt[j] > 0) {
          ans[i] = ans[ans.size() - 1 - i] = j;
          cnt[j] -= 2;
          break;
        }
      }
    }
    cout << ans << endl;
    return 0;
  }

  while (true) {
    if (sum % center.size() == 0) {
      int g = sum / center.size();
      cout << center.size() << endl;
      for (char c : center) {
        string ans(g * 2 + 1, '*');
        ans[g] = c;
        for (int i = 0; i < g; i++) {
          for (int j = 0; j < 128; j++) {
            if (cnt[j] > 0) {
              ans[g - i - 1] = j;
              ans[g + i + 1] = j;
              cnt[j] -= 2;
              break;
            }
          }
        }
        cout << ans << ' ';
      }
      return 0;
    }
    for (int i = 0; i < 128; i++) {
      if (cnt[i] > 0) {
        cnt[i] -= 2;
        sum--;
        center.push_back(i);
        center.push_back(i);
        break;
      }
    }
  }
}

I 問題

二分探索する。[0,i) 番目まではいい感じの分割が得られている状態を dp[i] というブール値で表した時、遷移は dp[i]-> dp[i+K],dp[i+K+1],...,dp[j] な感じになって連続区間になる。ブール値でやる必要もないのでいもす法でやれば良い。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int main() {
  int n, K;
  cin >> n >> K;

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  sort(a.begin(), a.end());

  int ok = 1e9, ng = -1;
  while (ok - ng > 1) {
    int mid = (ok + ng) / 2;

    vector<int> imos(n + 2);
    imos[0] = 1;
    imos[1] = -1;

    int j = 0;
    for (int i = 0; i < n; i++) {
      imos[i + 1] += imos[i];
      while (j < n && a[j] - a[i] <= mid) {
        j++;
      }
      if (imos[i] == 0) continue;
      if (j >= i + K) {
        imos[i + K]++;
        imos[j + 1]--;
      }
    }

    if (imos[n] > 0) {
      ok = mid;
    } else {
      ng = mid;
    }
  }

  cout << ok << endl;
}

K 問題

単純すぎて誤読してないか不安になる問題。i 番目が取りうる値の範囲を [L[i], R[i]] としたとき、L[i],R[i] から L[i+1],R[i+1] が計算できる。n 番目の値は R[n] にすれば良いのは明らかで、n,n-1,n-2,... の順に戻して行けば値が分かる。

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

pair<int, int> intersect(int l, int r, int ll, int rr) {
  int a = max(l, ll);
  int b = min(r, rr);
  return make_pair(a, b);
}

int main() {
  int n;
  cin >> n;

  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a[i], &b[i]);
  }

  vector<int> L(n), R(n);
  L[0] = a[0];
  R[0] = a[0] + b[0];

  for (int i = 1; i < n; i++) {
    // L[i-1]-1 .. R[i-1]+1
    auto s = intersect(L[i - 1] - 1, R[i - 1] + 1, a[i], a[i] + b[i]);
    if (s.first > s.second) {
      cout << -1 << endl;
      return 0;
    }
    L[i] = s.first;
    R[i] = s.second;
  }

  vector<int> ans(n);
  ans[n - 1] = R[n - 1];
  int curr = R[n - 1];
  for (int i = n - 2; i >= 0; i--) {
    if (R[i] >= curr + 1) {
      curr++;
    } else if (R[i] >= curr) {
      // don't change
    } else {
      curr--;
    }
    ans[i] = curr;
  }

  long long des = 0;
  for (int i = 0; i < n; i++) {
    des += ans[i] - a[i];
  }
  cout << des << endl;

  for (int i = 0; i < n; i++) {
    printf("%d ", ans[i]);
  }
  puts("");
}

M 問題

これは良いよね。

まとめ

解いてない問題はそもそも読んですらない。E 問題に 1 時間費やしたのが、時間的にも体力的にも最悪だった。シンプルだけど面白い問題が多くて良かった。

Sandy the foodie

https://www.codechef.com/problems/KOK100

euler-tour tree。O(n log n) ではあるけど、定数倍が重くて通らなかった。

euler-tour を考えるとき辺で見るか、頂点で見るかどちらかだと思うけど、辺で考えると対称性が良い気がするので辺で実装している。今回の問題のように頂点に値を持たせる場合は、仮想的な何かを差し込んでおいてそれを使うと良い。