2024-04-16

ABC332G - Not Too Many Balls

ABC格

非想定解あるある、制約のせいで逆に迷った。

問題概要

考えたこと

今回は 1-indexed で考えた方が圧倒的にわかりやすいのでそのように統一する。

箱の色容量

色 $ i $ のボールを $ j $ 番目の箱に $ j $ 個入れる操作を「 $ 1 $ 色入れる」と定義する。
このとき、色 $ i $ のボールを箱 $ j $ に $ ( i \cdot j ) $ 個入れる操作は「 $ i $ 色入れる」ことに等しい。

箱 $ j $ の容量は $ B _ j $ なので、箱 $ j $ に入れることができる色の総数（＝色容量）を $ C _ j $ とおくと、

$$ C _ j = \frac { B _ j } { j } \notag $$

である。

ボールを入れる

色容量 $ C _ j $ をなるべく余らせないようにしたいので、$ C _ j $ の大きい箱から優先的にボールを入れていきたい。
この時点で箱 $ j $ の容量 $ B _ j $ を考慮するのは面倒なので、一旦 $ B _ j $ を無視してボールを割り当てて、後で均すこととする。

色 $ i $ のボールを入れる箱の番号の総数の上限は $ \dfrac { A _ i } { i } $ であるから（"箱の色容量"と同様の議論）、これを超えないように $ C _ j $ の大きい順に箱を選ぶ。このとき、各色 $ i $ に対して、

ボールがちょうど $ ( i \cdot j ) $ 個入った箱
ボールが $ ( i \cdot j ) $ 個未満入った箱（高々 $ 1 $ 箱）
ボールが入らなかった箱

が存在する。1. については imos 法や双対セグメント木などで色の総数を管理すれば、箱 $ j $ に割り当てたボールの総数（ $ D _ j $ とする）を復元できる。

ボールを均す

$ C _ j $ の大きい箱から優先的にボールを入れた都合上、$ C _ l < C _ r $ を満たす箱 $ l , r $ について箱 $ l $ から箱 $ r $ へボールを移すことはできない。箱 $ l $ に入っているボールはどの色についても箱 $ r $ に満量入っているためである。
したがって、箱 $ r $ から箱 $ l $ へボールを移すことのみを考えればよい。

結論から言うと、箱 $ r $ から箱 $ l $ へボールを移す際に色の制約は実質的に無視することができて、箱 $ j $ の容量 $ B _ j $ のみに注意して可能な限りボールを移してしまえばよい。

上図のようにボールを移すと、箱 $ l $ に移動した部分は高さ（＝ $ 1 $ 色あたりのボールの個数）が圧縮されるので、色 $ i $ のボールは $ ( i \cdot l ) $ 個以下となっている。

ボールと箱容量の役割交換

計算量は、

箱を $ C _ j $ の降順にソートする部分：$ O ( M \log M ) $
ボールを入れる部分：二分探索により $ O ( N \log M ) $
ボールを均す部分： $ O ( M ) $

であり、全体で $ O ( ( N + M ) \log M ) $ である。

ボールと箱容量のマッチング問題であるため、ボールを箱容量に、箱容量をボールに読み替えてもよい。
そうした場合、$ O ( ( N + M ) \log N ) $ に収まる。

提出コード

atcoder.jp

2024-04-09

ABC297Ex - Diff Adjacent

ABC格

困ったときの平方分割。

問題概要

atcoder.jp

考えたこと

要素の総和が $ k $ の"素晴らしい整数列"の個数を $ f (k) $ とする。
また、このうち最後の要素が $ x $ であるものの個数を $ f _ x (k) $ とすると、

$$ f _ x (k + x) = f(k) - f _ x (k) $$

が成り立つ。

右辺にある $ f _ x (k) $ に (1) を代入し続けると、$ t = \lfloor \frac {k} {x} \rfloor $ として、

$$ \begin{align} f _ x (k + x) & = f (k) - f (k - x) + f (k - 2x) - f (k - 3x) + \cdots \notag \\ & \qquad \cdots + (-1) ^ t ( f (k - tx) - f _ x (k - tx) ) \notag \\ & = \sum _ { i = 0 } ^ t (-1) ^ i f (k - ix) - (-1) ^ t f _ x (k - tx) \notag \end{align} $$

ここで、$ f _ x (k) = 0 \, ( x > k ) $ であるから、

$$ \begin{align} f _ x (k + x) = \sum _ { i = 0 } ^ t (-1) ^ i f (k - ix) \notag \\ \Leftrightarrow f _ x (k) = \sum _ { i = 1 } ^ t (-1) ^ { i - 1 } f (k - ix) \end{align} $$

である。

(2) の右辺は $ k $ を昇順に見ていく際に各 $ x $ に対して $ k \bmod x $ の値によって管理することができるため、$ f _ x (k) $ の計算は $ O(1) $ で済む。
これを求めていけば最終的に $ f (N) $ が得られるが、愚直にやると時間計算量、空間計算量ともに $ O ( N ^ 2 ) $ であるから $ N \leqq 2e5 $ の制約においては厳しい。

これは平方分割の要領で解決できる。
具体的には、$ x > \sqrt N $ において $ f _ x (k) $ の総和を求めることを考えると、(2) の右辺は $ i $ の値によってもまとめることができて、各 $ i $ に対して $ k \bmod i $ の値で管理すればよい。
計算量は $ O ( N \sqrt N ) $ となる。

なお、出力する値は個数ではなく長さなので、同様に計算すること（省略）。

提出コード

atcoder.jp

2024-02-29

AGC047D - Twin Binary Trees

AGC格

問題概要

atcoder.jp

考えたこと

なんとなく、親ノードに遡りながら状態をまとめていけばよさそう。

当初、特殊辺を二つの木に対して同時に親ノード側に伸張することを考えたが、二つの特殊辺が片方の木でのみ接続するパターンに対する数え上げパートが原因でTLEした。

しばらくして、特殊辺の伸張はもう一方の木に対して独立に行うことができることに気付く。

二つの木をそれぞれ $ A, B $ とし、$ i $ 番目の特殊辺を $ ( a_i, b_i ) $ とすると、$ A $ に対して $ x $ 回、$ B $ に対して $ y $ 回親ノード側に遡った拡張特殊辺は $ ( a_i $ >> $ x, b_i $ >> $ y ) $ と表すことができる。

サイクルの積は、二つの拡張特殊辺 $ ( u, v ), ( u \, xor \, 1, v \, xor \, 1 ) $ を結ぶときに数え上げればよい。

拡張特殊辺をまとめるパートは、各 $ u $ に対して $ v $ を列挙する方法において、

$ v, v \, xor \, 1 $ -> $ ( v $ >> $ 1 ) $ : そのまままとめる
$ u, u \, xor \, 1 $ -> $ ( u $ >> $ 1 ) $ : マージソートの要領でまとめる

とすれば計算が間に合う。

各 $ x, y $ に対して拡張特殊辺の数は高々 $ 2 ^ H $ 本なので、計算量は $ O ( H ^ 2 ･ 2 ^ H ) $ である。

提出コード

空間計算量の改善を図った結果とても見づらいコードになってしまった（いつも通り）。

atcoder.jp

2023-09-20

自前ライブラリ自動挿入 for 競プロ

環境構築

kyokkounoite.hatenablog.jp

前回の続き。テンプレート化したアルゴリズムたちを毎回コピペするのは面倒なので自動化した。

target

C++er
Visual Studio Code

environment example

MSYS2
atcoder-tools

筆者は Visual Studio Code の Workspace Folder 以下のディレクトリを（無関係なものを除いて）以下のようにしている。

.
├── atcoder-workspace
│   ├── arc165
│   :   ├── A
│       :   └── main.cpp
│
├── library
│   ├── .include_base.hpp
│   ├── edge.hpp
│   ├── minimum_spanning_tree_kruskal.hpp
│   ├── union_find.hpp
│   :
│
└── library_inserter.py

code of library inserter

処理はそこまで重くないので Python で書いてみた。

以下のコードは自己責任の範疇において自由に複製・利用・改変してもらって構わない。

# library_inserter.py

import sys
import re


# line number of including ".include_base.hpp"
INCLUDE_BASE_LINE = 0

# maximum line number required to include other dependent libraries
MAX_INCLUDE_LINES = 10

# libraries are inserted above this expression in "main.cpp"
MAIN_LIBRARY_END = r'<templates end>'

# whether to remove a blank line directly above the line in which other dependent libraries are included
REMOVE_EMPTY_LINE = True


def recursive_inserter(main_data: list, library_path: str, already_inserted: set, insert_line: int) -> int:
    with open(library_path) as library_file:
        cnt = 0

        for line in library_file:
            body = re.fullmatch(r'#define [A-Z_]+HPP', line.strip())

            if body is not None:
                defined = body.group().replace(r'#define ', '')

                if defined in already_inserted:
                    return insert_line

                break

            cnt += 1
            if cnt >= MAX_INCLUDE_LINES:
                return insert_line

        already_inserted.add(defined)

        library_file.seek(0)
        skip = {INCLUDE_BASE_LINE}
        cnt = 0
        empty_line_above = False

        for line in library_file:
            if cnt != INCLUDE_BASE_LINE:
                body = re.match(r'#include "[a-z_/]+\.hpp"', line.strip())

                if body is not None:
                    insert_line = recursive_inserter(
                        main_data, body.group().replace(r'#include ', '').strip('"'), already_inserted, insert_line)

                    skip.add(cnt)
                    if REMOVE_EMPTY_LINE and empty_line_above:
                        skip.add(cnt - 1)

            cnt += 1
            if cnt >= MAX_INCLUDE_LINES:
                break
            empty_line_above = (line.strip() == '')

        library_file.seek(0)
        cnt = 0

        for line in library_file:
            if cnt not in skip:
                main_data.insert(insert_line, line)
                insert_line += 1

            cnt += 1

        main_data.insert(insert_line, '\n')
        main_data.insert(insert_line + 1, '\n')
        return insert_line + 2


def main(main_path: str, library_path: str):
    already_inserted = set()

    with open(main_path) as main_file:
        main_data = main_file.readlines()

    insert_line = 0

    for data in main_data:
        body = re.fullmatch(r'#define [A-Z_]+_HPP', data.strip())

        if body is not None:
            already_inserted.add(body.group().replace(r'#define ', ''))
        elif re.search(MAIN_LIBRARY_END, data) is not None:
            break

        insert_line += 1

    print(recursive_inserter(main_data, library_path, already_inserted, insert_line) - insert_line)

    with open(main_path, 'w', newline='') as main_file:
        main_file.writelines(main_data)


if __name__ == '__main__':
    if len(sys.argv) == 3:
        main(sys.argv[1], sys.argv[2])
    else:
        print('"library_inserter.py" failed due to the wrong parameter.', file=sys.stderr)
        print('The correct format is: $ library_inserter.py <main_path> <library_path>', file=sys.stderr)
        sys.exit()

細かな挙動については上記コードを参照のこと。

how to use

当然ながら path は環境に合わせて適宜変更すること。

.include_base.hpp

"main.cpp" には記述済みなので挿入したくないが、各ライブラリのメンテナンス性のために記述しておきたい部分。

#ifndef _INCLUDE_BASE_HPP
#define _INCLUDE_BASE_HPP
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 998244353;
#endif  // _INCLUDE_BASE_HPP

[[ library_name ]].hpp

以下を順不同でヘッダファイル上部に記述する。

".include_base.hpp" のインクルード
- 挿入行 (0-indexed) を INCLUDE_BASE_LINE ("library_inserter.py") に代入する
インクルードガード
他の依存ライブラリのインクルード

これらの行数が MAX_INCLUDE_LINES ("library_inserter.py") 以内になるように調整する。

// minimum_spanning_tree_kruskal.hpp

#include ".include_base.hpp"
#ifndef MINIMUM_SPANNING_TREE_KRUSKAL_HPP
#define MINIMUM_SPANNING_TREE_KRUSKAL_HPP

#include "edge.hpp"
#include "union_find.hpp"

// if G is disconnected, return -1
template<typename T>
T kruskal(Edges<T>& edges, int v) noexcept(false) {
  sort(edges.begin(), edges.end());
  UnionFind tree(v);
  T ret = 0;
  for(auto& e : edges) {
    if(tree.unite(e.from, e.to)) ret += e.cost;
  }
  if(tree.size(0) != v) throw -1;
  return ret;
}

#endif  // MINIMUM_SPANNING_TREE_KRUSKAL_HPP

main.cpp

MAIN_LIBRARY_END ("library_inserter.py") に格納した文字列を含めること。この文字列は挿入ライブラリとコード本体の境界線となる。

tasks.json

本当は library フォルダ内のファイル一覧を動的に取得して Visual Studio Code に反映させたかったが、結構な手間がかかりそうだったので諦めた。ライブラリを追加・削除する頻度はかなり低いはずなので大した問題ではなさそう。

{
  "tasks": [
    {
      "label": "insert library file",
      "type": "shell",
      "command": "python ../library_inserter.py '${file}' '${input:library_filename}'",
      "presentation": {
        "echo": false,
        "reveal": "silent",
        "focus": false,
        "panel": "shared",
        "showReuseMessage": false,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${workspaceFolder}/library"
      }
    }
  ],
  "inputs": [
    {
      "id": "library_filename",
      "type": "pickString",
      "description": "enter the template_filename",
      "options": [
        "edge.hpp",
        "minimum_spanning_tree_kruskal.hpp",
        "union_find.hpp",
        ...

      ],
      "default": ""
    }
  ]
}

keybindings.json

前回同様、Ctrl+K Ctrl+S などから開く。

[
  {
    "key": "Ctrl+F7",
    "command": "workbench.action.tasks.runTask",
    "when": "editorTextFocus && resourcePath =~ /^.*\/atcoder-workspace\/.*\/main.cpp$/",
    "args": "insert library file"
  }
]

winning run...

スクロールはされないので矢印キーで誤魔化すなど。

example of main.cpp with minimum_spanning_tree_kruskal.hpp here

#include <bits/stdc++.h>
using namespace std;

#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T> using Graph = vector<vector<T>>;
template<typename T> using Spacial = vector<vector<vector<T>>>;
template<typename T> using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>;
constexpr int MOD = 10;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
char interval[2] = {' ', '\n'};

template<typename T, typename... Args> auto make_vector(T x, int arg, Args... args) { if constexpr(sizeof...(args) == 0) return vector<T>(arg, x); else return vector(arg, make_vector<T>(x, args...)); }

template<typename T> struct is_plural : false_type{};
template<typename T1, typename T2> struct is_plural<pair<T1, T2>> : true_type{};
template<typename T> struct is_plural<vector<T>> : true_type{};
template<typename T> struct is_plural<complex<T>> : true_type{};
template<> struct is_plural<string> : true_type{};

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) { return is >> p.first >> p.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << p.first << ' ' << p.second; }
template<typename T> istream& operator>>(istream& is, vector<T>& vec) { for(auto itr = vec.begin(); itr != vec.end(); ++itr) is >> *itr; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { if(vec.empty()) return os; bool pl = is_plural<T>(); os << vec.front(); for(auto itr = ++vec.begin(); itr != vec.end(); ++itr) os << interval[pl] << *itr; return os; }
template<typename T> istream& operator>>(istream& is, complex<T>& x) { T a, b; is >> a >> b; x = complex<T>(a, b); return is; }
template<typename T> ostream& operator<<(ostream& os, const complex<T>& x) { return os << x.real() << ' ' << x.imag(); }

bool CoutYN(bool a, string yes = "Yes", string no = "No") { cout << (a ? yes : no) << '\n'; return a; }

template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); }

template<typename... Args> void debugger(int, const char*, const Args&...);
#define debug(...) debugger(__LINE__, #__VA_ARGS__, __VA_ARGS__)


/* -------- <insert libraries below> -------- */


#ifndef EDGE_HPP
#define EDGE_HPP

template<typename T>
struct edge {
  int from, to;
  T cost;

  edge(int to, T cost) : from(-1), to(to), cost(cost) {}

  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}

  operator int() const { return to; }

  bool operator<(const edge<T>& e) const {
    return cost < e.cost;
  }

  bool operator>(const edge<T>& e) const {
    return cost > e.cost;
  }

  bool operator==(const edge<T>& e) const {
    return from == e.from && to == e.to && cost == e.cost;
  }

  bool operator!=(const edge<T>& e) const {
    return !((*this) == e);
  }
};

template<typename T> using Edges = vector<edge<T>>;
template<typename T> using WeightedGraph = vector<vector<edge<T>>>;

#endif  // EDGE_HPP


#ifndef UNION_FIND_HPP
#define UNION_FIND_HPP

struct UnionFind {
  vector<int> data;

  UnionFind(int sz) {
    data.assign(sz, -1);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return false;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  int find(int k) {
    if(data[k] < 0) return k;
    return (data[k] = find(data[k]));
  }

  int size(int k) {
    return -data[find(k)];
  }
};

#endif  // UNION_FIND_HPP


#ifndef MINIMUM_SPANNING_TREE_KRUSKAL_HPP
#define MINIMUM_SPANNING_TREE_KRUSKAL_HPP

// if G is disconnected, return -1
template<typename T>
T kruskal(Edges<T>& edges, int v) noexcept(false) {
  sort(edges.begin(), edges.end());
  UnionFind tree(v);
  T ret = 0;
  for(auto& e : edges) {
    if(tree.unite(e.from, e.to)) ret += e.cost;
  }
  if(tree.size(0) != v) throw -1;
  return ret;
}

#endif  // MINIMUM_SPANNING_TREE_KRUSKAL_HPP


/* -------- <templates end> -------- */


void solve() {
  
}


/* -------- <programs end> -------- */


#define DEBUG
#ifdef DEBUG
void dbg() { cerr << '\n'; }
template<typename T, typename... Args> void dbg(const T& x, const Args&... args) { cerr << '\n' << x; dbg(args...); }
template<typename... Args> void debugger(int line, const char* str, const Args&... args) { cerr << line << " [" << str << "]:"; dbg(args...); };
#else
template<typename... Args> void debugger(int line, const char* str, const Args&... args) {};
#endif

#define COMPLEX_COMPARE
#ifdef COMPLEX_COMPARE
namespace std { template<typename T> bool operator<(const complex<T>& l, const complex<T>& r) { return real(l) != real(r) ? real(l) < real(r) : imag(l) < imag(r); } }
#endif

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}

2023-09-11

AtCoder用環境構築

環境構築

自分好みの環境構築で全部まとまってる記事は自分で作るしかない。

target

(OS: Windows)
MSYS2 MinGW64 GCC
Git
Visual Studio Code
atcoder-tools

install MSYS2

(参考)
MSYS2の導入 - 東京大学工学部精密工学科プログラミング応用 I・II
Windows10の開発環境をMSYS2で再構築 - Qiita
MSYS2 による gcc 開発環境の構築 - Qiita

インストール先のフォルダを

C:\programming\msys64

に変更する。諸々のツールを追加する際に C ドライブ直下が散逸するのを防ぎたい。

起動する MSYS2 は MinGW 64bit 版で統一する。

run pacman

パッケージ管理ツールの更新には色々流儀がありそう。

$ pacman -Sy pacman
$ pacman --needed -S bash pacman pacman-mirrors msys2-runtime
$ pacman -Su
$ pacman -S base-devel mingw-w64-x86_64-toolchain

各コマンドごとにターミナルを再起動して、更新されなくなるまで再度同じコマンドを実行させると安心できそう。

最後の mingw-w64-x86_64-toolchain をインストールすると GCC とともに Python もインストールされるはず。Group: mingw-w64-x86_64-toolchain - MSYS2 Packages から

toolchain > pkgconf > meson > python

の順に遡って辿れるので多分そう。

add PATH

Windows -> MSYS2

ユーザー環境変数のPathに C:\programming\msys64\mingw64\bin を追加

MSYS2 -> Windows

ユーザー環境変数に変数 MSYS2_PATH_TYPE 、値 inherit を追加
MSYS2でPATH が引き継がれない件 | こぼれネット

install Git

(参考)
【超入門】初心者のためのGitとGitHubの使い方 - RAKUS Developers Blog | ラクスエンジニアブログ
 VSCodeでGit・GitHubを使う方法を解説する【初心者向き】
リポジトリをクローンする - GitHub Docs

GitHub のプライベートリポジトリ上で競プロ用のアルゴリズムテンプレートを管理する。リポジトリ名は competitive にしてある。ついでに .vscode フォルダも push しておくと楽ができる。

改行コードの部分だけ気を付けてインストールする。デフォルトエディターの設定はそのままで問題ない。

git config

$ git config --global user.name [[ any_user_name ]]
$ git config --global user.email [[ any_email_address ]]

git clone

Git Bash を起動する。

$ cd /c/programming
$ git clone https://github.com/[[ user_name ]]/competitive.git

C:\programming\competitive フォルダが作成されていることを確認する。

GitHub 上に当該リポジトリをまだ作成していない場合は、

$ cd /c/programming
$ mkdir competitive
$ cd competitive
$ git init

でローカルリポジトリを作成する。

install Visual Studio Code

(参考)
VSCodeのインストール方法について解説する【初心者向き】

インストール先は変えずにそのままインストールする。PATH は自動的に追加される。

extensions

Japanese Language Pack for Visual Studio Code
C/C++
Bracket Lens

open folder

Visual Studio Code の [フォルダを開く] から

C:\programming\competitive

を開く。

git clone していない場合は .vscode フォルダ内の json ファイルを書き換えていく。それぞれファイルが存在しない場合は新規で作成すること。

.json files here (4 contents)

書き換えるべき部分だけ抜き出して記述してある。MSYS2 のインストール先が異なる場合はパスを適宜読み替えてほしい。

// c_cpp_properties.json

{
    "configurations": [
        {
            "name": "Win32",
            "includePath": [
                "${workspaceFolder}/**",
                "C:\\programming\\msys64\\mingw64\\include"
            ],
            "compilerPath": "C:\\programming\\msys64\\mingw64\\bin\\gcc.exe",
            "intelliSenseMode": "gcc-x64",
            "cppStandard": "c++20"
        }
    ],
    "version": 4
}

// settings.json

{
  "C_Cpp.default.includePath": [
    "C:\\programming\\msys64\\mingw64\\include",
  ],
  "C_Cpp.default.compilerPath": "C:\\programming\\msys64\\mingw64\\bin\\g++.exe",
  "C_Cpp.default.cppStandard": "c++20",
  "C_Cpp.default.intelliSenseMode": "gcc-x64"
}

g++ でデバッグすることも考慮して以下の 2 つも一応書き換えておく。ショートカットキーはあとで上書きするので、少なくとも AtCoder をやる上では意図せずデバッグが開始されることはない。

// tasks.json

{
  "version": "2.0.0",
  "tasks": [
    {
      "label": "g++.exe build active file",
      "type": "process",
      "command": "C:\\programming\\msys64\\mingw64\\bin\\g++.exe",
      "args": [
        "-std=c++20",
        "-g",
        "-O2",
        "${file}",
        "-o",
        "${fileDirname}\\${fileBasenameNoExtension}.exe",
        "-lgdi32"
      ],
      "group": {
        "kind": "build",
        "isDefault": false
      }
    }
  ]
}

"isDefault": true のままだと atcoder-tools でビルドしたときに "args" が上記の内容に置き換わってしまうので注意する。

// launch.json

{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "(gdb) Launch",
      "type": "cppdbg",
      "request": "launch",
      "program": "${fileDirname}\\${fileBasenameNoExtension}.exe",
      "args": [],
      "environment": [],
      "cwd": "${workspaceFolder}",
      "stopAtEntry": false,
      "externalConsole": true,
      "MIMode": "gdb",
      "miDebuggerPath": "C:\\programming\\msys64\\mingw64\\bin\\gdb.exe",
      "setupCommands": [
        {
          "description": "Enable pretty-printing for gdb",
          "text": "-enable-pretty-printing",
          "ignoreFailures": true
        }
      ],
      "preLaunchTask": "g++.exe build active file"
    }
  ]
}

customize

左下の歯車アイコン、あるいは Ctrl+, から [設定] を開き、右上のアイコンから [設定 (JSON) を開く] を探し出して settings.json を開く。好みに合わせてカスタマイズする。

// settings.json

{
    "workbench.startupEditor": "none",
    "editor.tabSize": 2,
    "files.eol": "\n"
}

install atcoder-tools

(参考)
Visual Studio Code の統合ターミナルで MSYS2 の bash を選択できるようにする - Qiita
MSYS2 で pip を使う - Qiita
VSCodeでAtCoder用環境を構築する｜デロイトトーマツウェブサービス株式会社（DWS）公式ブログ
 便利！ AtCoder で競技プログラミングをするときに重宝する AtCoder Tools のご紹介 - Qiita
GitHub - kyuridenamida/atcoder-tools: Convenient modules & tools for AtCoder users, written in Python 3.6

ここからが結構長い。

before installing...

set MSYS2 as default terminal

Visual Studio Code の規定のターミナルを MSYS2 に変更する。カスタマイズ時に使用した settings.json に追記する。"PowerShell" "Command Prompt" "Git Bash" の項目は変更しなくて良い。もしこれらの項目が存在していないなら、Ctrl+, で設定を開き terminal.integrated.profiles.windows で検索して [settings.json で編集] を押せば自動入力されるはず。

// settings.json

{
    "terminal.integrated.profiles.windows": {
        "PowerShell": {
            "source": "PowerShell",
            "icon": "terminal-powershell"
        },
        "Command Prompt": {
            "path": [
                "${env:windir}\\Sysnative\\cmd.exe",
                "${env:windir}\\System32\\cmd.exe"
            ],
            "args": [],
            "icon": "terminal-cmd"
        },
        "Git Bash": {
            "source": "Git Bash"
        },
        "MSYS2 Bash": {
            "path": [
                "C:\\programming\\msys64\\usr\\bin\\bash.exe"
            ],
            "args": [
                "--login"
            ],
            "env": {
                "MSYSTEM": "MINGW64",
                "CHERE_INVOKING": "1"
            },
            "overrideName": true
        }
    },
    "terminal.integrated.defaultProfile.windows": "MSYS2 Bash"
}

install pip

MSYS2 MINGW64 を起動する。MSYS2 で pip コマンドを使用できるようにする。Visual Studio Code のターミナルでも作業可能だが、その際は

$ cd ~

でホームディレクトリに移動しておく必要があるかも[要検証]。

$ pacman -S python3-pip
$ pip3 install --upgrade pip

installing now...

そのまま MSYS2 上で作業を進める。

$ pip3 install atcoder-tools
$ pip3 install markupsafe==2.0.1

after installing...

~/.atcodertools.toml を作成する。ホームディレクトリは /c/programming/msys64/home/[[ user_name ]] になっているはず。

# .atcodertools.toml

[codestyle]
indent_type='space' # 'tab' or 'space'
indent_width=2
template_file='/c/programming/competitive/template.cpp'
workspace_dir='/c/programming/competitive/atcoder-workspace/'
lang='cpp' # Check README.md for the supported languages.
# code_generator_toml="~/universal_code_generator.toml"
[postprocess]
# exec_on_each_problem_dir=''
# exec_on_contest_dir=''
[compiler]
compile_command='g++ main.cpp -o main -std=gnu++20 -O2 -Wall -Wextra'
compile_only_when_diff_detected=true
[tester]
compile_before_testing=true
compile_only_when_diff_detected=true
timeout_adjustment=1.2
[etc]
download_without_login=false
parallel_download=false
save_no_session_cache=false
skip_existing_problems=true
in_example_format="in_{}.txt"
out_example_format="out_{}.txt"

[postprocess] についてはまた後で設定する。

コード生成テンプレートファイルがない場合は作成する。

template.cpp here (1 content)

// template.cpp

#include <bits/stdc++.h>
using namespace std;

#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T> using Graph = vector<vector<T>>;
template<typename T> using Spacial = vector<vector<vector<T>>>;
template<typename T> using greater_priority_queue = priority_queue<T, vector<T>, greater<T>>;
{% if mod %}
constexpr int MOD = {{ mod }};
{% else %}
constexpr int MOD = 998244353;
{% endif %}
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
char interval[2] = {' ', '\n'};

template<typename T, typename... Args> auto make_vector(T x, int arg, Args... args) { if constexpr(sizeof...(args) == 0) return vector<T>(arg, x); else return vector(arg, make_vector<T>(x, args...)); }

template<typename T> struct is_plural : false_type{};
template<typename T1, typename T2> struct is_plural<pair<T1, T2>> : true_type{};
template<typename T> struct is_plural<vector<T>> : true_type{};
template<typename T> struct is_plural<complex<T>> : true_type{};
template<> struct is_plural<string> : true_type{};

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p) { return is >> p.first >> p.second; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << p.first << ' ' << p.second; }
template<typename T> istream& operator>>(istream& is, vector<T>& vec) { for(auto itr = vec.begin(); itr != vec.end(); ++itr) is >> *itr; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& vec) { if(vec.empty()) return os; bool pl = is_plural<T>(); os << vec.front(); for(auto itr = ++vec.begin(); itr != vec.end(); ++itr) os << interval[pl] << *itr; return os; }
template<typename T> istream& operator>>(istream& is, complex<T>& x) { T a, b; is >> a >> b; x = complex<T>(a, b); return is; }
template<typename T> ostream& operator<<(ostream& os, const complex<T>& x) { return os << x.real() << ' ' << x.imag(); }

bool CoutYN(bool a, string yes = {% if yes_str %}"{{ yes_str }}"{% else %}"Yes"{% endif %}, string no = {% if no_str %}"{{ no_str }}"{% else %}"No"{% endif %}) { cout << (a ? yes : no) << '\n'; return a; }

template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { return a > b && (a = b, true); }

template<typename... Args> void debugger(int, const char*, const Args&...);
#define debug(...) debugger(__LINE__, #__VA_ARGS__, __VA_ARGS__)


/* -------- <templates end> -------- */


void solve() {
  
}


/* -------- <programs end> -------- */


#define DEBUG
#ifdef DEBUG
void dbg() { cerr << '\n'; }
template<typename T, typename... Args> void dbg(const T& x, const Args&... args) { cerr << '\n' << x; dbg(args...); }
template<typename... Args> void debugger(int line, const char* str, const Args&... args) { cerr << line << " [" << str << "]:"; dbg(args...); };
#else
template<typename... Args> void debugger(int line, const char* str, const Args&... args) {};
#endif

#define COMPLEX_COMPARE
#ifdef COMPLEX_COMPARE
namespace std { template<typename T> bool operator<(const complex<T>& l, const complex<T>& r) { return real(l) != real(r) ? real(l) < real(r) : imag(l) < imag(r); } }
#endif

signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  solve();
  return 0;
}

これで一旦、ターミナル経由ならば atcoder-tools のコマンドが不自由なく使用できるようになっている。

set up keyboard shortcuts

(参考)
コマンドライン | 非公式 - Visual Studio Code Docs
Visual Studio Codeでタスク機能を使ってみよう - とことんDevOps | 日本仮想化技術のDevOps技術情報メディア
 【VSCode】キーボードショートカットを編集してみる

キーボードショートカットだけで機能させることを最終目標としている。

behavior of `atcoder-tools gen`

通常はファイルを生成して終わりだが、折角なので生成ファイルを全て開きたい。

よほどのことがない限り前から問題を解いていくので、後ろから生成ファイルを開いていく。AC してファイルを閉じていくと幸せになれそう。

set postprocess in .atcodertools.toml

一旦放置していた .atcodertools.toml を修正する。

# .atcodertools.toml

[postprocess]
exec_on_each_problem_dir='basename `pwd` >> ../.atcodertools_directories.txt'
exec_on_contest_dir='data=(`tac .atcodertools_directories.txt`); if [ ${#data[@]} -le 10 ]; then for dir in ${data[@]}; do code -g ${dir}/main.cpp:45:2; done; fi'

ファイル生成ごとにディレクトリ名を *\atcoder-workspace\[[ contest_id ]]\.atcodertools_directories.txt に追記し、すべてのファイル生成が終了したら追記内容を逆順に読み込み、読み込んだディレクトリ名順に *\atcoder-workspace\[[ contest_id ]]\[[ dirname ]]\main.cpp の 45 行 2 列目にキャレットを置いて開く、という挙動になっている。もし問題数が 10 問を超えていたらファイルを開かないようにしてある。

それなりに重たい処理になるので、マシンパワーが足りなければコメントアウトすることを推奨する。

set atcoder-tools commands in tasks.json

C:\programming\competitive\.vscode\tasks.json に追記する。もちろん、既に GitHub 上で管理できているなら不要な作業である。

tasks.json here (1 content)

// tasks.json

{
  "tasks": [
    {
      "label": "atcoder-tools gen",
      "type": "shell",
      "command": "atcoder-tools gen ${input:contest_id}",
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": false,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": true
      },
      "options": {
        "cwd": "${workspaceRoot}"
      }
    },
    {
      "label": "atcoder-tools test",
      "type": "shell",
      "command": "atcoder-tools test",
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": false,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    },
    {
      "label": "atcoder-tools submit",
      "type": "shell",
      "command": "atcoder-tools submit -u",
      "presentation": {
        "echo": true,
        "reveal": "always",
        "focus": true,
        "panel": "shared",
        "showReuseMessage": true,
        "clear": false,
        "close": false
      },
      "options": {
        "cwd": "${fileDirname}"
      }
    }
  ],
  "inputs": [
    {
      "id": "contest_id",
      "type": "promptString",
      "description": "enter the AtCoder contest_id",
      "default": ""
    }
  ]
}

特に "tasks": "focus" や "tasks": "close" については好みに合わせて書き換えるべし。

"cwd" の設定はキーバインドと連携させるので記述通りにすること。

set keyboard shortcuts in keybindings.json

左下の歯車アイコン、あるいは Ctrl+K Ctrl+S から [キーボードショートカット] を開き、右上のアイコンから [キーボードショートカットを開く (JSON)] を探し出して keybindings.json を開く。

// keybindings.json

[
  {
    "key": "Ctrl+F1",
    "command": "workbench.action.tasks.runTask",
    "when": "resourceDirname == /c/programming/competitive",
    "args": "atcoder-tools gen"
  },
  {
    "key": "F5",
    "command": "workbench.action.tasks.runTask",
    "when": "editorTextFocus && resourcePath =~ /^.*atcoder-workspace.*main.cpp$/",
    "args": "atcoder-tools test"
  },
  {
    "key": "F9",
    "command": "workbench.action.tasks.runTask",
    "when": "editorTextFocus && resourcePath =~ /^.*atcoder-workspace.*main.cpp$/",
    "args": "atcoder-tools submit"
  }
]

Visual Studio Code のエクスプローラー上で C:\programming\competitive が開いているなら問題なく動作するはず。

F5 に atcoder-tools test を割り当てることで [デバッグの開始] を抑制している。別のキーを割り当てる際は [キーボードショートカット] から検索をかけてみて、意図しない挙動が起こらないように注意する。

git push (optional)

(参考)
【超入門】初心者のためのGitとGitHubの使い方 - RAKUS Developers Blog | ラクスエンジニアブログ (再掲)
VSCodeでGit・GitHubを使う方法を解説する【初心者向き】 (再掲)

簡潔に記す。わからなければ上記サイトを参照すること。

.gitignore

C:\programming\competitive\.gitignore を作成する。

.gitignore here (1 content)

# .gitignore

# git ls-files --others --exclude-standard

# Ignore files generated by atcoder-tools
/atcoder-workspace/

# Ignore any other files if needed

push

Visual Studio Code の左上のアイコン群から [ソース管理] を開き、ステージングしてから [コミットしてプッシュ] する。

winning run...

後書きのようなもの。

PC を新調したので、競プロ歴 5 年目にしてようやく自動化ツールを導入した。

当初は online-judge-tools を導入する予定だったが、WSL 環境を嫌って MSYS2 でどうにかならないか丸 1 日かけて、結局どうにもならず。エラーが発生する度に原因を探し出して解決し、そして新たなエラーが発生する、というループを何度か繰り返しているうちにエラーを解決できなくなって諦めた。

atcoder-tools の方でも、インストール自体は難なくできたものの細かな仕様が不明瞭で(それはそう)、ソースコードを辿ったりシェルコマンドの構文を調べたり実験してみたり、そうこうしているうちに更に 2 日かかってしまった。その分個人的にはかなり満足のいく環境になったので良しとする。

あとはアルゴリズムテンプレートの自動挿入ができれば完璧か。

[2023/09/20 追記] 自動挿入できるようになった。

kyokkounoite.hatenablog.jp

2023-03-05

ABC277 (大和証券プログラミングコンテスト2022 Autumn) Ex - Constrained Sums

ABC格

問題概要

（筆者は問題を要約することに疲れたようです）

atcoder.jp

考えたこと

$ X_i $ の範囲を絞る

$ L_i \leqq X _ {A_i} + X _ {B_i} \leqq R_i $ に着目する。

$ X_i $ のとり得る範囲を $ L ^ X _ i \leqq X_i \leqq R ^ X _ i $ とする。
仮に $ X _ {B_i} $ の範囲を $ \overline { L ^ X _ {B_i} } \leqq X _ {B_i} \leqq \overline { R ^ X _ {B_i} } $ に固定したとして考えるとき、$ X _ {A_i} $ は

$ L_i \leqq L ^ X _ {A_i} + \overline { R ^ X _ {B_i} } $
$ R ^ X _ {A_i} + \overline { L ^ X _ {B_i} } \leqq R_i $

を満たす必要がある。つまり、 $ X _ {A_i} $ の下限値は $ max ( L ^ X _ {A_i} , \, L_i - \overline { R ^ X _ {B_i} } ) $ に更新され、上限値は $ min ( R ^ X _ {A_i} , \, R_i - \overline { L ^ X _ {B_i} } ) $ に更新される。

すべての $ i $ に対して $ \lbrace L ^ X _ i , \, R ^ X _ i \rbrace = \lbrace 0 , \, M \rbrace $ で初期化し、BFS（あるいはDFS）を用いて $ L ^ X _ i , \, R ^ X _ i $ を更新することを繰り返すと、条件を《なんとなく》満たすような $ X_i $ の範囲が求まる。
また、この過程で $ L ^ X _ i > R ^ X _ i $ となるような $ i $ が存在するとき、題意を満たす整数列 $ X $ は存在しない。

上限値と下限値の平均を考える

求まった範囲に関して、$ X _ {A_i} , \, X _ {B_i} $ の範囲をそれぞれ固定したとして考えてみると、

$ L_i \leqq L ^ X _ {A_i} + R ^ X _ {B_i} \leqq R_i $
$ L_i \leqq L ^ X _ {B_i} + R ^ X _ {A_i} \leqq R_i $

が成り立つことがわかる。これらの平均をとると、

$$ L_i \leqq \dfrac { L ^ X _ {A_i} + R ^ X _ {A_i} } { 2 } + \dfrac { L ^ X _ {B_i} + R ^ X _ {B_i} } { 2 } \leqq R_i $$

となる。よって、《平均値が整数なら》その値を $ X_i $ とすればよい。問題となるのは平均値が整数でない場合である。

$ \dfrac { L ^ X _ i + R ^ X _ i } { 2 } = Ave ( i ) $ とおく。

$ Ave ( A_i ) , \, Ave ( B_i ) $ のいずれか一方のみが小数であるとき、(1) は [整数] $ \leqq $ [小数] $ \leqq $ [整数] となることから、$ X_i = \lfloor Ave ( i ) \rfloor , \, \lceil Ave ( i ) \rceil $ のどちらでもよい。
したがって、両方ともに小数であるときのみを考えればよい。

$ Ave ( i ) $ の小数部分は $ 0.5 $ であるから、

$ L_i \leqq \lfloor Ave ( A_i ) \rfloor + \lceil Ave ( B_i ) \rceil \leqq R_i $
$ L_i \leqq \lceil Ave ( A_i ) \rceil + \lfloor Ave ( B_i ) \rfloor \leqq R_i $

は常に成り立つ。

2-SAT への帰着

結局のところ、

$ ( X _ { A_i } = \lfloor Ave ( A_i ) \rfloor ) \, \land \, ( X _ { B_i } = \lfloor Ave ( B_i ) \rfloor ) $
$ ( X _ { A_i } = \lceil Ave ( A_i ) \rceil ) \, \land \, ( X _ { B_i } = \lceil Ave ( B_i ) \rceil ) $

が成立するかどうかを判定し、成立しない部分を 2-SAT にぶち込んでしまえば、題意を満たす整数列 $ X $ が存在するか判定できる。

例えば $ L_i > \lfloor Ave ( A_i ) \rfloor + \lfloor Ave ( B_i ) \rfloor $ であるとき、$ X _ { A_i } , \, X _ { B_i } $ にどんな値を代入しようとも $ ( X _ { A_i } > Ave ( A_i ) ) \, \lor \, ( X _ { B_i } > Ave ( B_i ) ) $ を満たす必要があり（もう一方も然り）、これらの論理式を充足できなければ当然に整数列 $ X $ は存在し得ないため、$ Ave ( i ) $ 近傍のみを見るだけで充分であると言える。

計算量

BFS（あるいは DFS）で $ X_i $ の範囲を絞るパートが一番重く、$ O ( ( N + Q ) M ) $ である（ $ X_i $ の範囲が更新される回数は高々 $ M $ 回）。
2-SAT のパートは、頂点数 $ O ( N ) $、辺数 $ O ( Q ) $ より $ O ( N + Q ) $ になる。

おそらく想定解より定数倍が相当軽い実装になっていると思われる。

提出コード

atcoder.jp

2023-01-22

ABC256 (東京海上日動プログラミングコンテスト2022) Ex - I like Query Problem

ABC格

結論から言うと、クエリ平方分割で O(N√Q log(max {A}) + Q(√Q + logQ)) で解けます。

問題概要

atcoder.jp

考えたこと

クエリ 1 が曲者で、通常の遅延セグメント木には乗せられないため、仕方なく「困ったときの平方分割」をしてみる。

√Q 回のクエリを 1 ブロックとしてまとめると、クエリ全体として √Q 個のブロックがあることになる。
したがって、ブロックあたりおよそ O(N logN) くらいに収めることを考える。

前述の通り、1 ブロックあたりのクエリ回数は √Q 回なので、クエリ区間の切れ目も高々 2√Q 箇所である。
そこで、高々 (2√Q + 1) 個に細分化した区間に対して、それぞれ高々 √Q 回のクエリを行う。
区間の細分化には座標圧縮を伴い、O(√Q logQ) である。

区間内の全要素が等しい場合、1 つの値のみを変化させるだけになるので、どのクエリも O(1) で実行可能である。
なお、ブロック内の全区間に対する全クエリを終わらせたあとで、数列 A に値を代入することになるため、その計算に O(N) かかる。

次に、区間内の要素が異なる場合を考える。

クエリ 2 は、区間内の全要素を等しくする効果があるので、1 区間に対して 1 つの値のみを保持すれば良いことになる。
また、クエリ 3 については、クエリ 1 を行うごとに区間 sum を計算しておけばよい。
どちらも実質的に O(1) になる。

続いて問題のクエリ 1 については、高々 log(max {A}) 回行えば区間内の全要素が 0 になる。
各要素を愚直に除算するとして、区間 [L, R) に対して 1 回あたり O(R - L) で済むので、全区間全クエリでは O(N log(max {A})) で収まる。

以上を踏まえると、ブロックあたりの計算量は O(N log(max {A}) + Q + √Q logQ) となる。
これを √Q ブロック分繰り返せば良い。

提出コード

atcoder.jp

問題概要

考えたこと

箱の色容量

ボールを入れる

ボールを均す

ボールと箱容量の役割交換

提出コード

問題概要

考えたこと

提出コード

問題概要

考えたこと

提出コード

target

environment example

code of library inserter

how to use

.include_base.hpp

[[ library_name ]].hpp

main.cpp

tasks.json

keybindings.json

winning run...

target

install MSYS2

run pacman

add PATH

Windows -> MSYS2

MSYS2 -> Windows

install Git

git config

git clone

install Visual Studio Code

extensions

open folder

customize

install atcoder-tools

before installing...

set MSYS2 as default terminal

install pip

installing now...

after installing...

set up keyboard shortcuts

behavior of atcoder-tools gen

set postprocess in .atcodertools.toml

set atcoder-tools commands in tasks.json

set keyboard shortcuts in keybindings.json

git push (optional)

.gitignore

push

winning run...

問題概要

考えたこと

$ X_i $ の範囲を絞る

上限値と下限値の平均を考える

2-SAT への帰着

計算量

提出コード

問題概要

考えたこと

提出コード

behavior of `atcoder-tools gen`