導入
こういう話はある*1んですが、最初からバグらせやすい書き方をしておいて「バグが出たー」と言われてもそれはそうとなってしまうので、そういうのを控えるくらいのことはするべきだと思います。 書き方が悪いせいで「十分に複雑なコード」になってしまっているものもあります（もちろん概念自体が複雑なものを実装するときは複雑になって当然ですが）。
「控えるべき書き方」とか「書くときに気をつけるべきこと」とかを紹介します。 あくまで自分の主観であって、読み手の人の方針に反するのであれば強制する気はないです。「こういう書き方もあるよー」くらいに捉えてください。
紹介
主に想定は競プロ文脈です。業務だとどうのこうのみたいな苦情を受けつける気はありませんが、業務でも使えないとは言っていません。
変なケアレスミスでペナルティが出るのを防ぐのも紹介します。知っている人には常識のものばかりですが、知らない人にとっては身につけにくいものかなとも思います。あと無限回 Twitter で言及しているので見飽きている人もいるかもしれません。
控えたいこと
控えたいことの部分は章立ての書き方が難しい（「本来○○をするべき」なのか「○○を控えるべき」なのかが揺れがち）ですが、「本来○○をするべき」を意図して書きます。
フラグ変数を乱用しない
まず bool の変数名に flag flg f などという無意味な名前をつけるのは極力避けた方がいいです。bool の紹介のときにそういう名前がされがちなのでそれで覚えがちですが、せめて is_ok とか needs_update とか is_updated とか、「これが true のときはこういう条件なんだな」というのがわかるような名前にするべきです。int の変数に number と命名したり、string の変数に text と命名したりするようなものですね。それで十分なときはいいかもしれないですが。
使っているうちに自分でも条件を誤ってしまうミスの原因になります。後からデバッグのために読み返したときも気づきにくいです。 そもそもフラグ変数を避けられるときは避けた方がいいでしょう。
実際の問題を例にした方がわかりやすいかと思うので、そうします。
# よくない例 n = int(input()) s = input() flg = False if 'o' in s: flg = True if 'x' in s: flg = False print('Yes' if flg else 'No')
気にしたい条件は 'o' in s と 'x' in s だけなのに、flg を何度も書き替えるせいでコードを追うときに考えることが増えてしまいます。
o の判定と x の判定は独立の条件なのに処理の順番に依存している（x の判定を先に書くと s = 'ox' を Yes にしてしまう）のがうれしくないです。
# よい例 n = int(input()) s = input() is_ok = ('o' in s) and ('x' not in s) print('Yes' if is_ok else 'No')
気にしたい条件だけ書かれていて、読む際の負荷が少ないです。
他にも、このように条件が複雑になる場合は、フラグ変数を用いるのではなく関数を使うのがおすすめです。
def is_ok(a, b): if not (なにかの必要条件): return False if (なにかの十分条件): return True # なにか処理 if (なにかの条件): return (なにか) # なにか処理 return (なにか) n = int(input()) a = list(map(int, input().split())) b = list(map(int, input().split())) print('Yes' if is_ok(a, b) else 'No')
一度 False であることを確定させてしまえば、残りの処理でうっかり True になってしまうようなことがないのがうれしいです。
一度 False にしたものを True にしてまた False にして... のような処理が必要そうな場合は、考察を見直すか、その部分を別途関数に分けるのがよさそうです。
デバッグは標準エラー出力に書く
デバッグのために配列を出力させたりすることはあると思います。
# Python の例 print(a)
// Rust の例 println!("{a:?}");
// C++ の例 for (int i = 0; i < int(a.size()); ++i) printf("%d%c", a[i], i + 1 < n ? ' ' : '\n'); // あるいは `cout << a[i] << ...` など
C++ では長いマクロを自前で定義して DBG(a) みたいに書けるようにしている人もいるかもしれません。
ただ、ジャッジに提出する際にこれらのコードが有効になっていると WA になってしまいます。 いちいち「デバッグする」→「うまくいっていそうなのでデバッグ出力を消して提出する」→「またバグっていたのでデバッグ出力を書いて直す」のような手順を踏むのは手間ですし、消し忘れも起きやすいです。
それより、標準エラー出力というのを使うのがよいです。 本来のコマンドの出力ではなくユーザへのメッセージのための出力に使われたりするものなので、「競プロのジャッジをごまかすために使えるから本来の意図に反したものを使っている」という感覚ではないです。
各言語では以下のようにすればよいです。
# Python の例 import sys print(a, file=sys.stderr)
// Rust の例 eprintln!("{a:?}");
// C++ の例 for (int i = 0; i < int(a.size()); ++i) fprintf(stderr, "%d%c", a[i], i + 1 < n ? ' ' : '\n'); // あるいは `cerr << a[i] << ...` など
エラーの出力の量がまともであれば、有効にしたまま提出しても（出力が正しければ）AC になることでしょう。
エラー出力の長さのオーダーがボトルネックになって TLE ということはあります。 また、AOJ のようなジャッジでは「標準エラー出力になにかが書かれていると RE 扱いにする」という挙動もあるので、注意は必要です。 そうならないように、ジャッジ環境ではエラー出力が出ないようにする関数を作るなりしておくのがよさそうです。
# Python はジャッジ環境と区別するのどうしたらいいんでしょう。 # 自動で切り替えるのはつらいかも。コメントアウトで運用するしかない？ # （でも Python だと `eprint` の関数呼び出しが最適化で消えてくれなくて遅くなるとかある？） def eprint(*args, **kwargs): print(*args, **kwargs, file=sys.stderr) # 提出時はコメントアウト pass
// Rust の例 // リリースビルド時は `eprintln!` に何も出力させない。 // これをファイル冒頭にでも書いておくだけで勝手に分岐してくれる。 #[cfg(not(debug_assertions))] macro_rules! eprintln { ( $($tt:tt)* ) => {} }
// C++ の例 #ifdef ONLINE_JUDGE # define DBG(...) (void)0 #else // `DBG` のマクロを定義する。ここでも標準エラー出力に出すようにしておくと、 // 手元でのテストを自動化する際に都合がよいと思われる。 #endif /* ONLINE_JUDGE */
出力パートは一箇所にまとめる
「条件を満たすように操作できるときは Yes に続けてその操作列を所定の形式で出力し、そうでないときは No を出力せよ」というのはよくあるパターンです。
こういうので、main の中で判定と出力をいちいち書くのはやめた方がいいです。
int main() { // 入力パート略 if (!(必要条件)) { cout << "NO\n"; return 0; } // 諸々処理 vector<int> answer; if (十分条件) { // なんとかして構成するパート略 cout << "YES\n"; cout << answer.size() << '\n'; for (auto x: answer) cout << x << '\n'; } if (!(別の必要条件)) { cout << "N0\n"; return 0; } if (別の十分条件) { // なんとかして構成パート略 cout << "Yes\n"; for (auto x: answer) cout << x << '\n'; } }
バグがたくさんあります。return が漏れていたり、NO が N0 になっていたりなどです。配列サイズの出力の有無も間違っていますね。
最近の問題では大文字小文字の違いを許容しがちになっているので yES のような出力でも許されたりします*2が、そうでないジャッジではバグですね。
これも関数を分けるのがおすすめです。
pair<vector<int>, bool> solve(諸々) { // 可能なら `{vector{...操作列}, true}` を返し、そうでないなら `{vector{}, false}` を返す } int main() { // 入力パート略 auto [certificate, ok] = solve(諸々); if (ok) { cout << "Yes\n"; cout << certificate.size() << '\n'; for (auto x: certificate) cout << x << '\n'; } else { cout << "No\n"; } }
Rust では Option のような型を使えるので、そういうのを使う方がよいでしょう。
fn main() { input! { 諸々 } if let Some(certificate) = solve(諸々) { println!("Yes"); println!("{}", certificate.len()); for x in certificate { println!("{}", x); } } else { println!("No"); } } /// 可能なら `Some(vec![...操作列])` を返し、そうでないなら `None` を返す fn solve(諸々) -> Option<Vec<i32>> { todo!() }
certificate と呼んでいるのは、「Yes となる証拠の操作列」というような意味合いで、SAT などの NP の文脈で出てくる用語です。同じ意味で witness という言い方もされます。
計算パートと入出力パートは分ける
業務寄り・設計寄りの話で言えば「プレゼンテーション層」「アプリケーション層」のような概念に似ているかと思います（あるいはコントローラ層・サービス層とか）。
グラフの問題や区間クエリの問題でよくあります。 入力は 1-indexed・閉区間 ($1\le l\le r\le n$) で与えられがちですが、実際の処理は 0-indexed・半開区間 ($0\le l\lt r\le n$) で行うことが多いと思います*3。
そうしたとき、処理を行うパートで「ここの変数は 1 から始まるから 1 引いて...」と毎回やるのは漏れや混乱の原因です。 入力を受け取った時点で 0-indexed・半開区間に統一してしまうのがよいでしょう。
// 区間の例 for (int i = 0; i < q; ++i) { int l, r; std::cin >> l >> r; --l; query.emplace_back(l, r); } // グラフの辺の例 for (int i = 0; i < m; ++i) { int u, v; std::cin >> u >> v; --u, --v; edges.emplace_back(u, v); }
use proconio::{input, marker::Usize1}; input! { query: [(Usize1, usize); q], edges: [(Usize1, Usize1); m], }
出力に関しても、計算パートで気にするのではなく（前述の指針の通り共通化してある）出力パートで 1-indexed・閉区間に変換するのがよいでしょう。
いくつかの具体例だけで考察を終わらせない
具体例で考察するの自体が悪いとは思わないのですが、具体例で考えると、先入観で「そのケースがたまたま満たす条件」以外を見落としがちです。
関連記事かも。
「こういう処理を書きたいが、この処理は（入力の制約の範囲で）常に可能なのか？」のようなことを気にかけるとよいでしょう。
これ自体は複雑さに直接寄与するわけではないですが、後から「このケースが漏れていました」のような修正をする際にどんどん複雑になることが予想されます。
書きながら気をつけること
えびちゃんは無意識に気にしているのですが、不慣れな人は気にしている余裕がなかったりするかもしれません？
無意識に気をつけているのと、気にせずに祈るのは違うので注意してほしいです。 なんとなくで気にしているわけではなくて、「この処理があるってことはこういう条件をチェックする必要があるよね？」「こういう処理のときはここさえ気にすればいいよね？」のようなセンサーをぴんぴんさせている感じでしょうか。
事前条件
上で挙げたコーナーケースとかの記事にも関連しますね。
受験数学で言えば「$x$ で割るなら $x\ne 0$ を確認してから割る」というようなのがあるかと思いますが、アルゴリズムに関しても同じです。 問題文で与えられている制約から、処理を正しく行うための条件が成り立つことを確認する必要があります*4。
たとえば、法を $m$ とする計算で乗法逆元を持つ条件（あるいはその計算の仕方）についてきちんと理解せずに雰囲気でやっている初心者は多いのではないでしょうか。 水色や青の人でもそうした部分をあやふやにしている人は結構いる印象です。黄色だとさすがに全人類知っているかもしれません*5。
自分が書いているアルゴリズムが正しいことの証明をする際に、そうしたことを意識しないで何を気にするのでしょうという感じです。言葉が厳しいですか*6。
ループ不変条件・終了条件
これも正当性を示す際に出てくるものです。
// ループ前の処理 while loop_condition { // ??? ここで成り立っている条件 (*) ??? // ループ内の処理 } // ループ後の処理
「ループの冒頭で条件 (*) が毎回成り立っているか？」というのを考えます（これをループ不変条件 (loop invariant) と呼びます）。ループを通じて保たれている条件ということです。
帰納法のように考えていきます。まず最初のループでは「ループ前の処理」の内容と「loop_condition が真であること」を前提として使えます。
「i+1 回目のループでは、i 回目（あるいはそれ以前すべて）のループで条件 (*) が成り立っていたこと」と、「loop_condition が真であること」を使えます。
また、ループ後の処理の証明に関しては、「最後のループで条件 (*) が成り立っていたこと」と「loop_condition が偽であること」を前提として使えます。
もちろん、競プロのコーディング中にこれらを厳密に気にする必要があるとは思いませんが、「こうした手法で正当性を示すんだな」ということを知っていれば、「ループ不変条件を正しく管理するのを意識して書けばいいですね」「ループ不変条件さえ気にすればいいですね」となれるので、闇雲にあれこれ考える必要がなくなってうれしいかなと思っています。
たとえば、にぶたんにおいて「lo 以下の値では該当の判定関数 pred(_) が true になる」とか、「lo <= i < hi なる i で、pred(i) != pred(i + 1) になるものが存在する」とか、そういうのがループ不変条件ですね。
DP を計算するときにも「この時点において、何々の条件における最大値が dp[i][j] に入っている」のようなものを意識するのが大事そうです。
境界値
区間クエリの問題で、添字が複雑になって ±1 が大変になってくるというのは（入力層でのことを適切に処理しても、問題設定によっては）起きてくることだと思います。そうした際に、「区間の左端の最小値は適切に処理されるか？」「区間の右端の最大値は適切に処理されるか？」というのを気にして、そこの添字を正確に合わせるだけでうまくいくことはよくあります。
なので、きちんと整理して「区間の左端の最小値（右端の最大値）としてあり得るものはなにか？」を意識するのが大事になってきそうです。
他にも、DP 配列の長さを n にするのがいいのか n + 1 なのかとか、そういうのにも関わってきそうです。
おきもち
おわり
また表明したくなったら表明します。
*1:十分に複雑なコードを書けばどうせバグる、といった旨の記事です。
*2:これを利用して、どこの条件で yes 扱いになっているのかチェックするテクなどはなくはないですね。
*3:実際の処理も 1-indexed でやる方がいいという人もいるかもしれません。そういう人は 0-indexed・半開区間で与えられた場合のことを考えてください。
*4:「成り立つかどうか一応後から見てみます」というより、（チェックシートのような感じで）「成り立つことを確認してから話を進めます」のようなスタンスの方が個人的にはいい気がします。後からのチェックだと先入観で見逃しやすいですし。
*5:ソースはありません。「反例の人は名乗り出る前に勉強しましょう」とか言っておくことで反例をなくせます。
*6:でもたぶん、CS 系の勉強をしていない人だとアルゴリズムの正当性の示し方とかを知らなさそうなので、そうした記事を書くのがいいのかもしれません。
