AtCoder反省会してたはずが気が付くと規格読みながらcpprefjpにプルリク投げてた

はじめに

本記事では，私の所属サークルでAtCoderコンテストABC218の反省会していたはずだったのに，気が付くとC++の規格書を読みながらcpprefjpにプルリクエストを送信していた，という話をします．本記事は，室蘭工業大学 Advent Calendar 2021の3日目に割り当てられた記事です．

adventar.org

本記事の内容は，【LT会】Acompany競技プログラミングLT会 #1で発表したLTの内容をもとにしています．

acompany.connpass.com

経緯

まず，C++の規格書を読みながらcpprefjpの記事を修正するまでの経緯を述べます．

私の所属サークルのAtCoder反省会

私の所属サークルにはAtCoder反省会という会があります．これは，AtCoderのコンテストの時間になったら，オンラインで集合してコンテストに参加し，コンテスト終了後にそのコンテストの問題の解き直し，感想戦，解説などを行う会です．この会は，競技プログラミングをする部員同士で交流することを目的として始まりました．

ABC218

2021年9月11日に開催されたABC218では，100分間のコンテストの内82分経過した時点でA，B，D，Cを解くことができ，残り18分間でEに挑みました．

atcoder.jp

辺を報酬に関して昇順に並べた上で，グラフが連結になるまで，報酬が低い方からまだ連結していないノード同士を繋ぐ辺をグラフに追加していけば良さそうだなあと感じ，DSUを使って実装しました．しかしながら，結果はWrong Answerで，コンテスト中にデバッグを完了することができませんでした．

atcoder.jp

ABC218のAtCoder反省会

ABC218が終了した後，所属サークルのAtCoder反省会が始まりました． Eの解説をチラッとだけ見てみると，コンテスト中に思いついた解法は想定解法と同じっぽい雰囲気がありました．運の悪いことにサンプルのテストケースは通ってしまっていたので，テストケースをいくつか自作してプログラムの内部状態の変化を確認しました．そうすると，辺を報酬に関して昇順に並べる処理に失敗していることに気が付きました．この処理は以下のようにしてstd::multiset<tuple<ll,ll,ll>>型の変数Cに辺の情報を追加することで実装していました．

/* 省略 */
using ll = /** __int128; //*/ std::int_fast64_t;
/* 省略 */
void solve(){
  /* 省略 */
  auto cmp = [&](tuple<ll, ll, ll> const &t0, tuple<ll, ll, ll> const &t1) {
    return get<0>(t0) < get<0>(t1) || get<1>(t0) < get<1>(t1) ||
           get<2>(t0) < get<2>(t1);
  };
  std::multiset<tuple<ll, ll, ll>, decltype(cmp)> C(cmp);
  /* 省略 */
}

ここで，Cにはそれぞれの辺の情報が次のようなタプルとして格納されます．

要素として報酬，一つ目のノード，二つ目のノードをこの順に持つタプル

また，Cに格納される辺が報酬に関して昇順に並ぶようにするために，コンパレータcmpを指定しています．

このコンパレータは，とりあえずtuple<ll, ll, ll>のコンパレータのデフォルトの実装と同じものを用意しておいて，後で考察しながらいじれるようにするつもりでした（実際にはデフォルトの実装からいじる必要はありませんでした．）．しかし，デフォルトの実装のつもりで記述したコンパレータが実際にはデフォルトの実装と異なったものとなっていました．これが，Wrong Answerを解消できなかった根本的な原因であり，ここに誤りがある限りいくら考察を進めてもAcceptedには辿り着けません．

コンパレータの実装の誤りに気が付いたので，以下のサイトの記事を読んで正しい実装を確認することとしました．

cpprefjp.github.io

この記事を読んでいると，記事のコードの中に「`」が紛れ込んでいるのを見つけたため，この1文字を削除するだけのFix typoプルリクエストを軽い気持ちで送りました．

github.com

その時点では，「翌日にはマージされているだろう，また一つ，Fix typoのプルリクエストを送ってしまった」と思っていました．

プルリクエストがマージされるまで

翌日，プルリクエストにコメントが送られました．私は，コメントの内容を以下の通りに解釈しました．

私がプルリクエストを送る前の説明が，そもそも不完全であったため，それを完全なものとする必要がある．
私がプルリクエストを送る前の説明が，C++17における説明であり，C++20においての説明にする必要がある．

私は，元のプルリクエストの修正範囲を超えていると感じ，プルリクエストを閉じようとしました．そうしたところ，C++17における説明を完全なものとすることにも意義があるため，その修正をこのプルリクエストでやったらどうかという主旨のコメントが追加されました． C++の規格書として参照すべきURLも与えられていたため，これを見ながら修正を行いました．修正は，基本的に規格書の内容を日本語訳することにより試みました．これに合わせて，プルリクエストのタイトルを変更し，レビューをお願いしました．

これに対して返されたレビューについて，私は以下の通りに解釈しました．

修正内容には問題は無い．
コミットの単位をsquashにより修正するべきである．

squashをするのが初めてだった私が少し自信なさげに「やってみます」と返答したところ，なんとレビューコメントにsquashのやり方まで追記してくれたのでした．コミットのsquashを行うと，プルリクエストは無事マージされました．

私のFix typoでないプルリクエストで，個人的なプロジェクト以外のリポジトリにマージされたのはこれが初めてでした．

ABC218のE問題のAccepted

コンパレータはstd::tupleのデフォルトの動作で十分であると考察したため，デフォルトのコンパレータを使用するように変更したところ，デバッグも順調に進み無事Acceptedとなりました．

atcoder.jp

誤りのあったコンパレータを，あえて明示的にデフォルトの動作と同様の動作をするように修正すると以下のようになります．

/* 省略 */
using ll = /** __int128; //*/ std::int_fast64_t;
/* 省略 */
void solve(){
  /* 省略 */
  auto cmp = [&](tuple<ll, ll, ll> const &t0, tuple<ll, ll, ll> const &t1) {
    return get<0>(t0) < get<0>(t1) ||
           ((!(get<0>(t1) < get<0>(t0))) &&
            (get<1>(t0) < get<1>(t1) ||
             ((!(get<1>(t1) < get<1>(t0))) && get<2>(t0) < get<2>(t1))));
  };
  /* 省略 */
  std::multiset<tuple<ll, ll, ll>, decltype(cmp)> C(cmp);
  /* 省略 */
}

【LT会】Acompany競技プログラミングLT会 #1

私の友人の所属先が開催するLT会で，競技プログラミングに関するテーマでLTを募集していました．私も何か発表してみたいなあと考え，上記の内容を5分程度にまとめてLTを申し込みました． LTに対しては，予想していたよりも良い反応をいただくことができ，発表した甲斐があったと思いました．また，LT後の雑談も盛り上がり，Androidアプリの開発やRustをおすすめされたりしました．

私のLTの他に，2つのLTがありました．一つは，作問をすることにより，解けなくても思考を続ける粘り強さを養いましょう！という内容でした．解ける解けないといったことの他に，考察そのものの楽しさを忘れないようにしたいと思いました．もう一つは，ICPCに出場しましょう！という内容でした． ICPCに出場したり，コーチとしてついて行ったりしたことを思い出して，懐かしく感じました．

LT会の後で，LTの内容が競技プログラミングと少しずれていたかもしれないと思いました．友人にそのことを言ってみると，ずらし方が巧妙で気が付かなかったと言われました．