競プロ日記

現在エディタはVSCodeを使っている。
以前はAtomを使っていたのだが、数ヶ月前にVSCodeを使ってみるとかなり軽くて動作も安定していてすぐに乗り換えた。
ターミナル環境はなしで、C++コンパイラにはMinGW-w64を使い、BOOSTは自前でビルドしていた。
特にBOOSTのビルドが面倒くさかった・・・。

ところがこの数ヶ月でVSCodeとコンパイラ周りに色々問題が発生してしまい、1から環境構築を行うことになった。
1からVSCodeのターミナル内でビルド実行できるまで環境構築を行ったので、今度困らないようにメモしておく。
自分用メモではあるが、他人が見ても使えるように説明も入れておく。

といっても、コンパイラ環境構築はMSYS2を使ったら一瞬だった。
Linuxかよ。
ターミナル環境しゅごい・・・。
試しにClangも入れてみたが、Clangの方がエラーメッセージが見やすい気がするので乗り換えた。
gccに依存しているようなので、#include <bits/stdc++.h>も自分で作ることなく使える。
もちろんAtCoder等に提出の際はgccを選ぼう。

2019/11/11追記
VScode 3.task.json
"presentation": "panel"とコンパイルオプションと説明等を一部編集 
コンパイル&実行を高速にする書き方の追加

コンパイラ関連

1. MSYS2(64bit)をインストール。

2. pacman(パッケージ管理システム)をアップデート

   pacman -Syuu

3. Clangをインストール

   pacman -S mingw-w64-x86_64-clang
   (pacman -Ss clangで名前が変わっていないか等パッケージ検索できる)

4. BOOSTをインストール

   pacman -S mingw-w64-x86_64-boost
   (これだけ！ビルドいらない！)

5. gdbをインストール(オプション デバッグするなら)

   pacman -S mingw-w64-x86_64-gdb

VSCode

1. 公式拡張機能C/C++をインストール

2. setting.jsonに以下を追加(GUIでも可)

   "C_Cpp.default.compilerPath": "C:\\msys64\\mingw64\\bin\\clang++.exe",
   "C_Cpp.default.cppStandard": "c++14",
   "C_Cpp.default.cStandard": "c11",
   "C_Cpp.default.intelliSenseMode": "clang-x64",
   

3. tasks.json

   {
     // See https://go.microsoft.com/fwlink/?LinkId=733558
     // for the documentation about the tasks.json format
     "version": "2.0.0",
     "tasks": [
       {
         "label": "build c++",
         "type": "shell",
         "command": "clang++",
         "args": [
           "${relativeFileDirname}\\${fileBasename}",
           "-std=gnu++14",
           "-DLOCAL",
           "-g",
           "-O2",
           "-o",
           "${relativeFileDirname}\\${fileBasenameNoExtension}.exe",
         ]
       },
       {
         "label": "build & run C++",
         "type": "shell",
         "command": "chcp.com 65001; ${relativeFileDirname}\\${fileBasenameNoExtension}.exe",
         "dependsOn": [
           "build c++",
         ],
         "group": {
           "kind": "build",
           "isDefault": true
         },
         "presentation": {
           "panel": "shared"
         }
       },
       {
         "label": "run C++",
         "type": "shell",
         "command": "chcp.com 65001; ${relativeFileDirname}\\${fileBasenameNoExtension}.exe",
         "group": {
           "kind": "test",
           "isDefault": true
         },
         "presentation": {
           "panel": "shared"
         }
       }
     ]
   }
   

   
   文字コードがUTF-8を前提とすると、ターミナルで実行すると文字化けする(と思う)。
   これを解決するには"chcp.com 65001"等でターミナルの文字コードを変更する必要があるが、最初に一度実行しただけではダメ。
   パネルは一緒でも内部的にはおそらく新しいターミナルで実行されているので、毎回実行の前に毎回文字コードを変更する必要がある。
   現状他の手段は知らないが、こう書くと"Active code page: 65001"がプログラムの切れ目の判別にも使えて良いかも。
   VSCodeのターミナルで実行するかどうかは個人差があると思うが、この方が楽だと思う。
   特にWindowsは自動でサンプルケースを実行してくれるツール等の導入が面倒なので、手動でやるならせめて少しでも楽したい。
   なお、コンパイルオプションの-DLOCALは、LOCALを定義することでローカル環境のみで機能するマクロを実現するために入れている。
   
   2019/11/11追記
   この書き方だとコンパイル&実行がかなり遅い。
   まずdependsOnでタスクを呼び出すのが遅いのと、文字コードの変更を途中に挟むと一度クリアが挟むからなのか遅くなる。
   ということで頭悪そうだが以下のようにベタ書きするとかなり早くなる。
   ターミナルから直接コンパイル&実行した時と比べて明らかに遅いのは、VSCode内部で処理が入っているからだと思っていたが、このように書けば遜色ない速度になる。
   プログラムもタスクの設定もベタ書きが最速だぜ！
   

       {
         "label": "debug build c++",
         "type": "shell",
         "command": "clang++",
         "args": [
           "${relativeFileDirname}\\${fileBasename}",
           "-std=gnu++14",
           "-W",
           "-DLOCAL",
           "-o",
           "${relativeFileDirname}\\${fileBasenameNoExtension}.exe",
         ]
       },
   

4. ビルド用のショートカットキーを編集

   デフォルトでは"Shift+Ctrl+B"でビルドタスクの実行になっており、上記の設定ではコンパイルと実行がこれで行える。
   2回目以降の実行でもコンパイルをするのは無駄なので、テストタスクの実行をショートカットキーにすると時間の節約になる。
   自分は"Ctrl+Alt+B"に設定している。
   おそらくmakefileを使えば1つのコマンドで無駄なコンパイルも無くせるが、フォルダごとにmakefileを作るのは面倒なのでこの形式にしている。
   ファイル名を取得してmakefile1つだけでうまくやる方法もありそうだが、makefileはあまり詳しくないので知っている人がいたら教えて欲しい。

VSCode オプション

• コードフォーマッタ

  Atomを使っていた頃はAtom-beautifyでUncrustifyを使っていたが、VSCodeではデフォルトでclang-formatが入っているためこれを使っていた。
  Uncrustifyより設定が楽で、なおかつプロファイル毎に結構良い感じにフォーマットしてくれるのだが、どうしても納得いかない部分がいくつか出てきてしまった。
  VSCodeにも拡張機能としてUncrustifyが提供されているので乗り換えた。
  C++ではフォーマッタとしてUncrustifyが優先して使用する設定と、毎回フォルダに設定ファイルをコピーしなくてもデフォルトとして読み込む設定ファイルのパスを決める設定をしておく。
  せっかくコードフォーマッタを活用するなら保存(Ctrl+S)の度に整形するようにしておこう。
  ある程度書いて保存すればエディタが強制終了しても大丈夫だし、見やすくするために入れるスペースなんかも自動で入れてくれて結果的に早くなるかもならないかも。
  

  "[cpp]": { "editor.defaultFormatter": "LaurentTreguier.uncrustify", },
  "uncrustify.configPath.windows": "uncrustify.cfgのパス",
  

• デバッグ

  VSCodeのデバッグ機能は結構高機能らしいので、デバッグも設定すると良いかもしれない。
  自分は昨日始めて設定したが、競技プログラミングに限ればあまりいらないかなぁという印象。
  task.jsonと同じディレクトリにlaunch.jsonを作成する。
  

  {
    // IntelliSense を使用して利用可能な属性を学べます。
    // 既存の属性の説明をホバーして表示します。
    // 詳細情報は次を確認してください: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
      {
        "name": "clang++.exe build and debug active file",
        "type": "cppdbg",
        "request": "launch",
        "program": "${fileDirname}\\${fileBasenameNoExtension}.exe",
        "args": [],
        "stopAtEntry": false,
        "cwd": "${workspaceFolder}",
        "environment": [],
        "externalConsole": false,
        "MIMode": "gdb",
        "miDebuggerPath": "C:\\msys64\\mingw64\\bin\\gdb.exe",
        "setupCommands": [
          {
            "description": "Enable pretty-printing for gdb",
            "text": "-enable-pretty-printing",
            "ignoreFailures": true
          }
        ],
        "preLaunchTask": "build c++"
      }
    ]
  }
  

終わり。
競技プログラミングの環境構築とは書いたものの、普通のC++コーディングも同じ環境で行っている。
そちらではC++17を使用している等、主にtask.jsonは変更しているが。
競技プログラミングでも早く構造化束縛使わせて。

これだけ書いておけば新しいパソコンを買っても大丈夫だ！
自分で好き勝手設定したあの膨大なUncrustifyの設定ファイルだけは無くすととても嫌な気持ちになるから気をつけよう・・・。

後この忍者ブログとかいうサイトわざわざ<br>入れても自動で消してくるのさすがに頭おかしい。

問題

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, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector;
using Graph = vector;

Graph edges_to_graph(const Edges &edges, const int vertices_num, const bool directed = true) {
  Graph ret(vertices_num);
  for (const auto &e : edges) {
    ret[e.src].push_back(e);
    if (!directed) ret[e.dst].push_back(Edge(e.dst, e.src, e.weight));
  }
  return ret;
}

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;
void dfs(const Graph &g, int v, int p, int k, mint &sum) {
  if (g[v].size() == 1) return;
  rep (i, g[v].size() - 1) {
    sum *= k - 2 - i;
  }
  for (const auto &es : g[v]) {
    if (es.dst == p) continue;
    dfs(g, es.dst, v, k, sum);
  }
}
Graph graph(100001);
Edges edges(100001);
int main(void) {
  int n, k;
  cin >> n >> k;
  // Edges edges(n - 1);
  rep (i, n - 1) {
    cin >> edges[i].src >> edges[i].dst;
    --edges[i].src;
    --edges[i].dst;
  }
  // Graph graph = edges_to_graph(edges, n, false);
  rep (i, n - 1) {
    graph[edges[i].src].push_back(edges[i]);
    graph[edges[i].dst].push_back(Edge(edges[i].dst, edges[i].src, edges[i].weight));
  }
  int start, next;
  rep (i, n) {
    if (graph[i].size() == 1) {
      start = i;
      next  = graph[i][0].dst;
      break;
    }
  }
  mint sum = k;
  if (n > 1) {
    sum *= (k - 1);
    dfs(graph, next, start, k, sum);
  }
  cout << sum << endl;
  return 0;
}

今回の学びはスタック領域は思ったよりも弱いということ・・・。
解き方は分からなかったので解説を見た。
思ったより単純でグラフの苦手意識が抜けてないのかなと思う。
方針だけ見て後は自力で！と思ったんだけど全然ACできない。
最初の3つのテストケースだけまさかのRE。
割り算とかやってないし範囲外アクセスしかないかなぁと悩み続け、範囲外アクセスの原因になりそうなところ(グラフの次数が1の頂点を探す部分)を変えて全部WAにするつもりで提出したら1つだけACで他WA。
おそらく答えが0になる部分なんだけろうけど、やはりここが間違いだった？と思うもどう考えても間違っているはずがない。
グラフが木なら次数が1の頂点が必ずあるはず。

そこから色々探って最終的に、Vectorのメモリ足りてないのでは？と思い立つ。
今までVectorには基本的にプリミティブ型やそのPair等しか入れていなかったが、今回は構造体を入れている。
最近作ったグラフ関連の構造体だ。
上限は10^5なのでもしやということでヒープ領域に取ってみるとREの2つがWAになり、おそらく答えが0になるテストケースがACになった。

残りの2つは、自分の実装が「根とその子は初期値として最初に計算して残りをDFSで計算する」という形だったため、n=1のときに根の子がないのにある体で初期化してしまっていたのが原因だった。


今までも10^5くらいのVectorはスタック領域に取っていたような気はするのだが、今回ついに問題になった。
世間ではグローバル変数はあまり使うべきではないと言われているが、自分もそれを学生時代に感じたため、基本的には全てローカル変数として宣言している。
学生時代には基礎だけで事足りており、その後プログラミングすることがなかったので、グローバル変数に対する考え方もその頃のままだった。
取れるメモリの上限に引っかかる問題を解決する方法はいくつかあるようだが、グローバル変数も手段の1つとして入れても良いかもしれない。
競技プログラミングにおいてはグローバル変数一択だとは思うが。

初めてコンテストに参加したぞ！

順位: 2665
パフォーマンス: 813
新レーティング: 56
差分: -


結果はABCDの4完。
最初だしレート変動もほとんどないから良かったものの、Cで2WA、Dで2WAしてしまった。
どちらも考え方も実装もほぼ問題なかったのに小さなミスが原因だ。
しかもそれになかなか気づけずに合わせて15分程浪費してしまった。
ミスのペナルティはもちろん、15分あればE問題をACにできた可能性が無くもないので細かいミスには気をつけていきたいところ。

A問題

簡単

B問題

普段のB問題と比べて難しくない・・・？
最初単純に3^nかと思って解いたら全然違う答えが出て、問題文しっかり読んでないじゃん！とちょっとパニックになって紙に書き起こした。
合計5分以上かかった。

C問題

B問題より簡単。
初回提出もB問題より早かったのだが、ミス潰せなくて20分近く使って合計25分くらい。
特に2番目のミスはなかなか気づけなかった。

C問題のミス

1. ループ内で計算した一時変数を全体の最大値と比較代入する処理を繰り返した後、最後の出力の部分でカウント用の一時変数を出力してしまった。
2. if文で一時変数の増加、else文で一時変数と最大値との比較、一時変数の初期化を行っていたが、ループの最後にelse文が実行されない条件式になっていたため、最後の一時変数が最大値に代入されることがなかった。

D問題

これもかなり簡単だった。
今の所B問題が突出して難しくて、CDはそれより早く正しい実装に取りかかれた印象。
簡単な問題にはミスがつきもの。
C問題より遥かにひどい・・・。
ちょっと前にこれ最近だけで3回くらいやったから気をつけようって言ったところのやつ。
初コンテストの同じ問題で2回やるかね。
なんならこれから全部long long型でやっても良いまである。

D問題のミス

1. 答えのint型がオーバーフローしていた。
2. 答えをlong long型にするも、そもそもint型同士の計算途中でオーバーフローしていた。

E問題

テストケースが1つだけTLEで他はACという状態だった。
曰く最悪計算量がO(n^3)になっているらしい。
自分の中では、ループ文の最初でcontinuteしたらそれはオーダーに入れなくて良いからO(n^2)という計算で、なぜTLEするのかまるで分からなかったのだが、そういうことではないらしい。
どこかのなにかの解説で、ループの最初でcontinuteするからオーダーは～みたいなことを書いていた記憶があったのだが・・・。
もっと重い処理を書いていて、continuteの部分はO(10^8)に届かない範囲で気にしなくても良いねっていうことだったのかもしれない。

F問題

D問題が終わった段階でE問題とどっちから解くか比べて、どっちもそこそこ解けそうだけどF問題はハマったらヤバそう、という考察でE問題を解きにいった。
結局解く時間はなかった。
書いてたら方針思いつくかと一応入力部分だけ書いたのだが、先に解くかどうか決めてから取り掛かった方が良いのかな。

コンテストが終わってからも考えてみたものの全然分からなかった。
象限ごとに分けて考えたいなぁと思ったまでは良いものの、その先に進めなかった。
解説動画を見てなんとか納得。
偏角ソートは幾何の問題ではそこそこ出てくるみたいなので覚えていこう。
どうやって実装しようか悩んだ結果結局実装しなかったのだが、ベクトルAとベクトルBが反時計回りに180度以内ってどう判定しようか。
ベクトル周辺の知識あんまり覚えていない。


案外ABCDは早く解けてまた成長感じた。
Eも本当にあと一歩だったので全完もそんなに遠くはないのかなという気がする。
目標の黄色に年内に届くかどうかは全く分からない。
競技プログラミング始めて休止して始めて休止して、なんだかんだでのべ3ヶ月くらいなのでまだまだ伸びしろはあると信じたい。
今週も参加したいね。

https://atcoder.jp/contests/abc131/submissions/7223770

#include <bits/stdc++.h>
#define rep(i, n)     for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n)    for (int i = 1; i <= (int)(n); ++i)
#define irep(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(V, v)  for (auto &&V : v)
#define all(x)        (x).begin(), (x).end()
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = 1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;

class UnionFind {
  std::vector parent_;

  public:
  UnionFind(int size_num) : parent_(size_num, -1) {}
  int find(int x) {
    if (parent_[x] < 0) return x;
    return parent_[x] = find(parent_[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (parent_[x] > parent_[y]) std::swap(x, y);
    parent_[x] += parent_[y];
    parent_[y]  = x;
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
  int size(int x) {
    return -parent_[find(x)];
  }
};

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n;
  cin >> n;
  vector x(n), y(n);
  rep (i, n) cin >> x[i] >> y[i];
  UnionFind uf(100001);
  unordered_map<int, int> firstx;
  rep (i, n) {
    if (firstx.find(y[i]) == firstx.end()) {
      firstx[y[i]] = x[i];
    }
    uf.unite(firstx[y[i]], x[i]);
  }
  unordered_set checkedy;
  lint cnt = 0;
  rep (i, n) {
    if (checkedy.find(y[i]) == checkedy.end()) {
      cnt += uf.size(x[i]) - 1;
      checkedy.insert(y[i]);
    } else {
      --cnt;
    }
  }
  cout << cnt << endl;
  return 0;
}

ABCの最終問題は3回に1回くらいの割合でほぼ自力で解けるイメージなのだが、最近は難しい問題が続いていたのと、行列とかセグメントツリーとかの実装に時間を費やしたおかげで、自力で解けた！という感覚が久しぶり。
1回しか使ったことないのにUnionFind使えそうだなって気づけたのは成長感じる。
前回はインデックスを保存していたので、値に対してもUnionFindを使えると気づくのに少し手間取ったが、気づけば方向性の決定はすぐだった。

今回は実は完全に自力ではなく、WAしてからテストケースをチラ見してACした。
int型じゃ答えが入り切らなかった・・・。
ここ2,3日だけでこのミス3回くらいした気がする、マジで気をつけよう。

自力で解けた基本的には書くことがないのだが、他の解説と本質は同じ(だと思う)だが見かけの考え方が書かれてなくて後でどう考えたんだろうってなりそうなのでメモ。
二部グラフなんて二色で塗れますかしか知らないので思いつくはずもない。

考え方

x軸を主にしてもy軸を主にしても良いが、ここではx軸を主にする。

とりうるy座標の値全てに対して、そのy座標を持つ点のx座標の集合を作成する。
ある点Pと同じy座標に新たに点を追加することを考えた場合、その点Pのx座標[Px]が含まれる全ての集合の、[Px]以外の全てのx座標[Xi]を持つ点[Xi, Py]が追加される。
全てのy軸に対してこの操作を行うと、点Pを点に持つ長方形を全て作成できる。
※ここでは追加したい点に既に点があることは考えない。

すなわち、x座標が与えられたときに、そのx座標が属している集合を全て求められれば良い。
ここで、点を追加する際に、点Pのy座標以外のy座標は考えなくても良いことに気づくので、x座標が含まれる集合はy座標ごとに保持する必要はなく、集合間に重複する要素がある場合は結合しても良いことが分かる。
結合することでO(n*yMAX)からO(n)になって間に合う。


なぜ結合して良いのか、なぜy軸についても同じ操作をしなくて良いのか、感覚的にあやふやになりそうなので僅かに理論的な説明。

まず、なぜy軸についても同じ操作をしなくて良いのかについて。
点を追加しきった最終的な形を見ると、長方形を成している4つの点と、同じx座標かy座標を持つ点が3つ以上無く、2つ以下で独立している点に分けられる。
3つの点から長方形を作るパターンでは、左上・右上・左下・右下のどの点が欠けている場合でも、上記の方法で正しく長方形を作成することができる。
長方形は3つの点からしか作ることができないので、x軸かy軸いずれかを主にして考えるだけで全ての長方形を作成することができる。
2つ以下で独立した場合については、どちらを主にして考えても長方形を作ることができないので、どちらで考えても良い(どちらでも考える必要がない)。
よって、どちらか片方のみについて考えるだけで良い。

次に、なぜ結合して良いのかについて。
点Pを基点に点を追加して長方形を作成するためには、問題文の条件から、
・点Pと同じx座標を持つ点X1& 点Pと同じy座標を持つ点Y1
・点Pと同じx座標を持つ点X2, 点X2と同じy座標を持つ点Y2
・点Pと同じy座標を持つ点X3, 点X3と同じx座標を持つ点Y3
これらのパターンのどれかの点Xと点Yが同時に存在することが必要になる。
「点Pのx座標[Px]が含まれる集合があること」は、同じx座標を持つ点Xがあることを示す。
また、集合は同じy座標を持つ点について考えており、重複する要素がある場合は結合するが、「重複して集合の要素数が増加する=結合前の集合はそれぞれ少なくとも要素が2つ以上存在する」ことが言える。
集合を結合するとy軸の値の情報を無くしてしまうが、重複した要素は別の集合とのy軸の違いの架け橋になってくれる。
重複した点を点A(Ax, Ay)とすると、(点A, 追加された点(Ax, Py), 結合したい集合に含まれる点)を元に新たに長方形を作成できる。
よって、結合しても問題なく長方形を作成することができる。


話は戻って、結合した集合を作成できれば、後は数え上げるだけである。
点Qを基点にして考える場合、点Qのx座標が含まれる集合の要素数-1(自身の分は追加しない)だけカウントを追加する。
全ての点に対してこの操作を行うと、「同じy座標に対して何度も点の追加作業をしてしまう」という問題が発生する。
重複で追加をしなくても、先程は考えなかった、「追加すべき点に既に点があった場合、無駄に点を追加してしまう」という問題がある。
これらの問題を解決するために、以下の操作を行う。
・点を追加したy座標を記録する。
・点Qのy座標がすでに記録されていた場合、点の追加は行わず、自身と重複する点の追加を防ぐためにカウントを-1する。


実装
後で書くかも


頭の中のイメージはほとんど完成してるのに実装に結構時間を取られた。
集合の結合なんてせずに、○○が含まれる集合簡単に列挙できるデータ構造とかコンテナの使い方とか知ってればもっと楽だったんだけどあるのかしら。
どうやって実装するかの部分で悩んだのは結構久々だった。


今日はABC・・・と思ったら明日に延期されたみたいですね。
21:00開始予定だったけど実は18:30時点でもう結構眠いので延期されてよかった。

いくら解説読んでも理解できない。
Siで終わる場合の組み合わせ総数としてDPを立て、総和を求めれば良い、という方の解説はあまり読んでいないがある程度理解できた。
問題は公式のYouTubeの解説にもある、LCSの応用版みたいなdpの方である。
大体の解説が「dpの更新式を+=にすれば解けそうだが重複するのでそこを考えよう」という流れになっているが、+=にすれば解けそうの意味が分からない。
なぜ解けそうなのか。
理解できる気がしなかったので初の詰み問題となって、ブログにも「解けない」なんていうカテゴリができてしまった。
一応dpの遷移の練習として実装してACできたが、今後解ける気がしない。
めっちゃ丁寧な解説記事が出るのを待つ。