入黄するためのABCの戦い方

コンテストで2300以上のパフォーマンスを取ると、謎の力によりコンテストがUnratedになる確率が高まります。

コンテストでは2300をギリギリで超えないようなパフォーマンスを取るようにしましょう。

参考までに、私が入黄したコンテストでのパフォーマンスは2287でした。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

？？？

 

 

真面目な記事

気が向いたら書きます

AtCoderで青色になりました

AtCoderで青色になりました！わーー！！！

青色は始めたときからの目標だったので、到達できて一つ区切りがついたな、という手応えでちょっとホッとしています。 ここ最近は手が空くたびにAtCoderのプロフを眺めてはにやにやしています、えへへへ……

自分の中で一つ区切りがついた、ということもあり、 このタイミングでこれまでどういうことをやったのか、や、思い出をまとめていきたいと思い記事を書くことにしました。 どちらかというと自分なりの整理のための文章のような内容で、 「これをすれば入青できます！」という類のものではないのであしからず。。。

誰？

atcoder.jp

twitter.com

柑橘類です。ｽｯﾊﾟｲﾖ-
Twitterでよく騒いでいます。うるさいです。あと定期的にポエムを詠みます。

AtCoderは2022年の6月頃から始めています。競技プログラミングも本格的にやったのはその時期から…ではあるのですが、実はpaizaの存在は以前から知っており、A問題くらいまでなら全然解けるくらいにはやりこんでいました。 そういう意味では開始時点で完全に初心者だったか、と言われると若干アヤしい感じで、体感茶色中位くらいはあったと思います。

2020年に博士課程を中退し、ITコンサル的なお仕事を2年半したあと、現職はお世話になっていた人の会社で開発もどきのようなことをしています。最近はTypeScriptやRubyを書いていることが多いです。

研究室は物理専攻（半導体光物性）でした……が、実は大学院後半は物理よりも情報や数理最適化の方に興味があり、自分の研究に関連する範囲でそのあたりをいじくりまわしていました。 （指導教官からは「いつ実験するの？」と弄り倒されていました。でも、好きにやらせてもらえていたことはとても幸せな環境だったと思っています）

AtCoderでは主にC++を使っています。元々はPythonだったのですが、典型90の043 - Maze Challenge with Lack of Sleep（★4）でどうしてもPythonのDijkstra解が通せず、そこからC++に転向しています。

入青するまでにやったこと（精進周り）

精進

周囲で色変している人を見ると精進量は結構まちまちですが、私はまあまあ平均的な方だと思います。

眺めてみると緑＆水が同数くらい、青がその半分くらい、黄以上はほとんど解いていない、という感じです。 実際気合を入れて精進をしたこと、というのはあまりなく、どちらかというと後で書いているバチャ荒らしなどの流れで解いているものがほとんどだと思います。

バチャ荒らし

と私が勝手に呼んでいますが、要は人様の立てたバチャに勝手に参入して問題を解きます。 結構バチャに飢えているときは、茶色の人が立てている緑精進とかのバチャに勝手に参加して1stを取っていったりします。最悪ですね。

こう、特にやりたい問題がなくて暇なときとかに「誰かと一緒に問題に向き合っている」という感覚が好きでバチャには結構な頻度で参加しているとおもいます。 最近ではburiodenさん主催のABCDバチャとか、あとはTwitterで「〇〇時からバチャやるよー」という募集を見かけると 参加することが多い気がします。

まよコン

前述のバチャ荒らしの一環ではあるのですが、ちょっとこれに関しては特筆したいので章を分けています。

まよコンは、まよ🌽さん主催のバチャでABCなどが無い日の21:00～のバチャです。 バチャの中でもまよコンには結構前から参加していて、競プロを初めて2ヶ月くらいの8月頃から、それなりの頻度で出ていました。

個人的に問題セットがABCライク（というかABCの問題しか出ない）で、時間的にまあまあ出やすいのもあってかなり楽しくやらせてもらっています。 上のバチャ荒らしもそうですが、問題に多く触れる機会が作れることと、解説まで読んではいるけれど実装が面倒でやっていない、や、前に書いたときに死ぬほどバグらせた、 みたいな問題を解き直すいい機会になったりもするので、その点はすごくいいな、と思っています。

精進周りはもうちょっと書いていくのですが、個人的に色変に一番効いていると感じるのはまよコン含めたバチャへの参加だと思っています。

典型90・精選100問

競プロerには言わずとしれたこれとこれですね。

典型90の方は昔★5までは埋めたのですが、ちょっと最近サボりがちで★6は2,3ヶ月積んでいます。。。行列掃出しとGrundy数が重いんです。。。

精選100問は緑くらいのときにめちゃくちゃやる気になって、98/100を一気に埋めました。 これはやはりさすが選りすぐりのコンテンツ、と言った感じで、水色までの典型を一通り押さえる、脳死で書けるようにする、という意味でめちゃくちゃに役に立ったと思っています。 ちなみに埋めていない2問はABC149F - Surrounded Nodes（黄diff）と釘（JOI難易度7）です。重い。。。

入青するまでにやったこと（コミュニティ関連）

VRC競プロ部

テッド/妹尾@VRC競プロ部さん主催の、VRChat内で競プロの話をするグループです。 毎ABC後に23時から感想会を行って、解法や考え方の共有や、やんややんや喋ったりしています。

終わった後に解説をみんなで勉強できる、という点と、やはり同じ趣味の人が集まるコミュニティという意味でモチベーション維持にかなり効いている気がします。

こうやって見ると結構競プロ関係のイベントやコミュニティに色々参加しているんだな、という感覚です。自分的にはひっそりやっているつもりだったのですが。

ちなみに、ABCがない日にも競プロ以外で遊んでもらったりもしています。えへへへへ

夏を壊す会 with 競プロ部のみなさん

Twitter

多分この記事を見ている人には言わずもがなですが、Twitterでの交流も競プロのモチベーション維持に結構効いていると思っています。 近しいレートの人が「〇〇の問題といたよ！」というような話をしていると、自分も解いてみようかなーという気になったり、 他の人の提出コードを見てこんな書き方あるんだーと勉強になったり、色変にあたって一定の効果があったように感じます。

私のTwitterアカウント自体は競プロを始める前からあるのですが、ほぼ使ってない状態だったのでフォロー／フォロワーはほとんど競プロ関係です。 ので、TLはほとんど常に競プロの話題、という感じなので、そういう意味でも良いのかもしれません。

思い出深い問題

せっかくの機会なので、結構記憶に残っている問題を紹介しようと思います。みんなも解こうね。。。

コンテスト参加2回目、初めて「アルゴリズム」というものに触れた問題でした。 Cを通した後40分くらい考えてどうしても解けず、解説を見てとても驚いた記憶があります。

これに殺されてから、アルゴリズムを学ぶのが楽しくなって精進などを結構やるようになったと記憶しています。

ARC2回目参加C問題、人生で初めて通した青diffでもあります。 コンテスト中めちゃくちゃ考えて、解法を見つけて、実際にACと出たときにものすごく嬉しかったのが今でも覚えています。

個人的にはABCよりもARCの方が勝てるイメージが有り、それもあってARCの問題にはいい思い出が多いような気がします。

入青を決めた問題です。

ただ、実はこの回、Predictorの表示が実際のPerfよりもかなり低く表示されていて、通した時点では水パフォ、入青はしないように見えていました。 そのため、終わった後ももう一週お預けか。。。と思っていたのですが、更新が来たあとで入青していてそういう意味でもかなり印象的な入青でした。

問題としてもかなり面白い問題で大好きな問題の一つです。

雑記

こうやって振り返ってみると、競プロはひっそりやっているイメージでしたが意外と交流やコミュニティにも顔を出していたんだなあと実感しました。 バチャや精進で一緒に遊んでくれる人にはいつも感謝です。。。

青色にはなりましたが、もっともっといろんな問題も解きたい、強い人達といっぱい勝負したい気持ちは強いので、 黄色、更にはもっと上の色は目指していきたいです。次の色辺記事は何年後かなぁ・・・

あとは、ちょっと前に話題になった、レート近い人とお互いに問題出し合うやつとかもやりたいですね。 具体的にはhighestが同じくらいの某羊さんとか。どうですか。

？？？

実はVRC競プロ部に入ってからVRCで色んなワールド回るのが楽しくなってしまってハマってしまいました、、、 結構きれいなワールドが多いので写真とかとるのが楽しいんですよね、、、

青になったら多少載せてもいいはず。。。と甘えていろいろ載せちゃいます。みんなもVRC…しよう……！

1WAがとれない……ときのランダムテストのすゝめ


本記事には以下の問題のネタバレが含まれます。

ABC267 D: Index × A(Not Continuous ver.)

atcoder.jp

背景

競プロで、コード書いて、サンプルも全て通して自信を持って提出！……したのですが、テストケースで1つだけWAしてしまう……競プロerなら誰でも経験したことがあると思います。
すぐにバグの箇所が見つかれば良いのですが、クサいところを直して再提出したもののまたWAを出して順位を大きく落としてしまったり、コンテスト中にバグ箇所がわからずそのまま終了、なんてこともあると思います。
この記事では、そういった場合に役立つ「ランダムテスト」について解説します。

TL;DR

  • サンプルは全部通るのにWAが出てしまう場合、ランダムな入力データでテストを行うことで落ちるテストケースを見つけられることがある
  • 手順は以下の通り
    • ブルートフォース解法コードと、ランダム入力生成用のコードを作成する
    • これらを使ってランダムな入力を生成し、ブルートフォース解法で出力を生成
    • 生成したランダムなテストケースで元のコードをテストする
  • メリット
    • 落とせるケースを機械的に発見できる
  • デメリット
    • ランダムケース生成・総当り解法の作成にそこそこ時間がかかる
    • 適用限界があるので、全てのバグに対して落とせるテストケースが見つかるわけではない

例題

今回は、以下の問題を例に解説します。 atcoder.jp

i 番目 A_i まで見てそのうち j 個を選ぶような部分列のうち、答えに効いてくるのはその中で最もindex × Aの値が大きい部分列のみです。
なので、そのような部分列のindex × Aの値をメモしながらDPしていけば解くことができそうです。

ということで、その通り実装してみます。

Submission #35364750 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267) （WA）

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using vl = vector<ll>; using vvl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < n; i++)
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; }

int main() {
    int n,m;
    cin >> n >> m;
    vl a(n);
    rep(i, n) cin >> a[i];
    vvl dp(n+1, vl(m+1, -1));
    dp[0][0] = 0;
    rep(i, n) rep(j, m+1) {
        if (dp[i][j] == -1) continue;
        chmax(dp[i+1][j], dp[i][j]);
        if (j != m) chmax(dp[i+1][j+1], dp[i][j] + a[i] * (j+1));
    }
    cout << dp[n][m] << endl;
}

上記のコードでサンプルは通っているのですが、提出してみると半分くらいWAしています。

ランダムテスト用コードの作成

この問題に対して、ランダムテストでバグ箇所を発見していきます。必要なものは以下の2つです。

  • 元の問題に対するブルートフォース（総当り）解法コード
  • ランダムケース作成用のコード

それぞれ作っていきます。

ブルートフォース（BF, 総当り）解法コード

「計算量を度外視して元の問題を解くためのコード」です。 O(N ^3) でも O(N!) でも O(2 ^N) でも、とりあえず解ければ何でも良いです。 今回の問題では部分列を全て列挙する自明な O(2 ^N N) 解法があるため、これを実装します。

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using vl = vector<ll>; using vvl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < n; i++)
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; }

int main() {
    int n,m;
    cin >> n >> m;
    vl a(n);
    rep(i, n) cin >> a[i];
    ll ans = -1e10;
    rep(i, 1 << n) {
        if (__popcount(i) != m) continue;
        int count = 1;
        ll cur = 0;
        rep(j, n) {
            if ((i >> j) & 1) {
                cur += count * a[j];
                count++;
            }
        }
        chmax(ans, cur);
    }
    cout << ans << endl;
}

ランダムケース作成用コード

次に、テストケースをランダムで生成するコードを作成します。 これは、問題文の入出力形式と、先ほど作ったBF解法の計算量を見ながら作成します。 今回は 2 ^Nくらいの解法なので 1 \le M \le N \le 10くらいで作成すると良さそうです。
また、 A_i の範囲については特に計算量の縛りは無いですが、あまり数が大きいと後で落とせるケースが見つかったあとのデバッグが大変なので、そこまで大きくない範囲（ -10 \le A_i \le 10 くらい）にしておきます。

import random

n = random.randint(1, 10)
m = random.randint(1, n)
print(n, m)
a = [random.randint(-10, 10) for i in range(n)]
print(*a)

なお、自分はランダムケース作成用のコードはPythonで書いています。
これは、書いたものをコンパイルせずにさっと実行したいことと、順列の並べ替え（numpy）や木のテストケース作成（networkx）など、使えるパッケージが豊富なことが理由です。

ランダムテスト実施

2つのコードが書けたらランダムテストを実施します。これは各々の競プロ用のテスト環境などによるのでそれに合わせれば良いですが、例えば私の場合はonline-judge-toolを導入しているので、以下のようなフォルダ構成にしてコマンドを実行します。

cases/
└d/
  └test/
  └answer.cpp
  └answer_bf.cpp（総当り解法コード）
gen_rand.py（ランダムケース作成用コード）

ランダムケース作成（100個）

oj g/i -d "cases/d/test" "python gen_rand.py" 100

ランダムケースの出力作成

cd cases/d
g++ answer_bf.cpp
oj g/o -c "./a.out" -d "test"

これでランダムケースとそれに対する出力が生成されるため、あとは通常のサンプルと同じようにテストをすればOKです。私の場合はこれもonline judge toolで実施します。

oj t -d "cases/d/test" -c "./cases/d/a.out"

テスト結果の確認とエラー箇所の修正

テストをするとWAしているケースが見つかります。例えば、以下のようなケースで落ちていそうです。

[input]
1 1
-5

[output]
-1

[expected]
-5

-5だけの数列なのに-1が出力されるのはおかしいです。どこからこの-1が出てきているのか。。。と元のコードを眺めてみると、DP配列を-1で初期化してしまっていることが分かります。 したがって、初期化を-1ではなく-1e16などにすることで元の問題をACすることができます。 ACコード

10/4追記

oj g/iで--hackオプションを使うことで、落とせるケースだけを簡単に見つけることができます。
上のフォルダ構成では、例えば以下のようなコマンドで実行します。

cd cases/d
g++ answer.cpp -o a.out
g++ answer_bf.cpp -o naive
cd ../../
oj g/i --hack-actual ./cases/d/a.out --hack-expected ./cases/d/naive "python gen_rand.py" 5

指定した個数分（今回は5個）、元のコードとBF解法の出力に差がある入力が出現するまでランダム生成を実行して、それをtest/フォルダ配下に保存してくれます。

適用限界

ランダムテストの実施により「ランダムなケースに対して一定の確率で発生しうるバグ」については発見できることがあります。
しかし、逆に言うとそのような性質を持たないバグについてはランダムテストで発見することはできません。具体的には例えば、

  • 制約の境界付近(N=0, N=1など)で発生するコーナーケースへの対応不足
  • 制約の大きいところで発生するオーバーフロー（計算量の関係で、大きい数字でのランダムテストができないため）

などは発見することができないため、これらはコードを良く見返したり、元のコードにデバッグ出力を埋め込んだりして発見する必要があります。

まとめ

ランダムテストを使うことでWAがずっと取れない…と悩むことは一定数減るかと思います。
ただし、上述の通り万能ではないので、ランダムテストで発見できないようなバグを埋め込んでしまった場合は地道なデバッグの経験が効いてきます。
ランダムテストできるから、と甘えずに精進しましょう……

個人的DFS、BFS書くときにに気をつけてることまとめ

背景

ABC270でDFS・BFS（じゃなくても解けますが）の問題が出ました。 atcoder.jp

他の人のコードとか見ながら、結構みんな書き方まちまちなんだなーと思いつつ、個人的にバグらせないように気にしていることをまとめておこうと思い記事にしました。

この記事で触れないこと

DFS・BFS自体にはこの記事では触れません。これら自体については以下の記事などが良いと思います。

qiita.com

qiita.com

BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 - Qiita

TL;DR

共通

  • 書き方をテンプレート化しておいて、考えることを減らす

DFS

  • コード書く量が減る（はず）なので、再帰で実装
  • 再帰関数はほとんどの場合でローカル変数を参照したいので、lambda式で書く
  • 行きがけ順の処理と帰りがけ順の処理を書く場所を決めておいて、やりたい処理をそこに書く

BFS

  • そもそもあんまり書かない（再帰のほうが楽）
  • 訪問済みのマーク・判定はループの最初に入れる（これは諸説あり）

定義済みマクロとか

#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repe(a, v) for(auto& a : (v)) // v の全要素（変更可能）
template <class T> inline ostream& operator<<(ostream& os, vector<T>& v) {
    rep(i, sz(v)) {
        os << v.at(i);
        if (i != sz(v) - 1) os << " ";
    }
    return os;
}

その他、Graph型を定義しています。ライブラリ自体は以下に置いてますが、とりあえず隣接リストっぽくg[i]で隣接するノードを繰り返せると思っておけばよいです。

github.com

DFS

DFSを書くと決めた時点で、とりあえず脳死で以下まで書いてしまいます。（変数名とかは適宜変えます）

DFS（テンプレート）
Graph g;  // 適当に初期化
int s = 0;  // 最初の点
vb seen(n, false);
auto dfs = [&] (auto self, int x) {
    if (seen[x]) return;
    seen[x] = true;
    /* 行きがけ順にしたい処理を書く */
    repe(e, g[x]) {
        self(self, e.to);
    }
    /* 帰りがけ順にしたい処理を書く */
};
dfs(dfs, s);

lambda式にするのは、Global領域に変数をセットしに行くのがめんどくさいからです。

あとは、行きがけ順に処理したい内容と帰りがけ順に処理したい内容を考えて、それぞれコメントした箇所に書きます。 逆にここ以外をいじることはほとんどしないです。（ついでにここ以外をいじる場合は、大抵自分はどこかをバグらせます）

書き方がかなりテンプレート化されているのでマクロや関数テンプレートで書けるかなーと思いつつ、地味にやりたいことが多岐にわたることと、上くらいであれば毎回書いてもそこまで時間かからないので、自分はテンプレートにはしていないです。エディタのスニペットとかには入れてもいいかなーとは思っています。

この書き方で、ABC270-Cを解くと以下のような感じです。

DFS（ABC270-C）
vi ans;
vb seen(n, false);
auto dfs = [&] (auto self, int xi) {
    if (seen[xi]) return;
    seen[xi] = true;
    /* 行きがけ順処理ここから */
    ans.push_back(xi + 1);
    if (xi == y) {
        cout << ans << endl;
        return;
    }
    /* 行きがけ順処理ここまで */
    repe(e, g[xi]) {
        self(self, e.to);
    }
    /* 帰りがけ順処理ここから */
    ans.pop_back();
    /* 帰りがけ順処理ここまで */
};
dfs(dfs, x);

atcoder.jp

ちなみに自分のDFSの書き方は以下の記事に多分に影響を受けています。 blog.knshnb.com

BFS

これもDFSと同じ感じで、とりあえずBFSと決めたら以下まで書いてしまいます。

BFS（テンプレート）
Graph g;  // 適当に初期化
int s = 0;  // 最初の点
deque<int> q;
q.push_back(x);
vb seen(n, false);
while(!q.empty()) {
    int x = q.front();
    q.pop_front();
    if (seen[x]) continue;
    seen[x] = true;
    /* やりたい処理 */
    repe(e, g[x]) {
        q.push_back(e.to);
    }
}

あとはやりたい処理を考えて埋めるだけです。

なお、自分は訪問済みの判定は、Queueの追加のタイミングではなく、必ず繰り返しの最初に置くことにしています。これは、昔以下のように書いてよくバグらせていたからです。

BFS（バグ例）
while(!q.empty()) {
    int x = q.front();
    q.pop_front();
    seen[x] = true;
    /* やりたい処理① */
    repe(e, g[x]) {
        if (!seen[e.to]) q.push_back(e.to);  // Queueの追加時に判定し、訪問済みのマークは処理時にすると、無駄な遷移が増えTLEする
    }
}

訪問済みチェックのタイミングとマークのタイミングが同じであればいいので、Queueの追加のときにマークする、でもいいのですが、とりあえず考えることを減らすために、自分は「ループの最初で訪問済みチェックとマークを両方する」をルール化しています。

これをベースにBFSでABC270-Cを解くと以下のような感じです。 直前のノードを残しておくために、Queueの中身をpair<int, int>に改造しています。

BFS（ABC270-C）
vi prev(n, -1);
deque<pair<int, int>> q;
q.emplace_back(x, -1);
vb seen(n, false);
while(!q.empty()) {
    auto [x, par] = q.front();
    q.pop_front();
    if (seen[x]) continue;
    seen[x] = true;
    prev[x] = par;
    repe(e, g[x]) {
        q.emplace_back(e.to, x);
    }
}

vi ans; int current = y;
while (current != x) {
    ans.push_back(current + 1);
    current = prev[current];
}
ans.push_back(x + 1);
reverse(all(ans));
cout << ans << endl;

atcoder.jp

BFSはなんやかんやで、書いているとコードが長くなってくることが多い印象なので、どっちでもいいならDFSの方をよく書きます。

まとめ

書き方は人によりけりだとは思いますが、自分なりに「こう書けばバグらせない」みたいなテンプレートを持っておくことで、変なバグに悩まされることはなくなると思います。コンテスト中にえぐえぐ泣きながらデバッグして時間を溶かすのはしんどいので、バグらせないように書きましょう。。。

メモ化DPするときは必ず値を更新しようというお話

考えてみれば当然だけど、何回かやらかしているので自戒を込めて 本記事には以下の問題のネタバレが含まれます。

競プロ典型90問 45日目 Simple Grouping（★6）

TL; DR

  • メモ化再帰で初期値から更新されない値がある場合、メモ化配列を探索済みとして更新する処理を入れる。

例題

競プロ典型90問 45日目 Simple Grouping（★6）

ユークリッド平面上に、N個の点 (X1, Y1), (X2, Y2), ⋯, (XN ,YN)があります。 これらを、次の条件を満たすようにK個のグループに分けることを考えます。
・複数のグループに入る点があってはならない。
・どのグループにも属さない点があってはならない。
・ひとつも点が属さないグループがあってはならない。
このとき、同一グループ内での2点間距離の最大値を最小化してください。 ただし、ジャッジにはこのときの同一グループ内での2点間距離の最大値の2乗を出力してください。
なお、このときの最大値を2乗した値は必ず整数になることが証明できます。

解法

方針

点の集合としてN個の点のある部分集合をとり、グループ数Kを1減らした小問題を考えます。 このような全ての小問題について、その解と「選ばなかった点」を1グループとしたときのグループ内の２点間距離の最大値を考えると、元の問題を解くことができます。 また、K=1については、全ての点同士の距離を求めることで解くことができるので、上の操作を再帰的に繰り返すことで元の問題を解くことができます。

計算量

bit DPをメモ化再帰で実装すると、状態の数が2^ N K 、状態間の遷移は各部分集合の部分集合の数で O(2^ N) なので、ぱっと見 O(4^ N K) \simeq 10^ {10} くらいで間に合わなそうです。 ただ、実際には部分集合のサイズが小さくなればそれに応じてその部分集合の数も少なくなるので、さぼって 2^ N \times 2^ Nとしている部分を真面目に計算すると、

\sum_{k=0}^ N {}_N C_k 2^ k = 3^N

となり、 O(3^ NK) \simeq 2 * 10^ 8でなんとか間に合います。 上記の導出はO(3N)で部分集合の列挙をする実装を参照しました。

実装

というわけで、とりあえず実装します。

実装例 (TLE)

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

// テンプレート、マクロ
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
using ll = long long; ll INFL = 3300300300300300491LL;
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）

template<class T> T euclid_square(pair<T, T> s, pair<T, T> t) {
    auto square = [](T a) {return a*a;};
    return square(s.first - t.first) + square(s.second - t.second);
};

int main() {
    // 入力
    int n,k;
    cin >> n >> k;
    vector<pair<ll, ll>> p(n);
    rep(i, n) cin >> p[i].first >> p[i].second;

    // 各部分集合について、含まれる2点間の距離の最大値を前計算
    vector<ll> dist(1 << n, 0);
    rep(b, 1 << n) {
        rep(i, n) rep(j, n) {
            if (((b >> i) & 1) && ((b >> j) & 1)) chmax(dist[b], euclid_square(p[i], p[j]));
        }
    }

    // bit DP (メモ化再帰)
    vector dp(1 << n, vector<ll>(k + 1, INFL));  // メモ化配列
    auto dfs = [&] (auto self, int b, int k_) {
        if (k_ == 1) dp[b][k_] = dist[b];  // k = 1のときは計算して返す
        if (dp[b][k_] != INFL) return dp[b][k_];  // 値が更新されていれば返す
        for (ll b_from = b; b_from != 0; b_from = (b_from - 1) & b) {  // 部分集合全体に渡って繰り返し
            ll cur = max(dist[b_from], self(self, b - b_from, k_-1));
            chmin(dp[b][k_], cur);
        }
        return dp[b][k_];
    };
    cout << dfs(dfs, (1 << n) - 1, k) << endl;
}

これで、メモ化しているので、計算量は 3^ N K...と思って提出するとTLEします。

何が問題なのか

このDPでは、部分集合を管理するbit bに含まれる1の個数がkより小さいときには、dp[b][k]の値は最大値（INFL）から更新されません。 これは、元の問題に置き換えると「ひとつも点が属さないグループがあってはならない」という条件を満たすようなグループ分けが存在しないためです。

メモ化でないDPをしているときには、特にこれは気にする必要はないのですが、メモ化DPをしている場合、このような点をきちんと探索済みとしてマークしておかなければ複数回同じ点を探索されてしまいます。

AC解答

同じ点を複数回探索することを避けるために、元のコードで探索した結果値が更新されなかった場合にも、値を更新するようにしておきます。 これは、十分に大きな値であって、INFLとは異なる値にすればよいだけなので、例えば(INFL - 1)などとしておけば良いです。

ということで、再帰に以下の1行を追加します。

実装例 (AC、再帰関数部分のみ)

    // bit DP (メモ化再帰)
    vector dp(1 << n, vector<ll>(k + 1, INFL));  // メモ化配列
    auto dfs = [&] (auto self, int b, int k_) {
        if (k_ == 1) dp[b][k_] = dist[b];  // k = 1のときは計算して返す
        if (dp[b][k_] != INFL) return dp[b][k_];  // 値が更新されていれば返す
        for (ll b_from = b; b_from != 0; b_from = (b_from - 1) & b) {  // 部分集合全体に渡って繰り返し
            ll cur = max(dist[b_from], self(self, b - b_from, k_-1));
            chmin(dp[b][k_], cur);
        }
        /* 以下の1行を追加 */
        if (dp[b][k_] == INFL) dp[b][k_]--;  // 値が更新されていなければ、-1して探索済みをマークしておく
        return dp[b][k_];
    };

上記でACできます。

まとめ

  • メモ化再帰で初期値から更新されない値がある場合、メモ化配列を探索済みとして更新する処理を入れる。
  • これは、0で初期化するような場合も同じ（初期化を-1として、探索済みを0とするなど）

遷移考えるのが面倒なので、と甘えて再帰で書かずに、ちゃんとループで書こうね、という話もあったりなかったり

ABC257 D: Jumping Takahashi2 サンプルコード（Python）

解説を見てACしたので投稿。解説以上の情報は無いので、サンプルコードとしています。

方針

答えXを決め打って制約を満たすかを判定し、制約の範囲を二分探索する。 ある頂点から別の頂点へのパスがあるかは、ワーシャルフロイド法で判定できる。

Code

from itertools import product


def binsearch_int(s, e, f):
    c_min = s
    c_max = e
    while c_min != c_max:
        p = (c_min + c_max + 1) // 2
        result = f(p)
        if result:
            c_min = p
        else:
            c_max = p - 1
    return c_min

def dist(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def f(S):
    edges = [[None for j in range(N)] for i in range(N)]
    for i, j in product(range(N), range(N)):
        dist_ij = dist((nodes[i][0], nodes[i][1]), (nodes[j][0], nodes[j][1]))
        if dist_ij <= S * nodes[i][2]:
            edges[i][j] = 1
    # Use WF
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if edges[i][k] and edges[k][j]:
                    edges[i][j] = 1
    for i in range(N):
        for j in range(N):
            if edges[i][j] is None:
                break
        else: return False
    else: return True

N = int(input())
nodes = []
for _ in range(N):
    nodes.append(tuple(int(i) for i in input().split()))

print(binsearch_int(0, 4 * 10 ** 9 + 1, f) + 1)

その他コメント

  • ワーシャルフロイドを使っている部分では、距離は必要ないのでパスが存在するなら1、無いならNoneとしている。このようにしてもワーシャルフロイドは問題なく動作する。
  • 二分探索の最大値は、4 * 10 ** 9 + 1としておく必要がある。（最初2 * 10 ** 9 + 1としていてWAした。）ちなみに適当に10 ** 10とかしておいたらTLEした。世知辛い。
  • 二分探索自体はコンテスト中でも思いついていたが、探索範囲10 ** 9とかだと間に合わないと勘違いしていた。logNってめっちゃ短いんですね。。。
  • 二分探索部分は再利用できるように書いたので、またどこかで使う機会はありそう。