ABC164E - Two Currencies

問題

E - Two Currencies

解法

（計算量に関しては自信ないです）

を頂点とみなす。ただし、は都市、は持っている銀貨の枚数を表す
銀貨の枚数はより多く持っていても意味がないので、頂点数はで済む。

上記のように頂点を増やした場合、辺は鉄道路線と両替の2種類存在する。
鉄道路線を使う場合、頂点から頂点に 分かけて移動する。ただし、銀貨が枚以上必要である。
両替をする場合、からに 分かけて移動する。
鉄道路線の辺数は、両替の辺数はなので、合計の辺数はとなる。

ここまで整理できてしまえば、後はダイクストラ法を適用すればよい。
計算量はとなり、制約上問題ない範囲である。

コード

Submission #12405582 - AtCoder Beginner Contest 164

ABC117D - XXOR

問題

D - XXOR

解法

2進数での各桁におけるは、各の中で桁が0である個数と1である個数の多い方をにかけることで求めることができる。

ここでネックとなるのが以下という条件だが、これは桁DPを考えれば良い。
つまり、上位の桁から、未満が確定している場合とと途中まで一致している場合に分けて処理するということである。
未満が確定している場合については愚直に遷移すれば良いが、と途中まで一致している場合については、の桁目が1のとき、の桁目を0にすれば未満が確定している場合へ遷移できることを考慮する必要がある。

計算量は、となる。

コード

Submission #11232446 - AtCoder Beginner Contest 117

感想

DPの考え方が浅かったためACできず、解説を見てしまった。
ただ、その戒めとして記事を書いたので、次回以降解けるようになっていることを願う。

ABC113D - Number of Amidakuji

問題

AtCoder Beginner Contest 113 - AtCoder

解法

条件を満たす横線の引き方は他の高さの引き方に影響されないため、各高さ毎に、各縦棒にたどり着けるのは何通りかをDPで求めれば良い。

DPの遷移としては、区間ごとに横線があるような引き方が何通りあるのかを事前に求めておけば、縦線毎に隣へ移動する場合を求めることができる。
また、横線があるような引き方が何通りかがわかれば、横線がない引き方が何通りかも全体から引けばわかるので、隣へ移動しない場合も求めることができる。

区間ごとに横線があるような引き方が何通りあるのかは、であることから、bit全探索によりで求めることができる。

計算量はDPと合わせて、である。

コード

Submission #11155114 - AtCoder Beginner Contest 113

感想

解説を見ずに解けると気持ちが良い。

yukicoder contest 241 C (No.1011 Infinite Stairs)

問題

No.1011 Infinite Stairs - yukicoder

解法

コンテスト中はPython/Ruby/PHP/Golang(Go)で上限のある重複組み合わせ - Qiitaを参考にして解いたのだが、解説ではDP+累積和で解いていたので、そちらの解法が上手くイメージができなかったこともあり、解き直すことにした。

DPとしては、回の移動の後段目に辿りつく移動方法が何通りあるかを考える。
ただ、このDPを愚直にやるとかかりTLEとなってしまう。
そこで、回の移動の後段目に辿りつくのは、回の移動の後段目から段目にいる場合であることから、この範囲を累積和で求めることでとなる。

また、余談ではあるが、回の移動の後段目に辿りつく移動方法が何通りあるかを考えるとき、回の移動の後段目以上に辿りつく移動方法が何通りあるかを考慮する必要がないため、をから順に求めることで、配列が1次元で済む。

コード

#447733 (C++14) No.1011 Infinite Stairs - yukicoder

感想

この問題は他の方法で解くことができたので助かったが、DPと累積和の問題に一抹の不安が残る結果となってしまった。

yukicoder contest 240 F (No.1008 Bench Craftsman)

問題

No.1008 Bench Craftsman - yukicoder

解法

基本は解説の通りであるが、自分なりの説明を行う。

まず、ベンチの耐久度を固定すると、人が番目の区画に与える負荷は、である。
この負荷は正の場合、人毎に等差数列になるため、imos法を用いることで、番目の区画に与える負荷の合計を、で求めることができる。

imos法の考え方としては、初項の場合は累積和を1回、公差の場合は累積和を2回行うことで、等差数列を作ることができる。
ただし、今回の場合はで傾きが反転するため、公差の場合においては左右それぞれの場合を考える必要がある。

右側の場合は比較的単純であるが、左側の場合は少し工夫が必要であり、1回目の累積和を行う際に、区間を1つ右にずらしておく必要がある。
そうすることで、実装の手間を減らすことができる。

あとは、固定していたベンチの耐久度を二分探索すれば良い。
ただし、が0の場合は、負荷が正である個数をにするか、処理を分ける必要がある。

全体の計算量は、となる。

コード

#440982 No.1008 Bench Craftsman - yukicoder

感想

わかってみるとそれほど難しくはないが、わかるまでが大変だった。
ただ、苦戦しただけあって、imos法の考え方を少しは理解できたように思う。
（自分なりの説明ができているかどうか微妙なので、問題があれば消します）

ABC157E

問題

E - Simple String Queries

解法

クエリの回数分、文字目から文字目まで調べるのでは間に合わない。

そこで、各アルファベット毎に、以上で初めて登場する位置を探索し、その位置が以下だった場合、種類を増やすことにする。

始めて登場する位置は、各アルファベット毎に位置を昇順に持っておいたものから、二分探索することで求めることができる。

文字を変更する場合、変更前の文字は削除する位置を二分探索で探し、変更後の文字は挿入する位置を二分探索で探せばよい。

計算量は。ただし、に26の定数倍がある。

コード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define all(x) (x).begin(),(x).end()

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

  int N; cin >> N;
  string S; cin >> S;
  vector<vector<int>> v(26);
  for (int i = 0; i < N; i++) {
    v[S[i]-'a'].push_back(i);
  }
  int Q; cin >> Q;
  for (int k = 0; k < Q; k++) {
    int type; cin >> type;
    if (type == 1) {
      int i; cin >> i; i--;
      char c; cin >> c;
      if (S[i] == c) continue;
      int j = S[i] - 'a';
      v[j].erase(lower_bound(all(v[j]), i));
      S[i] = c;
      j = c - 'a';
      v[j].insert(lower_bound(all(v[j]), i), i);
    }
    else {
      int l, r; cin >> l >> r; l--; r--;
      int ans = 0;
      for (int i = 0; i < 26; i++) {
        if (v[i].empty()) continue;
        int index = lower_bound(all(v[i]), l) - v[i].begin();
        if (index < v[i].size() && v[i][index] <= r) ans++;
      }
      cout << ans << "\n";
    }
  }
}

感想

セグメント木を多少触ったばかりだったので、流石にその方法で解くことはできなかった。

また、この解法では位置を持っておくためにvectorを使用しているが、今回の場合はsetというデータ構造の方が明らかに便利なので、次からはそちらを使うようにしたい。

ABC086D

問題

D - Checker

参考

解説PDF

解説放送

累積和を何も考えずに書けるようにする！ - Qiita

ARC 089 D - Checker (500) - kurarrr's memooo

解法

マスが白の時、マスは黒（逆も然り）
マスが黒の時、マスは黒（白の時も然り）

よって、調べる範囲はで済む。
この範囲の中から、斜めに接続しているの正方形2つの総和の最大値を求めれば良い。

総和の求め方としては、二次元累積和を用いる。
二次元累積和については、この記事以上に説明できることはない。

斜めに接続している正方形2つの種類は、愚直に探索すれば個である。
しかし、この探索ではループを考慮しなければならないため、二次元累積和の範囲がになってしまう。
勿論、は制約的に問題ないためこの方法でも良いのだが、この記事で探索の個数が個でも可能であることが判明したため、そちらで実装した。

具体的な方法としては、の範囲に斜めに接続しているの正方形2つがどのような形で配置されているかを考える。
正方形2つがそれぞれループを持っている場合は存在せず、正方形2つがループなく存在する方法は内部に対角に配置する2通りしかない。
つまり、それ以外の場合はループのない正方形とループのある正方形の2つによって構成されているということである。
これは、ループのない正方形とループのある正方形が対になっていることを表しており、ループのある正方形の総和はからループのない正方形の総和を引いたものとなることがわかる。
よって、ループのない正方形を全探索すれば良い。
正方形2つがループなく存在する場合に探索が重複するが、気にする必要はないだろう。

コード

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

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

  int N, K; cin >> N >> K;
  int K2 = K * 2;
  
  vector<vector<int>> a(K2, vector<int>(K2));
  for (int i = 0; i < N; i++) {
    int x, y; cin >> x >> y;
    char c; cin >> c;
    if (c == 'W') x += K;
    a[x%K2][y%K2]++;
  }

  vector<vector<int>> cs(K2+1, vector<int>(K2+1));
  for (int i = 0; i < K2; i++) {
    for (int j = 0; j < K2; j++) {
      cs[i+1][j+1] = cs[i][j+1] + cs[i+1][j]
                   - cs[i][j] + a[i][j];
    }
  }

  auto query = [&](int x1, int y1, int x2, int y2) {
    return cs[x2][y2] - cs[x1][y2] - cs[x2][y1] + cs[x1][y1];
  };

  int ans = 0;
  for (int i = 0; i <= K; i++) {
    for (int j = 0; j <= K; j++) {
      int res = query(0, 0, i, j)
              + query(i, j, i+K, j+K)
              + query(0, j+K, i, K2)
              + query(i+K, 0, K2, j)
              + query(i+K, j+K, K2, K2);
      ans = max(ans, res);
      ans = max(ans, N-res);
    }
  }
  cout << ans << "\n";
}

感想

相当苦戦したので、自分なりに解法を記してみた。

二次元累積和の他に、imos法を使った解法もあるようなので、そちらも別の機会に取り組んでみたいところ（今は力尽きた）