ABC333 A-E を解く速度を振り返る

この記事はサステナブルなぴょこりんクラスタ Advent Calendar 2023 の為に書いたものです。

初めに

前回の続きです。
別ネタを準備しようと思ってたんですが間に合わなかったんだすまない。

軽く前回のおさらいをすると、
AtCoder で最近成績伸びないの、難しい問題を解く以前に簡単な問題を解く速度が足らなくない？
という話をしました。

今回は、前回参加した AtCoder ABC 333 を題材にして、
自分が問題を解いたときに何にどのくらいかけていたのか、
強い人はどうなってるのか、の分析をしていきたいと思います。

ABC 333 の自分の成績

これも前回のおさらいですが、ABC 333 の自分の成績は以下でした。

A問題	B問題	C問題	D問題	E問題	F問題	G問題
〇(0:51)	〇(6:02)	〇(15:29)	〇(30:58)	〇(44:41)(1×)	×	×

誤答ペナルティ5分を足すと、この成績は5問を 49:41 で解いた成績となります。

1問平均10分、まぁそんなもんかなという気もしますが、これでは青コーダーにはなれんのだ、というのは前回も書いた通りです。

ABC333 A-E 問題振り返り

というわけで、今回はA-E問題の解いた様子を振り返りましょう。
こんなこともあろうかと当日解いていた様子はひっそり録画に収めています

youtu.be

これを今回は youtube 検索して見つけた強い方との内容と見くらべてみましょう。

www.youtube.com

雑に youtube 検索して見つけたもので比較をしましたが、
よく調べたらこのお方(こたつがめさん)はレッドコーダーで、
ABC333 の（レート対象外の人も含めた）総合順位は6位の方でした。やばすぎ。
まぁ、比較対象は高みにあればあるほど自分との差が浮き彫りになるというものなので、かえって良かったかもしれません。

お断り
この分析はこたつがめさんの許可を得ずに作成しています。
基本的に強い人の動きを参考しようというリスペクトの気持ちのみで作成していますが、
もしかしたら不快に思われる内容があるかもしれませんし、何かしら問題がある可能性はあるかもしれません。
問題があれば削除しますのでご連絡ください。
ここまでお断り

A 問題

A - Three Threes

問題要約

N (1~9) が与えられるので N を N 文字つなげた文字列を出力する

自分の解法要約

提出内容：https://atcoder.jp/contests/abc333/submissions/48533969

for 文で出すだけ

自分のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
00:14	00:00	ここまでで全問題をタブで開き、A問題を見始める
00:17	00:03	問題文を把握したのでコードを書き始める
00:37	00:23	最初のコンパイル
00:41	00:27	お試し実行開始。N=9 を試す
00:51	00:38	提出

まぁ51秒で提出してるのでこんなもんですよね。
実際のところ、テストもさぼったし、今回はかなりA問題を解くのは早かったと思います。

強い人のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
00:04	00:00	A問題を見始める
00:19	00:15	vim 起動、動作確認
00:26	00:22	提出準備開始
00:33	00:27	提出

比較した感想

vim で解いてる（　 Д ）　ﾟ　ﾟ

コード書き始めの時間は大差ないというのに、提出時間ですごく差が付きましたね。
こういうの vim では x@-pZZ でかけるらしい。みじかっ。
最近 vscode に乗り換えたけど自分は長らく vim を使ってたつもりではあるのですが、これを真っ新な状態で書けるような覚え方はしていないし、この解法がぱっと出てきて一発で通せるというのには舌を巻きますね。これが今の上級者の力か…

A問題の教訓：簡単な問題は vim など超ライトな方法で提出することを検討する

B 問題

B - Pentagon

問題要約

ABCDEの頂点からなる正五角形がある。
2つの線分を入力としてこの二つの線分の距離が等しいかどうかを判定せよ。

自分の解法要約

提出内容：https://atcoder.jp/contests/abc333/submissions/48542494

とりえる長さは辺の長さか対角線の長さの二種類しかない。
ABCDE を 012345 の数字と対応付け、入力を受け取ったら頂点の対応する数字の差を取ってみる。
差が1か4だったら辺の長さ、2か3だったら対角線の長さなので、
その結果を見比べれば良い。

自分のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
00:53	00:00	問題文読み始め
01:16	00:23	とりあえず入力受付部分だけ書きはじめる。（その後、少し悩む）
01:48-02:20	00:55-01:27	頂点を数字に割り当てて差を求めるコードを書く
02:36-03:01	01:43-02:08	差の値が常に正の数になるように線分の文字列をソート
03:26-04:16	02:33-03:23	差の値が2or3の時、1or4で決まる変数を設定
04:16	03:23	初コンパイル。エラーをすぐなおす
04:25	03:32	コンパイル成功
04:29	03:36	テスト実行。結果がおかしいと気づいて考え始める
04:51	03:58	printf デバッグを書いて様子を見る。この後変数名ミスに気付く
05:10	04:17	変数名ミスを修正し再実行。まだおかしい。この後で定数の設定ミスに気付く
05:24	04:31	直ったのを確認
05:58	05:05	提出…の前に printf デバッグのコードを消して変な出力が出ないか確認するなど
06:02	05:09	提出

最初にコード書くまで大体3分半、デバッグに約1分、デバッグきれいにして提出するのに大体30秒、という感じですね。

強い人のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
00:42	00:00	B問題を見始める
00:54	00:12	問題文を理解する＋A問題のジャッジ結果を確認する
01:05	00:23	vim 起動、ほどなくして実装開始
01:36	00:54	文字列受け取って頂点の数字の差をとり1 or 2 を返す関数を書く
01:45	01:03	一通りの実装が完成
01:59	01:17	テストケースでの通過を確認
02:13	01:31	手入力で追加で何通りかテストを試す
02:18	01:36	提出

うーん、はやい。すごい。

比較してみた考察

このレベルのコードで上級者は printf デバッグとか当然やってないんだよな。そりゃそう。
文字列を受け取ってから頂点の数字を取って 1 or 2 を書く関数をつくったのが印象的ですね。

int f()
{
   string S;
   cin >> S;
   int a=S[0]-'A', b=S[1]-'A';
   int d=abs(a-b);
   d = min(d,5-d);
   return d;
}

同じことを自分がやったコードが以下です

   string A,B;
   cin >> A >> B;
   sort(A.begin(), A.end());
   sort(B.begin(), B.end());
   int diff = (A[1] - 'A') - (A[0] - 'A');
   int diff2 = (B[1] - 'A') - (B[0] - 'A');
   int len = 1;
   if (diff == 2 || diff == 3)
      len = 2;
   int len2 = 1;
   if (diff2 == 2 || diff2 == 3)
   {
      len2 = 2;
   }

自分はとりあえず入力を変数にぶち込むとこを先に書いてしまいがちなので、
入力から始まる一連の処理を関数にする発想がなくてdiff1とかlen2 とか作りながらコピペコードを書いてしまうのですが、
このあたりを一つの関数にまとめることでバグを減らす効果がありそうです。
事実、自分がバグって困ったのは len2 とかの名前変更ミスとか len2 =1 に化けてたとかですし。
重複コードは廃すべきというのは理論上わかっているところではあるのですが、このまとめ方は思い浮かばなかったなぁ。

また、値が1,4の時と2,3 の時をまとめる方法がわからなかった僕は diff==2 || diff==3 という格好悪い条件式にしていますが、
d = min(d,5-d) というスマートな書き方をしてるのもすごく賢いですね。

言われたら確かにそれでよいねってなるけれど、これを瞬時に出せる引き出しと速度があるのは強い…。

B問題の教訓：コードの重複を排除するテクはもっと身に着けられるところがありそう

C 問題

C - Repunit Trio

問題要約

10進数ですべての桁の数字が1である整数をレピュニットと呼ぶ。
3つのレピュニットで表せる整数のN番目 (N<=333)に小さいものを求めよ

自分の解法要約

提出内容：https://atcoder.jp/contests/abc333/submissions/48552335

N の数が小さいのである程度の数のレピュニットを配列で持ち、
for文を3つ回して和のリストを作ってソートし、N 番目を取る

自分のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
06:03	00:00	問題文読み始め
06:09	00:06	とりあえず入力を受け付けるコードを書きつつ考える
07:11	01:08	色々考えるも、同じ値のレピュニットを足してよいと聞いて少し悩む
08:02	01:59	そうはいってもfor文3つかけるので良いはずだと思う
08:24	02:21	レピュニット何個用意しよう…8^3 >333 だから8桁かな、と思う（間違い）
08:38	02:35	`lep[]={1,11,...11111111}` を用意
09:01	02:58	`for(i=0...8)for(j=0...8)for(k=0...8) v.add(lep[i]+lep[j]+lep[k])` と書き始める
09:42	03:39	`lep[0]+lep[1]+lep[0]` と `lep[1]+lep[0]+lep[0]` が重複して計算されるのまずいと気づく。とりあえず 8桁は9桁にする
10:29	04:26	lepの値はスカスカだし適当に重複排除するか…と思うも、 c++ でベクトルの重複排除の書き方を忘れたのでぐぐる
11:04	05:01	1st compile、コンパイルエラーちょいなおす
11:12	05:09	2nd compile、コンパイルできたのでテストを調べる
11:26	05:23	結果が一致しないので再考。
12:08	06:05	9桁足らない説を予測してprintf してみるも空振りしたように感じる (本来この想定はあっていたが、printf の場所自体が悪かった）
12:31	06:28	そもそも `for(i=0...N)for(j=i...N)for(k=j...N)lep[i]+lep[j]+lep[k]` でいいから unique とか要らんわ、と思い書き直す
13:00	06:57	直すも結果がおかしかったり9桁で足りなかったり
14:20	08:17	sort を勢い余って消してるのを治しつつ lepを10桁で試す
14:53	08:50	lepを11桁で試す
15:14	09:11	lepを12桁で試して結果の一致を確認
15:29	09:26	printf コードをコメントアウトして提出

重複無しで足し算するなら for(i=0...N)for(j=i+1...N)for(k=j+1...N) だよね～ってのは割とよく見るのですが、
重複有りってなっただけでなぜか混乱して右往左往してしまったのがかなり反省点だなぁと思う。

強い人のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
02:22	00:00	C問題を見始める
03:08	00:46	vim 開く、こうか？というコードを書き始める
04:08	01:46	コードを書いてテストを始める
04:20	01:58	提出

2分かかってなくて草。

比較してみた考察

そもそも解き方が違うんですよね。
自分の考えた解き方は
https://atcoder.jp/contests/abc333/editorial/7982 で紹介されているものに近いですが、
強い人が採用した方法は
https://atcoder.jp/contests/abc333/editorial/7979 の解き方です。

肝としてはレピュニットは1しかない数字なのだから3つ足しても各桁の値は最大で3までにしかならないし、
1の桁は必ず3だしこの数字は単調減少しかない、という話らしい。なるほど。
後者の解き方は自分は思い浮かばなかったんですが1分足らずでこの解法にたどり着くのは強いなぁ…。

それはそれとして。自分の解き方でも editorial のページにある通りもっとコードは簡素にかけたはずなんですよね。
python では r = [int("1" * (i + 1)) for i in range(L)] と書いてるところを丁寧に手書きで作ってるところとか、
for 文の終端の値をハードコードしてるから逐一丹精込めて変えてるところとかに要領の悪さが出ていそうです
（そもそもそんなに変えるとは思わなかったので size とかとるのさぼったのが裏目った…）

また 11:26 時点で結果が合わないことから解き方を考え直して書き直していますが、
たぶん何かしらバグってるだけで 11:26 時点の解き方でも問題はなかったはずなので、
そういったタイムロスも響いていますね。

後は純粋に考察してからコード書き始めるまでも遅い。

C問題の教訓１：解法を変えると素早く解ける可能性がある
C問題の教訓２：{1,11,111...} みたいな定数のハードコードを極力なくしてきれいに書く努力をしたい

D 問題

D - Erase Leaves

問題要約

木(グラフ)構造が与えられる。
葉を除去する操作のみ認められてるとしたとき、頂点1を削除するまでに最小で何回操作が必要か？

自分の解法要約

提出内容：https://atcoder.jp/contests/abc333/submissions/48565924

頂点 n を削除する最小の操作数を ans[n]とするような配列を考えると

$ans_n = 1+ \displaystyle \sum_{k}^{nの子}ans_k$

として再帰的に計算できるので、1 を root とした dfs で適当に計算する。

ただし、頂点1を削除するにあたっては子のうち一つを削除する必要はないので、
$ans_1 - max_{k}^{1の子} ( ans_k )$ が答えになる。

また、そもそも 1 が葉であるときは ans[1以外] の値は計算されず上の式の値が変な値となるため、このケースは特殊処理として1を返す。

自分のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
15:30	00:00	問題文読み始め
16:41	01:11	とりあえず入力を受け付けるコードを書きかける
17:31	02:01	ans[n] みたいなものがあればよいはずだな…と考える
18:01	02:31	枝を持つ構造体とか ans[n] とかをグローバル変数にお引越しし、再帰関数 rec で ans を計算しようとする
20:35	05:05	1st compile, 色々エラー
21:41	06:11	dfs したいのに親もたどってしまう問題を修正。コンパイル通るが結果があわない
22:21	06:51	printf デバッグしながら思い悩む
22:34	07:04	そもそも入力を受け取るところが不完全と気づく
22:58	07:28	修正完了したがまだ結果が合わない
23:41	08:11	ans[n] の計算結果が 1+ min(ans[k]) と間違ってることに気づく
24:34	09:04	ans[n]= 1+ sum(ans[k]) としたら ans[1] が答えにならなくない？と悩む
25:56	10:26	ans[1]-max(ans[k]) がこたえになるからいいか。と思ってコードを修正
26:34	11:04	直したがまだ答え合わない
27:50	12:20	ans[n] = sum(ans[k]) になってて +1 忘れてることに気づいて修正
28:21	12:51	だいぶよさそうだがテストケース2だけ落ちることに悩む
29:45	14:15	ノード1が葉だと不都合があることに気づく。特殊処理を書く
30:58	15:28	提出

強い人のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
04:25	00:00	D問題を見始める
05:10	00:45	コードを書き始める
05:40	01:15	入力受付部分済
05:52	01:27	あとはこの dfs を書けばOK、という実装ができる
06:06	01:41	dfs 書き終わってテストをし始める
06:13	01:48	提出

これも2分経ってなくて草

比較してみた考察

今回も似ているようで微妙に考え方が違いますね。強い方の解法としては、
答えは min(N- (頂点1の隣接点を k としたとき、k から頂点1を経由せずに行ける点の集合（部分木）のサイズ)) といえるから、
この部分木を適宜 dfs で計算すればOK,というものでした。
1を削除した後で残ってる部分木のサイズさえわかればよいよね、的な。

この解法はノード1が葉の時の特殊処理が必要でない解法のため、
自分のようなデバッグに思い悩んでいないのが良いですね。

また、部分木を求める dfs は僕が ans を計算するときに書いた rec 関数と一緒ですが、書き方の練度と短さが段違いですね。

自分のコードだと

vector<int> ans(300000, INT_MAX);
vector<vector<int>> E(300000, vector<int>());

int rec(int cur, int p)
{
   if (E[cur].size() == 1)
   {
      // cout << cur << ":" << 1 << endl;
      return ans[cur] = 1;
   }
   else
   {
      ans[cur] = 1;
      for (int i = 0; i < E[cur].size(); i++)
      {
         if (E[cur][i] != p)
         {
            ans[cur] += rec(E[cur][i], cur);
         }
      }
      // cout << cur << ":" << ans[cur] << endl;
      return ans[cur];
   }
}

ですが、これを強い人に書かせると

vector<int> G[3<<17];
int dfs(int u, int p)
{
    int ch=1;
    for(int v:G[u]) if(v1=p) ch += dfs(v,u);
    return ch;
}

こうなる。

部分木のサイズを求める関数など頻出だからそりゃぁね、といわれたたらそうかもですが、
あまりに早くてビビりました。

葉の場合の場合分けをする必要がそもそもない
n=1の結果しか必要ないので ans[N] みたいな変数定義とか詰め込みとかのコードは不要になる
- 木のサイズがそこそこ大きくてなおかつ dfs(1), dfs(1の子), dfs(1の孫) とかを必要に応じて何度も計算する必要があるならあった方が良いけど。
そもそも for 文も int i = 0... みたいな書き方をしない方が速い

あたりがポイントかなぁと思います。

D問題の教訓：解をそのまま ans... みたいなテーブルに安易に入れずに言い換えを考えるとスマートにとける可能性がある
D問題の教訓2：部分木サイズの計算などよくある関数の記述方法はコンパクトに書く習慣づける (嫌ならスニペット化してもよい）

E 問題

E - Takahashi Quest

問題要約

以下のどっちかのイベントがトータルでN回起こる

タイプ x のポーションを発見する（とるか取らないか選択できる）
タイプ x のポーションで倒せるモンスターが現れる

モンスターを全部倒せなければ -1 を出力せよ。
モンスターを全部倒せるなら、道中の所持ポーション数の最大値を可能な限り小さくしたい。
その値と、各ポーション発見イベントで取る・取らないの行動を出力せよ。

自分の解法要約

提出内容： https://atcoder.jp/contests/abc333/submissions/48576060

イベントを逆順で見ていきつつ greedy で解く。

モンスターが出てきたら、対応するポーションは絶対にどこかで拾わなくてはならない。
道中の所持数の最大値を最も小さくするためには、
引き続きイベントを逆順で見たときに、対応ポーション一番最初に出てきたタイミングで拾えばよい。

そんな感じでポーションを拾う戦略を立てて、倒せないモンスターがいたら -1、
倒しきれるなら道中ポーションの最大値とポーション拾う・拾わないの結果を出力する。
道中ポーションの最大値は逆順で戦略を考えるなかでは計算しずらいので、正規のイベント順でシミュレーションする。

拾わなきゃいけないポーションの集合は重複を含みや挿入・検索・削除に O(N) かけたくないやつなので、
multiset を使って O(logN) で処理する。

自分のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
30:59	00:00	E問題開く
32:21	01:22	とりあえず入力受付部分を書き始める
33:11	02:12	multiset の削除ってどうかくっけ、をググる
34:56	03:57	大体わかったのでかきはじめ
37:06	06:07	逆順にたどって ms と行動選択を計算するとこまで完了。結果出力部書き始める
37:54	06:55	1st compile、いろいろミスってる
38:16	07:17	コンパイル通るが結果違う（ここまで、最初の1行目にはとりあえず1を返せば良いと思っていた）
38:31	07:32	ポーション拾う数を答えるのか？と思ってコードを書く
39:12	07:52	書いたけどそれだとサンプルケースおかしくない？と気づく
40:06	08:13	出すべきは道中所持ポーション数の最大と気づく
41:16	09:07	ポーション取る取らない戦略は今のコードのままでよさそうと判断。道中所持ポーション数の最大値の出し方考える
42:36	10:17	愚直に最初からシミュレーションするコードを書き始める
42:55	11:37	コンパイル通ってテスト結果見る。拾う・拾わない戦略の結果が異なるが何種類か解がある代物なので放置
42:55	11:56	提出
42:56	11:57	F問題開く
43:01	12:02	とりあえず入力受付部分かく
43:12	12:13	E問題が Wrong Answer になってると気づく
43:26	12:27	サンプルでも落ちてる…だと…？
43:49	12:50	ポーション取る取らないの出力するとこ、モンスター登場ターンを飛ばすのを忘れて0を余計に出力してたと気づく
44:41	13:42	修正と再テストを完了して再提出

問題文の理解が中途半端なままコードを書いてめちゃくちゃもてあそばれてる感がありますね。

強い人のタイムライン

コンテスト開始からの時間	問題開始からの時間	やったこと
06:27	00:00	E問題を見始める
07:48	01:21	コードを書き始める
08:57	02:30	上から順にイベントを見ていき、積むパターンの出力まで終える
09:00	02:33	実装を書く
09:44	03:17	結果出力あたりかく
10:00	03:33	コンパイル通ってサンプルを使ったテストを始める
10:50	04:23	提出

リアルタイムにみててどういう解法してるのか理解できなかったけど爆速で解いてて笑った。

比較してみた考察

今回も解き方は微妙に異なっていますね。

僕はイベントを逆順に見ることで「モンスターを倒すときに必要なポーションは最後に獲得する」を実現していましたが、
強い方の解法ではイベントを普通に上から順に処理しながら、各タイプのポーションがいつにあるかを vector で記録し、
必要となったら pop_back() でモンスターの登場前に最後にとれるポーションを使う、という実装をしていました。
また、この解き方だとモンスターが出るタイミングでポーションを拾う箇所が確定するので
最大所持数のカウントに難ありかとも思われましたが、imos 法(説明略)を使って計算を行っているようです。
もっとも、どちらにせよ for 文は2回書かないという点ではどっちも同じですが…

この辺りはまぁ…解く速度の観点ではそんなに違わないかな…という気もしますが、
multiset を使わないだけ計算量の観点では vector を使った方が強そうですね。

E 問題についてはどちらかといえば、
問題文を十分に読まずに勘違いして先に進んで手間取った所が響いたかなぁ、という気がします。

あとはなんかこう… imos 法とかを記述する練度が半端なくて
ノータイムでさらさら書いてるのが強いなぁと思いました。

E問題の教訓：問題文の誤読に気を付ける 　

終わりに

というわけで今回は、 ABC 333 の A-E 問題を題材にして自分のタイムラインと強い人のタイムラインを比較し、
それぞれの問題を見比べた教訓を書き並べてみました。

ここで得られた教訓みたいなのは頭ではわかってはいる気でいたのですが、
実際に強まった人のプレイングを見るといかに実践するのが難しいのかが身に沁みますね。

たぶん今後も全盛期みたく ABC に毎回参加じゃ！みたいな勢いは出せないとは思うのですが、
参加は継続しながら、適度な研鑽の仕方を模索していきたいなぁと思います。

やおよろず

ゆるふわな内容を書いても良い。と言うか何でも良い。そんな自由度の高いブログをめざします。

ABC333 A-E を解く速度を振り返る

初めに

ABC 333 の自分の成績

ABC333 A-E 問題振り返り

A 問題

問題要約

自分の解法要約

自分のタイムライン

強い人のタイムライン

比較した感想

B 問題

問題要約

自分の解法要約

自分のタイムライン

強い人のタイムライン

比較してみた考察

C 問題

問題要約

自分の解法要約

自分のタイムライン

強い人のタイムライン

比較してみた考察

D 問題

問題要約

自分の解法要約

自分のタイムライン

強い人のタイムライン

比較してみた考察

E 問題

問題要約

自分の解法要約

自分のタイムライン

強い人のタイムライン

比較してみた考察

終わりに