nakashiiiの自由帳

自由に書きます

neovimを導入した備忘録

雑メモ 環境構築

neovimの導入にかなり手こずったので、次回思い出すためのメモ。
プラグイン追加したら、追記していくかも。

  • OS：macOS Big Sur 11.6.8
  • ターミナル：iTerm2
  • 対象言語：C++

インストールしたもの

neovim

GitHub - neovim/neovim: Vim-fork focused on extensibility and usability brew install した

現状のinit.vimはこんな感じ

"プラグイン
packadd vim-jetpack
call jetpack#begin()
Jetpack 'tani/vim-jetpack', {'opt': 1} "bootstrap
Jetpack 'neoclide/coc.nvim', { 'branch': 'release' }
Jetpack 'EdenEast/nightfox.nvim'
Jetpack 'nvim-treesitter/nvim-treesitter', {'do': ':TSUpdate'}
call jetpack#end()

"設定
syntax enable
colorscheme nightfox

lua <<EOF
require'nvim-treesitter.configs'.setup {
  highlight = {
    enable = true,
  },
}
EOF

LLVM

LLVM を Mac にインストール - solareenlo

この記事を参考に brew install した

  • PATHを通す
  • shellを再起動

を忘れずに。（忘れていて「あれ〜動かないぞ〜」をやってました）

LLVM自体が何かはよく分かっていない。「C++に必要ななんやかんやがたくさん入ってるやつ」くらいの認識。今回はclangdというものが欲しかったので入れた

iTerm2

iTerm2 - macOS Terminal Replacement

デフォルトのターミナルだと、あとから紹介するシンタックスハイライト用のnightfoxがうまく動かなかったのでこちらをインストール。

bear

https://github.com/rizsotto/Bear

makefileからcompile_commands.jsonを生成するツール 。 bear -- make でmakefileからcompile_commands.jsonを生成してくれる。
compile_commands.json はcoc.nvimを使って補完をする時に必要らしい。

Makefile

free: free.cpp
    g++ -std=c++17 -Wall -O2 free.cpp -o free

compile_commands.json

[
  {
    "arguments": [
      "/usr/local/bin/g++",
      "-c",
      "-std=c++17",
      "-Wall",
      "-O2",
      "-I",
      ".",
      "-I",
      "/作業ディレクトリのパス/ac-library",
      "-o",
      "free",
      "free.cpp"
    ],
    "directory": "/作業ディレクトリのパス",
    "file": "/作業ディレクトリのパス/free.cpp",
    "output": "/作業ディレクトリのパス/free"
  }
]

インストールしたもの（neovimプラグイン関係）

vim-jetpack(パッケージマネージャー)

GitHub - tani/vim-jetpack: The lightning-fast plugin manager, alternative to vim-plug
上記のInstallationのコマンドを実行しただけだったはず、、

パッケージマネージャーについてはこの記事を参考にした。
Vimのプラグインマネージャの種類と選び方 - Qiita

結局、自分のような初心者は動きさえすれば、なんでもよい（あとから変更できる）ので、

  • 利用者が多い
  • 簡単に使えそう

あたりで選んだ。書き方が簡単そうなvim-jetpack（vim-plugの後継？）にした

プラグインをインストールする時は、以下のように Jetpack [プラグイン名] みたいな感じで init.vim に追記して、 :JetpackSync を実行する

coc.nvim

GitHub - neoclide/coc.nvim: Nodejs extension host for vim & neovim, load extensions like VSCode and host language servers. neovim用のlanguage server protocolのクライアント。そもそもlanguage server protocol（以下、LSP）は何かというと、以下の記事が詳しい。（よく分かってないので丸投げ）

language server protocolについて (前編) - Qiita

補完、整形、構文チェックなどの、コーディング支援的なやつをプロトコル化して、導入しやすくしようね。みたいな理解。
これを入れておくと、細かい設定がなくても上記のようなコーディング支援を一発でインストールできるので、自分みたいな初心者にはピッタリかも。

:CocConfig で設定ファイルをいじれる。

coc-clangd

https://github.com/clangd/coc-clangd

coc.nvimが入っていれば、 :CocInstall coc-clangd するだけ（だったはず）。上記のQuickStartに色々書いてあるが、LLVMインストール済みでPATHが通ってれば、他の作業は不要なはず。

これを入れて、makefileつくってcompile_commands.jsonをつくれば、以下のような感じで補完がきくようになってるはず

coc.nvimでC++の補完
coc.nvimでC++の補完

ただし、C++での競技プログラミングで使っている #include <bits/stdc++.h> のヘッダーがclangにはないので、その設定をする必要がある。
clang++ -xc++ -fsyntax-only -v /dev/null を打つと、clangがヘッダーファイルを探しに行く場所が分かるので、そのどこかにbitsディレクトリをつくって、 stdc++.h ヘッダーを置く。以下の記事を参考に。

clang で bits/stdc++.h を使う - Qiita

ここまでくれば、標準ライブラリの補完はすべてOK。 multisetとかで補完きいてるか確かめてみる。

nvim-treesitter

https://github.com/nvim-treesitter/nvim-treesitter

よく分かってない。詳しい説明はこちら。
日常に彩りを加える nvim-treesitter の設定術

今回は、「関数に対してシンタックスハイライトをつけたい」というモチベーションで導入。
インストールしたあと、以下を init.vim に追記。

syntax enable
colorscheme nightfox

lua <<EOF
require'nvim-treesitter.configs'.setup {
  highlight = {
    enable = true,
  },
}
EOF
~

nightfox.nvim

https://github.com/EdenEast/nightfox.nvim

デフォルトのシンタックスハイライトを変更したくて導入。
init.vimに colorscheme nightfox を追記する。こんな感じになる。

気になる

気になってるもの。追記したりするかも。

  • tmux

参考

ちゃんと考察する練習をしたメモ

競プロ 雑メモ 精進 累積和

こちらの記事で「ちゃんと考察してから解きましょうね」（超意訳）と書いてあり、最近はその練習をしています。

初心者が陥りがちな嘘貪欲やコーナーケースやその他諸々に関して - えびちゃんの日記

記事で例題として載っている問題について、コードを書いたので、そのメモ。 あとからランダムなテストケースで確認できるように、愚直解もいっしょに載せる。

負の値を含む区間和の数え上げ

問題

（気が向いたら考察書く。とりあえずコメントには書いてある） → 書いた

負の値を含む数列の区間和を求めたい

まずはサンプル見てみる[] は最大となる区間を表す

1 2 3 -1000 [4 5] -1000 6
→ 9 が最大
[1 2 3 -1 4 5 -1 6]
 → 19が最大

考察のポイント

  • 全探索を考えてみる
  • 探索対象がふたつあって, O(N2)の時は, 一方を固定してみる
  • 二分探索は単調性がある時に有効(今回は使えない)
  • ソート済み状態を保ちながら集合を管理したい時は, そういうデータ構造使うと便利
    • set → 重複なし集合. 今回は負の値があるので, 累積和が重複するので NG
    • multiset → 重複あり集合. 今回は集合の値が重複するので, 有効. 集合の任意の値の削除も O(logN)でできる
    • priority_queue → 重複あり集合. 今回は見終わった値の削除がしたいが, priority_queue は最大の要素しか削除できないので NG
  • 区間和は累積和を使うと, うまく求まる

考察(思考垂れ流し ver.)

  • 区間を全探索で 2 重ループにすると O(N2)になって間に合わない
  • 尺取っぽいな. 尺取で単調費減少の区間でやってみる
    • 合計が減少したあとに, 最大値をとることがあるのでダメそう
  • でも, 区間を[l,r)とすると, l は固定して全探索しておきたい
  • 区間を[l,r)の 各 l での l<=r<=n の中での最大値がほしい(図参照)
  • l が固定されると, 累積和を使うとなんかうれしそう
  • 累積和 sum[l]<=sum[r]の範囲で最大のものを求めたい
  • なんか, r を二分探索したいなあ. でも, 負の値があるので累積和の単調性がない
  • なんとかして, 常に区間[l,r)の累積和の集合が, ソート状態を保てるようにしたい
  • set とか multiset とか priority_queue だな.
  • set は重複取り除くのでダメ. priority_queue は見終わった値を取り除けないのでダメ.
  • multiset でできそうかも？
    • 累積和計算して, multiset に突っ込む
    • 集合の最大値 → multiset の末尾要素みればよい
    • 見終わった区間を無視 → multiset から,現在の累積和 sum[0,l)を取り除く
    • multiset に入ってるのは l=0 の時の累積和なので, 区間和[l,r)じゃないよね？
    • → 取り除いた累積和[0,l)を引けば, 区間和[l,r) になる

コーナーケース

  • 区間[l, l) = 区間をひとつも選ばない時はあるのか？
    • 0<=l<=r<=n なので, ありえる. a の要素がすべて負の時は, [l,l)=0 が最大となる
  • 区間の数の最小は？
    • n=1. 上記解法で n=1 の場合も正常に動くはず
  • 区間やループ範囲に気をつける
    • l を全探索 0<=l<=n
    • mutiset から取り除くのは sum[l] は大丈夫？
      • l=0 の時, 0 が取り除かれる.
      • l=1 の時, a[0]が取り除かれる.
      • l=2 の時, a[0]+a[1]が取り除かれる.
      • 見終わった累積和[0,l)が取り除かれてるので大丈夫そう

コード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const long double EPS = 1e-14;
using plint = pair<ll, ll>;
using pint = pair<int, int>;
using Graph = vector<vector<int>>;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = a; i < b; ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define fore(i, a) for (auto i : a)
#define all(obj) (obj).begin(), (obj).end()
template <typename T> inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T> inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }

/**
 * 考察メモ
 *
 * (案)
 * - 区間[l, r)とすると,
 * - lをi<nで全探索
 * - aをセグ木にのせて, 各lでのrを求めて, 値を求める
 * うーん、いまいちダメそう
 *
 * (案)
 * - 区間を正の区間と負の区間に区切って, 配列を再度つくる.
 * - {-, +, -, +,..}みたいな配列が出来上がる
 * - 符号ごとに累積和をとっておくとうれしい？
 * うーん、よくわからん
 *
 * (案)　※有力
 * 累積和を取って, multiset に突っ込む
 * lを走査しながら, multiset から一番大きい数字を出力.
 * l+1に行く時に, multiset から累積和のl要素を削除する
 *
 */
// NOTE: 型は？ → 10^9 * 10^5 = 10^14 で ll

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  // 累積和
  a.insert(a.begin(), 0);
  vector<ll> sum(n + 1);
  inclusive_scan(all(a), sum.begin());

  // multisetに突っ込む
  multiset<ll> s;
  rep(i, n + 1) s.insert(sum[i]);

  // NOTE: ループ範囲を詰めていない. 怪しいかも
  // lを走査しながら, multisetから一番大きい区間を探す
  ll ans = 0;
  rep(l, n + 1) {
    auto it = s.end();
    --it;
    chmax(ans, *it - sum[l]);
    s.erase(s.find(sum[l]));
  }
  cout << ans << endl;
}

愚直解

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const long double EPS = 1e-14;
using plint = pair<ll, ll>;
using pint = pair<int, int>;
using Graph = vector<vector<int>>;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = a; i < b; ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define fore(i, a) for (auto i : a)
#define all(obj) (obj).begin(), (obj).end()
template <typename T> inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T> inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// 関数定義------------------

// メイン------------------
int main() {
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  a.insert(a.begin(), 0);
  vector<ll> sum(n + 1);
  inclusive_scan(all(a), sum.begin());

  ll ans = 0;
  rep(l, n + 1) rep(r, l, n + 1) chmax(ans, sum[r] - sum[l]);
  cout << ans << endl;
}

個人的三分探索のテンプレメモ

三分探索 競プロ

二分探索の問題を解いていたら、凸グラフの頂点を求めたくなって、ついでに三分探索の練習したのでメモ。問題は以下。

B - 花束

三分探索詳しい説明は以下のサイトを参考に（というかほぼそのまま実装）した。

今回は整数のみの練習で、実数は扱ってない。

テンプレ

添字で混乱しないように、参考サイトから名前を変更してある

  // 3分探索で最も大きい本数を求める (グラフは上に凸)
  ll lo = LO_INIT;
  ll hi = HI_INIT;
  while (abs(lo - hi) > 2) {
    ll cl = (lo * 2 + hi) / 3;
    ll ch = (lo + hi * 2) / 3;
    if (f(cl) > f(ch)) {
      hi = ch;
    } else {
      lo = cl;
    }
  }

  // lo, lo+1, hi の3つのいずれかが求めたい値
  ll ans = 0;
  rep(i, lo, hi + 1) ans = max(ans, f(i));
  cout << ans << endl;

気をつけるポイント

  • 関数fでオーバーフローとゼロ除算に気をつける
  • LO_INIT、HI_INITは、関数fがとりうる範囲で設定すること

練習した問題

Submission #33388398 - AtCoder Regular Contest 050

上記は想定解法が2分探索なので、実装がちょっとめんどくさいことになっている。

添字迷子にならないための練習

競プロ 累積和

以下の記事を見ながら練習したことのメモ。

rsk0315.hatenablog.com

現状、以下の記事内の

何も考えずに AC するまで [i] [i+1] [i-1] などを適当に書き換えるような癖はつけない方がいいと思います。

みたいなことが度々あるので、少しずつ書き改めていく。

※練習のため、上記の記事からの新規性はほぼゼロです。

累積和

実装

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

  // 元の配列
  vector<int> a(n);
  rep(i, 0, n) cin >> a[i];
  a.insert(a.begin(), 0);

  // 累積和
  vector<int> sum = a;
  rep(i, 1, n + 1) sum[i] += sum[i - 1];

  // 逆からの累積和
  vector<int> t(n + 1, sum[n]);
  rep(i, 1, n + 1) t[i] -= sum[i];

  // 階差
  vector<int> diff(n + 1);
  rep(i, 1, n + 1) diff[i] = a[i] - a[i - 1];

  // 階差から元の配列を復元
  vector<int> b(n + 1);
  b[0] = 0;
  rep(i, 1, n + 1) b[i] = b[i - 1] + diff[i];

  rep(i, 0, n + 1) cout << setw(2) << a[i] << " ";
  cout << ":元の配列" << endl;
  rep(i, 0, n + 1) cout << setw(2) << sum[i] << " ";
  cout << ":累積和" << endl;
  rep(i, 0, n + 1) cout << setw(2) << t[i] << " ";
  cout << ":逆からの累積和" << endl;
  rep(i, 0, n + 1) cout << setw(2) << sum[i] + t[i + 1] << " ";
  cout << ":a[i]を覗いた累積" << endl;
  rep(i, 0, n + 1) cout << setw(2) << diff[i] << " ";
  cout << ":階差" << endl;
  rep(i, 0, n + 1) cout << setw(2) << b[i] << " ";
  cout << ":階差から元の配列を復元" << endl;
}

ポイント

  • 元の配列の初項を 0 にする
  • 入力はいつもどおり, サイズ n で受け取れる. あとから最初の要素に 0 を insert
  • 累積和の配列は a をコピーするだけなので, 長さは考えなくていい
  • 累積和の計算は前から順番に走査しながら足していくだけ
  • 区間和は半開区間で求まる. s[i] は 区間[l,r)の和
  • つまり, 0-indexd の[l, r]の累積和は, [l, r+1)なので, sum[r+1] - sum[l] で求まる
  • 階差も初項 0 で考える

練習問題の提出

二分探索

（練習したら書く）

尺取法

（練習したら書く）

2022 年後半の競プロ精進について

競プロ 雑メモ

2022 後半は、前半よりも競プロの時間を取れない（取らないと決めた）ので、どのように精進しようか迷っている。 以下はその思考メモ。

  • やっぱり水色になりたい
  • 水色になるためには、以下のようなことが必要そう（体感）
  • 現状はたぶんこんな感じ
    • 7,8 割くらいで 4 完できる
    • 遅いときでは C 問題まで 40,50 分くらいかかったりする
    • 10 回に 1 回くらい 5 完できる
    • A,B 問題もたまに手間取る A:10 分弱, B:15 分みたいな？
    • 茶 diff を落とすことはほとんどない
    • 緑 diff は解けたり解けなかったり
    • 水 diff はだいたい解けない
  • 自分の課題は以下のようなこと
    • 1 度履修した典型アルゴリズムをサラッと書けない。(尺取、01-bfs など)
    • 水 diff の考察をしきれない
    • 簡単な問題を解くのに時間がかかる
  • 上記を踏まえて、精進候補としてはこんな感じ
    • 緑 diff 埋め(D 問題まで素早く解く練習)
    • 水 diff 埋め(5 完の確率を上げる)
    • バチャ(実装訓練寄り)
    • 典型 ★4 復習
    • DEF 問題埋め(5 完の練習)
    • 前に解いた問題の復習(知識の定着を図る)
    • 苦手アルゴリズムの集中訓練
  • うーん、とりあえずこんな感じでやってみる
    • 水 diff を 100 まで埋める (試験管なし) ※現在 45
    • 苦手アルゴリズムの集中訓練
      • 01bfs
      • 尺取
      • 水 diff 埋めで出会ったやつ
  • 理由
    • 色変する人はだいたい色+1 の問題解いてるので, それを信じて水 diff 解く(まあ、普通に考えても色変したければ色++解いたほうが良い)
    • 現在 45 なので、とりあえず 50 問くらい解いてみれば、次にやることが見えてきそう
    • 苦手アルゴリズムの集中訓練はなんとなく、めっちゃ大事な気がするのでやる
    • (バチャは楽しいけど、今は見送り)

という感じでやっていくぞ！

半年間で競プロを 546 時間やった振り返り（茶 424 → 緑 904）

競プロ 雑メモ

年初に「今年の前半は競プロをがんばる！」と決めて半年間取り組んだので、その振り返りです。取り組んだこととその感想が主な内容です。
自分の備忘録目的で殴り書きした感じなので、あまりまとまりがない上に、箇条書きですがご了承ください m(_ _)m

結論としては、「競プロ楽しく取り組めてよかったなー！」です。

自己紹介

ざっくりと。

  • 高専の非情報系出身です。1
  • 2021 年の 11 月から AtCoder で競プロを再開2しました
  • 仕事は web サイト開発で 主に PHP を書いてます3
  • 競プロの使用言語は C++です4
  • 好きなベーシストはピノ・パラディーノです

競プロを始めたきっかけ

  • 現在プログラムを書く仕事をしているのですが、「プログラムを書く上での基礎」があまり身についていないと感じていました。具体的には、コンピュータの動作原理であったり、ネットワークの動作原理であったり、競プロで学べるアルゴリズムとデータ構造であったり、などです。
  • 足りないものをあげるときりがないのですが、その中でも比較的楽しく学べそうな「アルゴリズムとデータ構造」の基礎を身に着けたいという理由で競プロをはじめました。
  • また、2022 年の年初に今年こそは目標を立てっぱなしにしないで、何かがんばりたい！と思って、競プロなら楽しくできそうだなと思ったためです。
  • 一応年初の目標は、「半年で競プロに 700 時間使う」だったのですが、結局 546 時間で目標達成ならずでした、、残念。

スプレッドシートにちまちま勉強時間を記録してました

レート推移と精進量

レート推移や精進量はこんな感じです。

レート推移

パフォ推移

成長、、しているような、、してないような、、

解いた問題

streakは単調増加で気持ちいいので続けています

精進の芝生（赤色はAHCです）

月ごとのレート推移と勉強時間

月 レート推移 勉強時間
2022/01 424 → 547 (+123) 94h
2022/02 547 → 678 (+131) 110h
2022/03 678 → 800 (+122) 96h
2022/04 800 → 857 (+57) 99h
2022/05 857 → 919 (+62) 100h
2022/06 919 → 904 (-15) 47h

うーん、明らかにレートが伸びづらくなっているので、ここからが根性試されるなあ、、という感じがします。（そして、勉強時間が如実に減っていますね、、）

アルゴリズム・データ構造と習熟度

以下は、アルゴリズム・データ構造とその習熟度です。
茶〜緑 diff の問題が出た時を想定しています。

アルゴリズム 習熟度
全探索 書ける
bit 全探索 書ける
二分探索 書ける
尺取法 書ける(怪しい)
累積和 書ける
DFS 書ける
BFS 書ける
01-BFS 書ける(怪しい)
DP 書ける
ダイクストラ 使える(ライブラリ頼み)
ワーシャルフロイド 使える(ライブラリ頼み)
クラスカル法 使える(ライブラリ頼み)
高速な素数列挙、素因数分解 使える(ライブラリ頼み)
データ構造 習熟度
set 使える
map 使える
multiset 使える(怪しい)
セグ木 使える(怪しい)
BIT 使える
遅延セグ木 使える(怪しい)
UnionFind 使える

けっこう怪しいものが多いです。うーん、よくないですね。ポジティブに捉えると、課題がある程度明確とも言えます。

やった精進と感想

これまでやった精進と感想です。時系列にはなっていないです。

APG4b (AtCoder Programming Guide for beginners)

  • C++で競プロをやると決めてから、真っ先に一通りやりました。けっこうボリュームはありますが、大切な部分が分かりやすくまとまっていて、すごくありがたかったです。
  • 最近は見返すことはほとんどないですが、1〜2 ヶ月くらいは頻繁に見返しながら問題を解いていた気がします。

典型 90（★2 ~ ★4）

  • まさに典型的なアルゴリズムやデータ構造を学べる良問ばかりな印象です。
  • ★2、★3 は自力 AC できるようになるまで解きました。3 周目ですべて自力 AC できました。
  • ★4 は 1 周しかしてません。（本当は自力 AC できるまでやりたいと思いつつ後回しで、なあなあに、、）
  • やった精進の中ではかなり効率的に力がついた感があります。

蟻本（初級編のみ）

  • 灰色のころに読んだので、かなり時間がかかりました。
  • 今思うと緑くらいまでに必要なアルゴリズムやデータ構造の網羅性が高く、とりあえず「ふーん、こんなアルゴリズムがあるのね」というのを知れたのはすごくよかったです。
  • 中級編、読まねばと思いつつ、なあなあに、、

アルゴリズム x 数学本

  • 競プロに必要な基本的な数学知識がギュッと詰まっていて、「数学無理ぃ、、」という感じの競プロ er 全員におすすめしたいです。
  • 考察テクニックも書いてあって、勉強になりました。

AtCoder Problems Recommendation

  • 最もお世話になったコンテンツです。
  • 茶色の時はひたすら moderate に出てくる問題を倒していました。本当に moderate(= そこそこ難しくて力になりそうな問題たち)な問題がバンバン出てきて、本当にすごいです。
  • 「今日疲れたなあ、、」って時は Easy からつまんで、「解けるぜひゃっほーー！！」ってやるのも結構楽しいです。
  • 自分は毎日続けるのが性に合っているので、streak を伸ばしています（執筆時点で 161 日）

バチャ（あさかつ）

  • 「コンテストで解けなかった 1 問を解けるようにするとよい」という直大さんのツイートを見て、それを早回しでやりたいと思ってはじめました。
  • 自分は「あさかつ」という朝の 7:30〜の 6 問 60 分のバチャに何回か出てました。diff は灰灰茶緑水青です。
  • バーチャルコンテストというだけあって、コンテストに似た緊張感があります。なんとなくですが、コンテストに落ち着いて取り組めるようになった気がします。
  • コンテストより短くて、1 時間という時間が個人的にちょうどよかったです。
  • 簡単な問題の早解き訓練と、難しい問題の考察訓練をいいバランスでできるのがうれしいです。

コンテスト出場(ABC)

  • コンテストはよっぽど大切な予定が無い限り出ると決めてました。理由は、長期で出続けるとレーティングに実力が反映されると考えたためです。
  • どうしても直近数回のコンテストだと、得意/不得意な問題でパフォーマンスがばらつくので、2〜3 ヶ月単位くらいで、自分のレートの変動を見るのがいいと思っています。
  • それでも、大きくレーティングを落とすと、ずーーーん、、、となって、寝るまでは引きずりますが、、、（寝たら忘れます）
  • ARCは1回だけ参加しましたが、基本的に出ない方針でした。ABCは優先参加するので、週末の夜に2回もコンテストに出るのは時間の都合上難しかったためです。また、自分の実力からするとパフォーマンスが大きくばらつくことが予想できたので、レーティングが実力に収束しにくくなるかも？とも思いました。

ACL(AtCoder Library)

  • C++ で atcoder 公式から提供されているライブラリです。C++で競プロしようと決めた時は知らなかったですが、頻出のデータ構造やアルゴリズムが簡単につかえてとても便利です。
  • 自分が使えるのは、以下です。
    • modint (一番お世話になってます！めちゃくちゃ最高です)
    • fenwicktree(コンテスト未使用)
    • segtree(コンテスト未使用)
    • lazysegtree(コンテスト未使用)
    • dsu

EDPC(Edupdational DP Contest)

  • 苦手な DP を書けるようになったのは EDPC が一番効果が合った気がします。
  • A〜E までしかやってません。
  • けんちょんさんの EDPC 解説記事にもお世話になりました。

AHC

  • アルゴリズムの精進ではないのですが、とっても楽しかったです。レートが下がらないし、WA 仕放題なので気楽に取り組めるのもうれしいです。
  • 詳しくは こちらの記事 に書きました。

お世話になった解説

C++を利用しているので、主に C++の解説記事、動画に大変お世話になりました。 特に、以下のブログと動画にお世話になりました。

  • はまやんはまやんさんのブログ
    「うー、分からない、、検索してみよ」という感じで検索すると高確率ではまやんさんが解説を書いていて、何度も何度も助けられました。
  • けんちょんさんのブログ
    解説のわかりやすさはもちろん、記事のタグがめちゃくちゃいい感じについていて、類題を探したり解いたりする時にすごく助かりました。
  • すぬけさんの公式解説動画
    公式解説、解説記事を読んでも分からない、、という時に本当に助けられました。初心者の目線で同じことでも毎回丁寧に板書しながら解説してくれるのがとてもありがたかったです。

これらの解説のコードをそのまま読めるというだけでも、「C++にしてよかったなあ」と思いました。

お世話になった Twitter

  • コンテスト後の感想戦が楽しい＆勉強になります。
  • もちろんコンテスト外のみなさまのなんやかんやのつぶやきも楽しいし、勉強になります。
  • 問題が分からない時につぶやくと、どこからともなく助けてくれる強い人が現れて的確なアドバイスをくれることがあって、すごく助かりました。
  • レートが近そうな人を見つけて、勝手にライバル認定してがんばるのもいいと思います。
  • ただし、Twitter にはとんでもなく強い人がゴロゴロいて、自分より後に始めた人が光の速さで色変していったり、ライバルだと思ってたのに瞬く間に遠くにいってしまったりします。そういう時は速攻でライバル認定解除して、心の平穏を取り戻すのが大切だと感じました。

精進について

精進について、自分はざっくり分けると以下のように捉えています。 感覚的には、後半 2 つはかなり密接に紐付いている感じがして、スッと実装ができるので、考察が浮かぶみたいな感覚です。

  • 知識をつける精進
    • 内容：いわゆる座学。まだ知らないアルゴリズムやデータ構造を学ぶ精進。
    • 精進方法：本、記事を読む。読んだ内容を書いてみる。
  • 実装力をあげる精進
    • 内容：解法が見えた時に、それを実装に落とす精進。
    • 精進方法：身につけたい解法の類題を探して、立て続けに解く。
  • 考察力をつける精進
    • 内容：本番で問題を考察して、実装の手前まで持っていくための精進
    • 精進方法：自分の色 or 1 色上の問題をノーヒントで解く。バチャとか AtCoderProblems とかでランダムに問題を解く

hamamu さんのこちらの記事にある 3 種の精進とほぼ同じですね。

コンテストの思い出

コンテストで印象に残っている回です。 DP への苦手意識が強かったので、思い出回が DP 回に集中してますね。

  • ABC237
    atcoder 再開してから、唯一の 2 完回。パフォも再開後ダントツの最低(273)でした。けっこう凹みましたが、全然力がついてないという事が自覚できてとてもよかったです。ちなみにこの問題のコーナーケース？が取れませんでした。
  • ABC240
    コンテストで初めて DP を AC した回。問題見た時はダメだ〜って思ったけど、なんとか書けてとてもうれしかったです。
  • ABC244
    初 5 完＆入緑した回。E 問題は DP。入緑もうれしかったけど、この DP が書けた方がうれしかったかも。
  • ABC247
    はじめて再帰をコンテストで書いた回（たぶん）。そして茶落ちしました。灰diffの問題ですがコンテスト中、苦労した記憶があります。
  • ABC253
    5 完 2 回目。E 問題で、その時に練習していた DP 高速化を書けてとってもうれしかったです。

やっぱり「はじめてコンテストで○○の使って解いた！」という時が、すごくうれしいです！

今後について

今後は水色タッチを目指してがんばりたいです。 現状と今後の課題は、多分こんな感じです。

  • 水色になるために明らかに不足している知識はなさそう
  • 簡単な問題の早時きがイマイチなので、C 問題まで 15 分くらいで片付けられるようにしたい。D、E にしっかり時間を残したいので。
  • D、E 問題を考察して実装に落とす力が不足している。緑 diff 後半〜水 diff の問題をたくさん(50〜100 問)くらい解く必要がありそう。
  • 実装が苦手なアルゴリズム、すぐバグらせるアルゴリズムの「型」を決めて、頭を使わずに実装できるようにした方が良い(尺取りを que で管理したりみたいな)

ただ、今年の後半は競プロ以外で取り組みたいこともあるので、精進とコンテストの参加ペースは少し落とそうかなと思っています。 なので、どの精進を優先してやるかは、また計画立てないとな〜という感じです。

結論：競プロ楽しかったので、やってよかった

競プロ、とても楽しくていい趣味見つけたな〜という感じです。

はじめは仕事に役に立つかも？と思って始めたのですが、趣味としてすごく好きです。やっぱ問題解けた時、とりわけコンテストで解けた時の「解けたーーー！！！！！」が最高に気持ちいいです。
けっこう長く続けていけそうな気がしています。

また、仕事に役に立つか？はあんまり言及したくない気もするのですが、5あくまで個人的な感想として、

  • 計算量がどれくらいになるか？
  • どう書けば処理をバグらせにくく、可読性高く書けるのか？
  • 簡単な処理をパッと書けるか？

みたいな部分が仕事で役に立ったような気がします。

だいたい書きたいことはこんなところなので、この辺で終わりにします。
最後まで読んでいただいてありがとうございます！

  1. 正確には高専の専攻科です。
    ↩

  2. 再開というのは、2019 年に 3 ヶ月ほど競プロやってすぐに辞めてしまった時期があるためです。
    ↩

  3. 転職したので、仕事でプログラムを書くようになったのは 3 年前くらいからです。
    ↩

  4. 2019 年にやっていた時は、Python でした。C++は 10 年以上前の高専の授業ですこーし書いたことある程度です。↩

  5. Twitter でこの話題になる度、割と燃えてそうだからです。↩

【初参加】AtCoder Heuristic Contest 011 参戦日記 (Sliding Tree Puzzle)

競プロ AHC

はじめてヒューリスティックコンテストに参加したので、忘れないうちに感想とやったことをまとめたいと思います。
参加時の状態はこんな感じです。

上記の通り、ヒューリスティックコンテストは初参戦で、なおかつ事前予習ゼロでした。
「とりあえず参加して、なんとなく動くアルゴリズムを提出できれば OK」
という感じで、あまり気負わず参加しました。

予習がなくて大丈夫かな？という不安もありましたが、思ったよりも雑に提出できてとっても楽しめました。
アルゴ灰〜緑くらいで「参加してみたいけど、何すればいいか分からないな、、」という人の参考になればうれしいです。

ちなみに本記事は

の 3 部構成ですので、興味のあるところを適当に読んでいただければと思います。

目次

今回の問題

A - Sliding Tree Puzzle

ざっくり言うと、

  • N*N の盤面が与えられるので、時間内に「なるべく大きい木」をつくってください

という問題です。 ここで「木」というのは、以下のようなグラフを指します。

  • 閉路がない
  • 連結である
  • 木の大きさ = 頂点数

空白マスを 1 マスずつ移動しながら, 規定の操作回数以内で木を作っていきます。
以下の動画見るとイメージが掴めると思います。

AHC011 ビジュアライザ

まず感想

いきなり感想なのですが、想像していたよりずっと楽しかったです！！！
普段はアルゴの ABC のコンテストをメインに競プロを楽しんでいるのですが、それとは違った楽しさがありました。
以下、楽しかったポイントです
（感想なんかいいから、何やったの？という方は、こちら に飛んでください）

  • 自分の書いたアルゴリズムがビジュアライザで動く
  • 最高得点がスコアになるので, 雑に提出できる
  • どんどん点数がよくなる

自分の書いたアルゴリズムがビジュアライザで動く

公式からブラウザで動作するビジュアライザが提供されているので、答えをそこに貼り付けるだけで、 ぐるぐると自分の書いたアルゴリズム通りに、マスが移動します

試しにこちらの文字列 RRRDLUULDDDDLUUUR を以下の URL の「Output」のとこに貼って、再生ボタンを押すと動く様子が分かります。
https://img.atcoder.jp/ahc011/df8bb452a2.html?lang=ja

自分が書いたプログラムの動きが目で見て分かるというのは、けっこう感動します。 はじめて動いた時はすごくテンションがあがりました！

最高得点がスコアになるので, 雑に提出できる

アルゴのコンテストだと WA や TLE するとペナルティがあって、レーティングに響きます。したがって、提出する時は慎重に動作確認が必要で、緊張感があります
一方ヒューリスティックの場合、WA や TLE してもすぐに自分のスコアが下がることはありません。最終的なスコアは、「最後の提出に対するシステムテストのスコア」のみで決まります。

つまり、最終的に AC するコードを書けてればよく、それまでは WA し放題なのです！！！やったね！！（ただし、最終提出から 30 分の提出制限があります）

そのため、「スコアよくなるか分からないけど、ちょっと実装内容変えてみた」みたいなのをガンガン試せます！ このあたりもヒューリスティックコンテストならではだな、と感じました。

どんどん点数がよくなる

取り組み方にもよると思うのですが、私の場合は、
雑な動くコードを提出する → 改善できそうなところを直す → 再提出する → 改善できそうなところを直す → ...
という感じで進めていったので、頻繁にスコアが上昇して楽しかったです。

スコアの遷移は以下のような感じです。（後半あんまり伸びてないですね、、）
5/28 14 時: 2,869,199
5/31 14 時: 5,180,532
5/31 19 時: 8,285,682
6/02 14 時: 9,485,743
6/02 19 時: 10,311,706
6/03 06 時: 11,095,544
6/03 13 時: 11,688,503
6/04 09 時: 11,903,356

感想まとめ

ヒューリスティックコンテスト初参加してみて、思っていたよりかなり参加するハードルが低いと思いました。
具体的には以下です。

  • 事前予習なし、環境構築なし（いつも競プロやる環境だけ）
  • 長期コンテストなら自分が取り組みたいタイミングで取り組める
  • レーティングが下がらないので、精神的に気楽

楽しかった点ばかりでも微妙なので、ヒューリスティックコンテストで個人的なデメリットを挙げるとすると以下です。（本当は無いですが、無理やり挙げてみます）

  • 参加中は解法に関する言及が一切できないので、ムズムズする（Twitter 見ると、なんだかムズムズしてます笑）
  • 長期だと無限にやることが湧いてくるので、時間を溶かしすぎる
  • アルゴの精進時間をヒューリスティックにあてなきゃいけないので、次回の ABC がちょっと不安

けっこう参加ハードル低いと思うので、気になっている方はぜひ次回一緒に参加して楽しみましょう！！

実装内容の解説

ここからは実際にやったことの解説です。
言語は C++です。

おおまか方針としては、「ランダムに盤面を探索して、大きい木の盤面を残していく」という感じです。
アルゴリズム分類的には「乱択」＋「山登り」になるのかな？（詳しくないので、間違ってるかもです、、）
ざっくり以下となります。

  1. 評価関数を用意しておく
  2. 盤面をランダムに探索する
  3. 盤面のランダム探索を繰り返しながら、徐々に木を大きくしていく

以下は上記を図にしたものです。

探索1回目

探索2回目

1. 評価関数を用意しておく

まず問題を解くにあたって現在のスコア(= 木のサイズ)を測定できる必要があります。
いくつかやり方があると思いますが、今回は UnionFind で実装しました。

  • UnionFind で接続できるマスを併合する
  • 併合する時に閉路があれば, スコア無しにする

また、盤面は問題文の通りに 1 マスを 4bit で表現しています。

マスとbitの対応関係（AHC011 問題文より引用）

実装は以下です。

// マス目は4ビットで持つ
using bs = bitset<4>;

/**
 * @brief 盤面を受け取って, 最大の木を返す
 *
 * @param bits 判定する盤面
 * @return vector<int> 最大の木のマス目の集合
 */
vector<int> get_max_size(vector<bs> bits) {
  dsu uf(n * n);                         // 連結・閉路判定用
  vector<bool> is_cyclic(n * n, false);  // ufの親を閉路かマーク

  // 右と下だけ見ていく (盤面外に注意)
  vector<int> dx = {1, 0};
  vector<int> dy = {0, 1};
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int idx = (i * n) + j;  // 現在の位置
      for (int k = 0; k < 2; k++) {
        int nx = i + dx[k];
        int ny = j + dy[k];
        int nidx = (nx * n) + ny;  // 次の位置
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        // 下
        if (k == 0 && (bits[idx] & bs(0b1000)) != bs(0b0000) &&
            (bits[nidx] & bs(0b0010)) != bs(0b0000)) {
          // 閉路判定
          if (uf.same(idx, nidx)) {
            is_cyclic[uf.leader(idx)] = true;
            is_cyclic[uf.leader(nidx)] = true;
          }
          // 併合
          uf.merge(idx, nidx);
        }
        // 右
        if (k == 1 && (bits[idx] & bs(0b0100)) != bs(0b0000) &&
            (bits[nidx] & bs(0b0001)) != bs(0b0000)) {
          // 閉路判定
          if (uf.same(idx, nidx)) {
            is_cyclic[uf.leader(idx)] = true;
            is_cyclic[uf.leader(nidx)] = true;
          }
          // 併合
          uf.merge(idx, nidx);
        }
      }
    }
  }

  // 最大の木の要素集合を返す
  int ans_len = 0;  // 木のサイズ
  vector<int> ans_vec;

  for (auto vec : uf.groups()) {
    // 閉路があれば, スコア無し
    int root = uf.leader(vec.front());
    if (is_cyclic[root]) continue;
    // 最大の木を更新
    if (chmax(ans_len, (int)vec.size())) {
      ans_vec = vec;
    }
  }

  return ans_vec;
}

2. 盤面をランダムに探索する

評価関数ができたら, いよいよランダムに盤面を探索します
おおまかなアルゴリズムは以下です

  1. 上下左右 4 方向のうち, 次に移動する方向をランダムに決める
  2. 実際に動かしてスコアを計算
  3. もし最大スコアなら, 現在の {スコア, 移動経路, 現在の盤面} を保持しておく

以下、いくつか工夫した内容です。

前の位置には戻らないようにする

ランダムだけど、なるべく効率よく探索したいので、自分が前にいた位置には戻らないようにしました。
前の位置に戻ってしまうと、移動回数は増えるのに、盤面は全く変わらないためです。

ひとつ前には戻らない

確定した盤面には到達できないようにする

すでに確定した盤面に対しても、移動を禁止しました。すでに確定した盤面よりも大きな盤面にしていくためです。

確定しているマスは探索しない

同じ場所から動けなくなったら探索を打ち切る

  • 前の位置には戻らないようにする
  • 確定した盤面には到達できないようにする

この２つの制約によって、同じ場所から動けなくなることがあります。
そのため、同じ場所から動けない場合は探索打ち切りとしました。

動けなくなったら、探索を打ち切る

壁面のところはいつでも通れるようにしておく

確定した盤面には到達できないようにすると、空きマスが狭いエリアに閉じ込められることがあります。
そのため、壁際のエリアは常に探索を許可することにしました。

壁際のみを許可としたのは、以下の理由です。

  • 実装が簡単
  • 壁際のみなので、ランダムに動くよりは木のサイズを小さくしない

壁面は常に探索OKにする

というわけで、実装は以下となります。

/**
 * @brief ランダム探索の結果
 *
 */
struct Result {
  int score;             // 木のサイズ
  string moving;         // 移動経路
  vector<char> ng_grid;  // 最大の木の位置をマークした盤面
};

/**
 * @brief 空きマスをランダムに動かして, なるべく大きな木をつくる
 *
 * @param bits 探索する盤面. 最終的に最も大きい木をつくれる盤面に変更する
 * @param x_ini 空きマスの初期 x座標
 * @param y_ini 空きマスの初期 y座標
 * @param ng_grid 確定済みの盤面
 * @return Result
 */
Result random_seach(vector<bs> &bits, int x_ini, int y_ini,
                    vector<char> ng_grid) {
  string moved;                        // 移動経路
  auto max_tree = get_max_size(bits);  // 最大の木
  int score = max_tree.size();         // 最大の木の大きさ
  int max_cnt = 0;             // 最高値を記録した時の, 移動回数
  int move_cnt = 0;            // 移動回数
  int px = IINF, py = IINF;    // 一つ前の位置
  int x = x_ini, y = y_ini;    // 現在の位置
  vector<bs> bits_max = bits;  // 最大スコアの盤面
  vector<char> ng_grid_max = ng_grid;  // 最大スコアの探索NG盤面
  int loop = 0;       // 同じ場所をぐるぐるしているかを判定
  int limit = t / 2;  // 探索回数の上限

  // 適当にたくさん探索する
  while (move_cnt <= limit) {
    loop++;
    // 適当に進む
    int next = get_random(0, 3);
    int nx = x + dx[next];
    int ny = y + dy[next];
    int nidx = (nx * n) + ny;  // 次の位置
    int idx = (x * n) + y;     // 現在の位置

    // もう1回進むところガチャ
    if (loop > 20) break;  // 同じ場所から抜け出せなくなっている
    if (px == nx && py == ny) continue;  // 前と同じ位置には戻らない
    if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;  // 盤面外
    if (ng_grid[nidx] == '#') continue;                    // 確定済み
    loop = 0;  // 動けるので, loopを初期化

    // 移動を記録
    moved.push_back(dir[next]);

    // 入れ替えてスコアを計算
    move_cnt++;
    swap(bits[idx], bits[nidx]);
    auto tmp_tree = get_max_size(bits);
    auto tmp_ng_grid = make_char_grid(n, tmp_tree);
    int tmp_score = tmp_tree.size();
    if (chmax(score, tmp_score)) {
      if (move_cnt > t) break;  // 操作回数はtを超えないようにする
      max_cnt = move_cnt;       // 移動回数
      bits_max = bits;          // 最大スコアの盤面
      ng_grid_max = tmp_ng_grid;  // 最大スコアの探索NG盤面
    }

    // 位置を記憶
    px = x, py = y;  // 一つ前の位置
    x = nx, y = ny;  // 現在の位置
  }

  // 最大スコアの盤面に戻す
  bits = bits_max;

  // {スコア, 移動経路, 現在の盤面}
  return {score, moved.substr(0, max_cnt), ng_grid_max};
}

3. 盤面のランダム探索を繰り返しながら、徐々に木を大きくしていく

ここまでで盤面のランダム探索ができるようになったので、あとはそれを適当に繰り返していくだけです。
以下の手順で徐々に木を大きくします。

  • ランダム探索を 50 セットくらい繰り返して, 一番大きな木の盤面を探す
  • 一番大きな木の盤面を初期盤面として, またランダム探索をする(すでにできた木のマスへは移動不可とする)
  • 上記を 10 セットくらい繰り返して、徐々に木を大きくする

これを1セットとして、10セットくらい繰り返す

実装はこちらです。

int main() {
  // デバッグ用
  ifstream in("input.txt");
  if (in.is_open()) {
    cin.rdbuf(in.rdbuf());
  }

  // 入力
  cin >> n >> t;
  vector<string> s(n);
  for (int i = 0; i < n; i++) cin >> s[i];

  // 探索する盤面初期化
  vector<bs> bits_now = convert_bit_vector(s);  // 入力をbitsetに変換
  vector<char> ng_grid_now = make_char_grid(n, vector<int>());  // 探索NG判定用

  // 探索回数の設定. 数値は動作見ながら微調整
  int limit = floor(5 * (2000.0 / t));  // 同じ盤面を探索する回数
  int d = 10;                           // 探索する深さ

  // 最終的な答え
  string ans;         // 最終的な移動経路
  int ans_score = 0;  // 最終スコア

  // 盤面を確定させながら, いいスコアを探す
  for (size_t i = 0; i < d; i++) {
    // 初期化
    auto [x_ini, y_ini] = get_blank_position(bits_now);  // 空きマスの初期位置
    int max_score = 0;                                   // 最大スコア
    string max_moving = "";     // 最大スコア時の経路
    vector<bs> bits_next;       // 次に探索する盤面
    vector<char> ng_grid_next;  // 次に探索する際の確定済み盤面

    // 同じ盤面をなるべくたくさん探索する
    for (int j = 0; j < limit; j++) {
      // 盤面初期化 (毎回同じ盤面からスタート)
      vector<bs> bits = bits_now;
      vector<char> ng_grid = ng_grid_now;

      // 探索
      auto [score, moving, ng_grid_res] =
          random_seach(bits, x_ini, y_ini, ng_grid);

      // 最大値更新
      if (chmax(max_score, score)) {
        max_moving = moving;  // 移動経路更新
        bits_next = bits;  // 最もいい盤面を, 次のスタート盤面にする
        ng_grid_next = ng_grid_res;
        ans_score = max(ans_score, max_score);
      }
    }

    // 次に探索する盤面をセット
    if (!bits_next.empty()) {
      if (ans.size() + max_moving.size() <= t) {
        ans = ans + max_moving;
        bits_now = bits_next;
        ng_grid_now = ng_grid_next;
      } else {
        break;
      }
    }
  }

  cout << ans << endl;
}

最終的なコード

以下となりました。最終提出はデバッグ用のコメントなど入っているので、より一層読みづらいです m(_ _)m
ちょっとだけ読みやすくした ver.もあるので、そちらを見てもらった方がいいかもです。

日記

最後に最終コードに至るまでツイート＋日記をつらつら書きます。 本当にただの日記なので、ゆるーく読んで頂けると幸いです。

2022/05/28

とりあえず問題文を読む。 うっ、なんか難しそうだけど、1 週間あれば何かしら書けそうかも。 そして、ゆっくりスコアの計算式を眺める。。。うん？これは何もしなくてもスコアもらえるじゃん！

というわけで提出！！

記念すべき初得点。なんにも実装してないけど、得点取れてとってもうれしかった。

2022/05/30

アルゴの精進も続けたい気持ちもあったので、こんな感じで取り組むことに決定

そして、全然方針が決まらず書き始められなかったので、思いつく限り簡単な方針で書くことに決定。
真っ先に思い浮かんだのが、ランダムに空きマスを動かして、一番大きい木の盤面で止める方針。
結果的にこれがほぼそのまま今回の最終方針になった。

2022/05/31

はじめて自分の書いたプログラムでビジュアライザを動かす。めっちゃうれしい！

この日はもう 1 回提出してさらにスコアアップ！
この時点では「時間いっぱいランダムに盤面を探索して, 一番大きな木を出力」というシンプルなアルゴリズムだった。

2022/06/01

コードの量が増えてきて辛くなってきている。

流石にこれ以上は無理と判断して、mainのランダムに探索するところを関数に切り出す作業を実施。 main 関数の見通しがかなりよくなったので、実装＆実験しやすくなった。

2022/06/02

バグ取り、けっこう大変。

ここで「あっ！木の閉路判定してないじゃん！！」に気づく。スコアがめっちゃ伸びるのでは？とワクワクし始める（なお、たいして伸びなかった、、）

10M 突破して、かなりうれしくなってる。
ここで、ランダム探索に加えて、確定した盤面を徐々に大きくする実装を取り入れる。

2022/06/03

だんだんと AHC 沼にハマる様子が分かる

ここで、最初に選んだ盤面が、大きくなりにくい盤面だとスコアが伸びないことに気がつく。 今までの処理をまるまる 2 回分やって、良い方を取る実装を取り入れて、スコアちょい伸び。

2022/06/04

探索回数を少しいじって微増。ここで今回の AHC は切り上げ。

2022/06/05

システムテストなるものがあることを知って、それが最終提出で走ることに焦る。 問題文をちゃんと読むの大切です、、（システムテストは 3 つほど TLE したけど、無事でした）

最後に

かなり長くなってしまいましたが、最後まで読んで頂いてありがとうございます。 参加迷っている方がいれば、次回はぜひAHCをワイワイ一緒に楽しめるとうれしいです！