競プロ日記

差分: -14

3完
前回のABC参加から2週間コード全くコード書かなかった結果がこれ。
LoLが忙しすぎた・・・。
という言い訳建前はあったとしても、このレベルでレート下がるのは雑魚でしかなくてショックを隠せない。

現状でD問題まではACして、EFはまだ残っている。
一応過去コンテストはAから始めてFまで通すようにしているのだが、だんだん残っている問題が増えてきた。

A問題

かんたんじゃなかった・・・。
久しぶりの緊張のせいか問題の理解が浅すぎた。
ここで1WA。

B問題

こっちはかんたん。

C問題

復元とか言われるといかつい感じがするけど案外かんたん。
ここまで大体1問5分で17分くらい。
今回はここまで！(絶望)

D問題

解く方針は1～2分で思いついたんだ・・・。
その方針というのは、「公約数の中で素数のものを選べば良い」というもの。
実際その方針は合っているので、正しく実装できればよかったんだけど全く出来なかった。
なんでこんなに間違うんだという程合わない。
コンテストが終わって数日してからだいぶWAを重ねてACしたのだが、原因は公約数を正しく求められていないというものだった。
2週間ぶりというのがたたってか、色々細かい(致命的な)ミスはやらかしていたが、一番の原因は、平方根までループを回して順に割っていく際、最後に残った平方根以上の数も約数になる、というのを忘れていた点である。
この平方根以上の約数の問題と大量に跋扈する細かい(致命的な)ミスが織りなすバグのハーモニーが僕を苦しめた・・・。
少し考えれば、解説の「最大公約数の約数の中で素数のものを選ぶ」と同じであるというのは分かるのだが、別にそちらに変換せずとも解けるため、そのまま前者で実装を試みた。
もし最初に思いついたのが後者だったらわりとACできてたのではないかと思っている。

E問題

Dに詰まって少し見たが、さすがにDの方が簡単だろうと手をつけなかった。
後は2週間ぶりでEは無謀だろういうのもあった。
制約がかなり小さいのでbitDPとか部分的に全探索したりするのかなとか考えた。

F問題

誘導部分グラフってなんやねん。
調べて理解したが、この問題を考えるべきではないと直感が告げた。


2週間ぶりでもDは間違いなく解けた問題だ。
反省しかない。
もうちょっと落ち着いてコードとやりたいことを広く見られるようになりたい。

ABC142からまた1週間空いて、今週はあるのかどうかまだ分からないが、あればなんとか頑張って参加したい。
というのも今週土曜日はWCSグループステージ開幕！
観戦しながらとか舐めたことしてまた3完にならないように気をつけたいが、見たいものは見たい。

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

template 
class ModInt {
  long long n_;

  public:
  constexpr ModInt(const long long num = 0) : n_(num % mod_num) {}
  constexpr const long long&value() const { return n_; }
  constexpr bool   operator==(const ModInt &r) const { return this->n_ == r.n_; }
  constexpr bool   operator==(const long long &r) const { return this->n_ == r; }
  constexpr bool   operator!=(const ModInt &r) const { return this->n_ != r.n_; }
  constexpr bool   operator!=(const long long &r) const { return this->n_ != r; }
  constexpr bool   operator<(const ModInt &r) const { return this->n_ < r.n_; }
  constexpr bool   operator<(const long long &r) const { return this->n_ < r; }
  constexpr bool   operator>(const ModInt &r) const { return this->n_ > r.n_; }
  constexpr bool   operator>(const long long &r) const { return this->n_ > r; }
  constexpr bool   operator<=(const ModInt &r) const { return this->n_ <= r.n_; }
  constexpr bool   operator<=(const long long &r) const { return this->n_ <= r; }
  constexpr bool   operator>=(const ModInt &r) const { return this->n_ >= r.n_; }
  constexpr bool   operator>=(const long long &r) const { return this->n_ >= r; }
  constexpr ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }
  constexpr ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }
  constexpr ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }
  constexpr ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }
  constexpr ModInt operator+(const long long &r) const { return ModInt(*this) += ModInt(r); }
  constexpr ModInt operator-(const long long &r) const { return ModInt(*this) -= ModInt(r); }
  constexpr ModInt operator*(const long long &r) const { return ModInt(*this) *= ModInt(r); }
  constexpr ModInt operator/(const long long &r) const { return ModInt(*this) /= ModInt(r); }
  friend ModInt operator+(const long long &l, const ModInt &r) { return ModInt(l) += r; }
  friend ModInt operator-(const long long &l, const ModInt &r) { return ModInt(l) -= r; }
  friend ModInt operator*(const long long &l, const ModInt &r) { return ModInt(l) *= r; }
  friend ModInt operator/(const long long &l, const ModInt &r) { return ModInt(l) /= r; }
  constexpr ModInt &operator++() { return *this += 1; }
  constexpr ModInt &operator--() { return *this -= 1; }
  constexpr ModInt &operator+=(const ModInt &r) {
    n_ += r.n_;
    if (n_ >= mod_num) n_ -= mod_num;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &r) {
    if (n_ < r.n_) n_ += mod_num;
    n_ -= r.n_;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &r) {
    n_ = n_ * r.n_ % mod_num;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt r) {
    long long exp = mod_num - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r   *= r;
      exp /= 2;
    }
    return *this;
  }
  friend istream &operator>>(istream &is, ModInt<mod_num> &r) {
    is >> r.n_;
    r.n_ %= r.mod_num;
    return is;
  }
  friend ostream &operator<<(ostream &os, const ModInt<mod_num> &r) { return os << r.n_; }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
};

using mint = ModInt;
vector<vector<vector>> dp;
int main(void) {
  int n, k;
  cin >> n >> k;
  dp.assign(n + 1, vector<vector>(n + 1, vector(k + 100)));
  dp[0][0][0] = 1;
  rep (i, n) {
    rep (j, i + 1) {
      rep (l, k + 1) {
        dp[i + 1][j][l + 2 * j] += dp[i][j][l];
        dp[i + 1][j + 1][l + 2 * (j + 1)] += dp[i][j][l];
        dp[i + 1][j][l + 2 * j] += dp[i][j][l] * j * 2;
        if (j > 0) dp[i + 1][j - 1][l + 2 * (j - 1)] += dp[i][j][l] * j * j;
      }
    }
  }
  cout << dp[n][0][k] << endl;
  return 0;
}

むーずかしくなーーーーーい？？？？？
箱根駅伝DPってなんやねん。
箱根駅伝DPを知っていることの難しさに加え、kの遷移について工夫する必要がある点についても考えると、これマジでABCか？って感じ。
個人的今まで解いたABC最難問(最理不尽)は今でもサプリメントだが、典型の難しさと工夫の難しさは過去最高じゃないかなぁという気がする。

それと今回配るDPを使った。
貰うDPと配るDPの違いはあまり詳しく見ていなかったものの、書いていたらこういうことなんだろうなというのがここ1ヶ月くらいで分かってきた。
貰うDPの方が好きなのだが、さすがに今回は配るDPの方が書きやすそう。
ここで配るDP初心者の罠。
kの遷移ではkより大きい値は持ち得るのは分かるものの、kより大きいdpの値は答えとなるdp[n][0][k]には影響を及ぼさない(よね？)し、配るDPなら配列外参照しても答えには関係ないし、ということで気軽に配列外参照してやったのだが、全然ダメだった。
そういやC++って配列外参照したら既にあるデータ破壊することがあったわ・・・。
さすがに昔からC++使ってるのでWAの後すぐに気付けたが、本番ならWAカウント1だもんなぁ。
いつか読んだDPの配列は最大値プラスいくつか余裕持っておこうねが頭によぎる。
件のサプリメントでDPは最初に要素数決定しておいた方が良いかも、と少し考えたものの、自分がコンテストで競うよりも勉強に重点を置いていることを考えると、要素数を最大値と置くよりも入力値から最大値を決定した方がDPの状態・遷移を追えると思ったのでそのようにしていた。
入力値を使うにしても余裕をどれくらい持たせるべきかを把握して、いついかなるときも配列外参照はダメ！と思っておこう(C++の基本)。
以下本題。


最初問題読み間違えて順列部分を見落としていた。
「絶対値だから0の場合は1通り他の場合は±で2通りあるから分けてDP遷移させよう」なんて考えたけど全然違った。
全く思いつかなくてPDF解説読んだけど解説もむずかC。
読み間違えてていたとは言え、DPで解けそうという部分があってたのはgoodポイント。
YouTubeの解説の説明部分を軽く見て理屈を理解した気持ちになり、実際に実装してみるも答えが合わない。
見比べてみるとkの遷移が間違っていた。
動画やその他ブログ等で正しい遷移を調べてみるも、なぜそんな遷移になるのか全く分からなかった。
理解にかなり手間取ったので考え方をメモしておく。


今までやってきて知っているDPには、「その状態で確定した値」を入れていた。
この表現もそのまま聞いてもなんのことやらだが、簡単に言うとその状態で実際に数え上げたらその値になるということだ。
今回の問題で同じようなDPを考えるとうまく行かない。
Kの遷移のうち、保留していた点と新しい点をつなげる場合、増加する奇妙さkはどの点を保留しているかによって変わってしまう。
そうすると、どの点を保留しているかについても情報を保持する必要がある上、kの遷移も保留している点それぞれに行う必要が出てきてしまう。

今回のDPはそうではなくて、「その状態で最低限持ち得ることが保証された値(その状態が持つポテンシャル)」を入れる。
DPの遷移はYouTubeの解説通り(新しい点同士を繋ぐ), (新しい点をどちらも繋がない), (新しい点の片方と保留した点を繋ぐ), (新しい点の両方と保留した点を繋ぐ)の4つがある。
どの遷移についても保留した点を繋ぐのは新しい点であることから、保留した点は保留した点同士繋ぐことはないことが分かる。

次に、今見ているi段目の新しい点について、保留した点と繋がない遷移をする場合を考える。
その次のi+1段目の新しい点と保留した点を繋ぐことを考えると、i段目で繋ぐよりも1つ多く交差することになる。
また最終的には、保留した点は全て繋がれる必要があることから、今まで保留した点j個全ての点が1つ多く交差すると考えて良い。
よって、kを遷移させるときは、保留した点が左右で2つあることも踏まえて、(次のi+1段目で保留する点の個数)×2を足し合わせる。
なお、DPの遷移上、「残り1段しかないのに保留している点が10個ある」なんてことにもなるが、このような値は答えに影響しない。

このように考えると、新しい点と保留した点を繋ぐ遷移は、今まで足してきた「最低限持ち得ることが保証された値」を実際の値に確定させる遷移であるとも言える。
すると、新しい点と保留した点を繋ぐ遷移よりも、繋がない遷移の方がkの増加量が多いのは、「値を確定させる=i+1段目の遷移で交差できる点が減る」と捉えられるため直感的にも理解できる。
少なくとも自分はこのように理解している。


この実際の値としてはおかしい「最低限持ち得ることが保証された値」を保持するのは、「点を保留する」という、実際の状態としてはおかしい状態を保持するからだと考えている。
例えば、ナップサック問題についてのDPを考える場合、[特定の重さまで][特定の番目の品物まで]を状態として持つ。
これらの遷移は全て問題の条件としてありえる値である。
しかし今回のDPでは、[点を特定の個数保留する]という状態を持つが、点を保留した状態なんていうのは問題で許されていない。
最終的には必ず全ての点同士が繋がれていなければならない。
この中間値専用の仮想の状態が、特殊なkの遷移を生み出す。
先程も書いたような、どの点を保留しているかまで保持するようなDPを(時間やメモリの問題は置いておいて)考えると、このような特殊な遷移ではなく、毎回kの増加量を計算して足し合わせる一般的な遷移ができるのだが、この特殊な遷移が時間やメモリを節約するために工夫した部分となるのだろう。

問題
ACコード

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst) : src(src), dst(dst) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector;
using Graph = vector;

void edges_to_graph(Graph &graph, const Edges &edges, const int vertices, const bool directed = true) {
  graph.resize(vertices);
  for (const auto &e : edges) {
    graph[e.src].push_back(e);
    if (!directed) graph[e.dst].emplace_back(Edge(e.dst, e.src, e.weight));
  }
}

template 
class SparseTable {
  vector<vector> st;
  vector lookup;
  vector   vec;

  public:
  SparseTable(void) {}
  SparseTable(const vector &original_vecter) { init(original_vecter); }
  void init(const vector &original_vecter) {
    vec = original_vecter;
    int lgsize = 0, vsize = vec.size();
    while ((1 << lgsize) <= vsize) ++lgsize;
    st.assign((1 << lgsize), vector(lgsize));
    for (int i = 0; i < vsize; ++i) st[i][0] = i;
    for (int j = 1; j < lgsize; ++j) {
      for (int i = 0; i + (1 << j) <= (1 << lgsize); ++i) {
        int l = st[i][j - 1], r = st[i + (1 << (j - 1))][j - 1];
        st[i][j] = vec[l] <= vec[r] ? l : r;
      }
    }
    lookup.assign(vsize + 1, 0);
    for (int i = 2; i <= vsize; ++i) lookup[i] = lookup[i >> 1] + 1;
  }
  T query(int l, int r) {
    ++r;
    int lgsize = lookup[r - l];
    return min(vec[st[l][lgsize]], vec[st[r - (1 << lgsize)][lgsize]]);
  }
  int query_index(int l, int r) {
    ++r;
    int lgsize = lookup[r - l];
    T   lv = vec[st[l][lgsize]], rv = vec[st[r - (1 << lgsize)][lgsize]];
    if (lv < rv) return st[l][lgsize];
    else if (lv > rv) return st[r - (1 << lgsize)][lgsize];
    else return min(st[l][lgsize], st[r - (1 << lgsize)][lgsize]);
  }
};

class EulerTour {
  int num = 0;
  void et_dfs(const Graph &graph, const int v, const int p, const int dep) {
    tour.push_back(v);
    in[v] = num++;
    depth_tour.push_back(dep);
    depth[v] = dep;
    for (const auto &e : graph[v]) {
      if (e.dst == p) continue;
      et_dfs(graph, e.dst, v, dep + 1);
      tour.push_back(v);
      depth_tour.push_back(dep);
      ++num;
    }
    out[v] = num - 1;
  }

  public:
  vector tour, depth_tour, in, out, depth;
  EulerTour(void) {}
  EulerTour(const Graph &graph, const int v) { init(graph, v); }
  void init(const Graph &graph, const int v) {
    tour.clear();
    depth_tour.clear();
    in.assign(graph.size(), 0);
    out.assign(graph.size(), 0);
    depth.assign(graph.size(), 0);
    et_dfs(graph, v, -1, 0);
  }
};

class LowestCommonAncestor {
  class PM1RangeMinimumQuery {
    int block_size, block_num;
    vector vec, block_bit;
    vector<vector<vector>> lookup;
    SparseTable<pair<int, int>> st;

    public:
    PM1RangeMinimumQuery(void) {}
    void init(const vector &original_vecter) {
      vec = original_vecter;
      int vsize = vec.size();
      block_size = 0;
      while ((1 << block_size) < vsize) ++block_size;
      block_size = max(1, (block_size >> 1));
      while (vsize % block_size) {
        vec.push_back(vec.back() + 1);
        ++vsize;
      }
      block_num = vsize / block_size;
      vector<pair<int, int>> block_min(block_num, {INT_MAX, INT_MAX});
      for (int i = 0; i < vsize; ++i) block_min[i / block_size] = min(block_min[i / block_size], {vec[i], i});
      st.init(block_min);
      block_bit.assign(block_num, 0);
      for (int i = 0; i < block_num; ++i) {
        int left = block_size * i;
        for (int j = 0; j < block_size - 1; ++j) {
          if (vec[left + j] < vec[left + j + 1]) block_bit[i] |= (1 << j);
        }
      }
      int bit_all = 1 << (block_size - 1);
      lookup.assign(bit_all, vector<vector>(block_size, vector(block_size)));
      for (int b = 0; b < bit_all; ++b) {
        for (int i = 0; i < block_size; ++i) {
          int mini = 0, now = 0;
          for (int j = i + 1; j < block_size; ++j) {
            b&(1 << (j - 1)) ? ++now : --now;
            if (mini > now) {
              mini = now;
              lookup[b][i][j] = j - i;
            } else {
              lookup[b][i][j] = lookup[b][i][j - 1];
            }
          }
        }
      }
    }
    int query_index(int l, int r) {
      int lb = l / block_size, rb = r / block_size;
      int lbpos = l % block_size, rbpos = r % block_size;
      if (lb == rb) return l + lookup[block_bit[lb]][lbpos][rbpos];
      int lbmini = l, rbmini = r;
      if (lbpos != 0) {
        lbmini = l + lookup[block_bit[lb]][lbpos][block_size - 1];
        ++lb;
      }
      if (rbpos != block_size - 1) {
        rbmini = r - rbpos + lookup[block_bit[rb]][0][rbpos];
        --rb;
      }
      int mini = vec[lbmini] < vec[rbmini] ? lbmini : rbmini;
      if (lb <= rb) {
        pair<int, int> stpair = st.query(lb, rb);
        if (stpair.first < vec[mini]) mini = stpair.second;
      }
      return mini;
    }
  };
  PM1RangeMinimumQuery rmq;

  public:
  EulerTour et;
  LowestCommonAncestor(void) {}
  LowestCommonAncestor(const Graph &graph, const int v) { init(graph, v); }
  void init(const Graph &graph, const int v) {
    et.init(graph, v);
    rmq.init(et.depth_tour);
  }
  int query(const int a, const int b) {
    int l = et.in[a], r = et.in[b];
    if (l > r) swap(l, r);
    int idx = rmq.query_index(l, r);
    return et.tour[idx];
  }
};

Edges edges;
Graph graph;
int main(void) {
  int n;
  cin >> n;
  edges.resize(n - 1);
  rep (i, n - 1) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    edges[i] = {x, y};
  }
  int q;
  cin >> q;
  vector<pair<int, int>> ab(q);
  rep (i, q) cin >> ab[i].first >> ab[i].second;
  edges_to_graph(graph, edges, n, false);
  LowestCommonAncestor lca(graph, 0);
  vector ans(q);
  rep (i, q) {
    int a = ab[i].first - 1, b = ab[i].second - 1;
    int v = lca.query(a, b);
    ans[i] = lca.et.depth[a] + lca.et.depth[b] - 2 * lca.et.depth[v] + 1;
  }
  rep (i, q) cout << ans[i] << "\n";
  return 0;
}

LCAを解こうとして確認できそうな問題を探したらこれが良さそうだった。
バグりまくってすごく時間かかった。
実装力が+2くらいされた。

いわゆるEuler Tree + ±1RMQの形。
記号だからかなんなのか、±1RMQを検索しようとしてもほとんど引っかからない。
他人のコードを見てなんとか理解した。
頑張って実装した結果確かに速いが、定数倍重いなぁという印象。
RMQ→LCAはもっと重そうだから普通にセグメントツリーとかで良いかなぁ。
LCAに帰着しない形でSparse Table使ってO構築(n)クエリO(1)で解くアルゴリズムもあるみたいだが、理解に頭を使うことに疲れた・・・。
また今度余裕ができたらそっちも試してみよう。

順位: 1394
パフォーマンス: 1152
新レーティング: 281
差分: +225


まだ灰色。
次あたり茶色になれそう。

前回に続いて4完。
EをやめてFから解いてたら解けてそうかもしれない。
前回もそんなこと言って実際解いてみたら時間内は無理そうだったので今回もそれかもしれない。
別の問題でRMQの実装に戸惑ってEもFもまだ解いていない。

A問題

かんたん。

B問題

問題文がややこしい・・・。
理解と実装のスピードを高めないといけない。

C問題

書いたら添字も関係性がすぐ分かるやつ。

D問題

問題文読み間違えた！
やってしまった！
その結果飛ばしてE問題を考えて時間を浪費した。
RR,LLが幸福じゃなくて、RLみたいに向き合ってるのが幸福かと思ってしまった。
普通の人は前の人が同じ向き向いていても幸福だと思わない・・・。
E問題から帰ってきてもう1回考え直したら条件違うじゃん！ってなって5分か10分くらいで解けた気がする。
最後の処理ちょっとミスって1WA。
この間違った条件でも似たような感じで解けそうではある。

E問題

結構考えたけど解ける気がしなかった。
ABC128 E Roadworkを思い出してO(NQ)のどちらかを二部探索でlogにできるのではと考えたのだが、どっちもnじゃあどうしようも・・・という感じ。
何を考えればO(n^2)から片方のnを二部探索に持っていけるのか全く分からなかった。

解説を見るとシグマを外してある数との掛け算の形に直していて驚くしかない。
新しいパターン。
こういう考え方もあるのか。

F問題二部平衡木では？となぜか直感。
二部平衡木がどんなものかあまり詳しく知らないし、関連アルゴリズムも全く知らない。
セグメントツリーくらいか。
ということで深く考えるのをやめてEを解くことにしてFはあまり考えていない。

コンテストが終わってから軽く考えたら普通に解けそうだなぁと思ってきた。
コンテスト中は焦っているのでかなり時間を費やしたEを解こうと頑張っていたが、Eに時間を費やし始める前にFに取り組めば良かったかもしれない。
前回もしかり、EFは難易度が逆転することも結構ありそう？