本日は4/7(日)のAtCoder ABC348を振り返る。
結果
ABCまでの3完で、パフォーマンスは396。
45分程度でCまでACできたが、D問題を解くための知識を持っておらず3完で終了した。
これを受けて思うのは、前回(ABC347)ではAB2完だったのだがパフォ385で、今回とは「C問題を解けなかった」という大きな差があるにも関わらずパフォーマンスに10程度しか差がない。
自分の直感では解いた問題数によってパフォーマンスが階段式に変わるのかと思っていたが、こちらの記事を読むに「参加者全員に対する順位」が参照されている模様？
なるほど、であれば前回と今回で順位に大きな差がないため、パフォーマンスがさほど変わっていないというのも頷けるではある。
「茶コーダーになるにはパフォ400を安定して取れるようになる」というのをどこかで見たことがある気がするので、であれば「6000位」より高い順位を安定して取れるようになれば良さそうなのかな。
閑話休題。
以下、各問題を個別に振り返る。
A(5:45)
事前目標は5分以内だったのだが、45秒オーバーしてしまった。
ロスした原因は「算術演算子」の記述ミス。「iが3の倍数ではなかったら」の部分を、
if (i+1 % 3 != 0)
と書いてしまったせいで、出力が全て"xxxxxx"となってしまった。
正しくは
if ((i+1) % 3 != 0)
非常に初歩的だが、実戦は気付かなくてとても焦った。
「A問題で時間を使っているようではこの先思いやられる…」的な思考がよぎってしまったが、今振り返ってみるとこのような思考は視野を狭くする原因になるためあまり良くないと思う。
モチベーションが高いことの裏返しではあるものの、純粋に問題を解くことのみに思考リソースを使うべきだろう。メンタル面での精進が必要だ。
最終的に提出したコードは以下。
#include <iostream> #include <algorithm> #include <string> #include <set> #include <vector> #include <bitset> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) using ll = long long; int main() { int N; cin >> N; rep(i, N) { if ((i+1) % 3 != 0) { cout << "o"; } else { cout << "x"; } } cout << "" << endl; return 0; }
B(5:45-17:38)
B - Farthest Point
シンプルな全探索。
この問題で分からなかったのは「2乗する」の記述方式。普通に調べてcmathヘッダのstd::powを使用した。
今回は使用しなかったが「平方根」も、pow(X, 0.5)の形で計算できるようだ。
B問題も5分を目標にしていたのだが、実際にかかった時間は12分程度…。powを調べたロスがあったとはいえ、個人的にはそれなりの速度で書けたと思っていたものの、5分というのはやはり高い目標のようだ。
公式の模範回答コードとの差分もほとんどなかったし、この辺りは純粋な「速度勝負」という感じなのかもしれない。C++の知識もそれなりについてきて、問題文通りに実装できるようになってはいるものの「慣れ」の部分で上位勢と差がついている感じはある。
こればかりはB問題を無限に解きまくって「慣れ」を高めるしかなさそう。少なくとも今回のように「2乗ってどう書くんだっけ？」と調べているようでは難しいだろう。まずは「本番で調べる必要がなくなる」程度の知識水準にしておきたいか。
先週は結構C問題の過去問を解くことに時間を割いてしまっていたが、今週はB問題を解くことにも時間を使うことにしよう。
次回はとりあえず目標を10分とする。
実際に提出したコードは以下。
#include <iostream> #include <algorithm> #include <string> #include <set> #include <vector> #include <bitset> #include <cmath> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) using ll = long long; int main() { int N; cin >> N; vector<int> X(N), Y(N); rep(i, N) { cin >> X[i] >> Y[i]; } vector<int> G(N); rep(i, N) { int max_length = 0; int max_length_i = 1; if (i == 0) max_length_i = 2; rep(k, N) { if (i==k) continue; int length = pow(X[i]-X[k], 2) + pow(Y[i]-Y[k], 2); if (max_length < length) { max_length = length; max_length_i = k; } } cout << max_length_i+1 << endl; } return 0; }
C(17:38-43:31)
atcoder.jp
関門のC問題。先週はC問題に80分掛けても解けず、半分トラウマになっていたが、今回は25分程度ですんなりと解けて（実際難易度も低かったようだ？）「あ、自分でもC問題は普通に解けるんだな」という心持ちを作ることができて良かった。
とはいえ、ここから更に解く速度を高めないとレートは増えていかない。
参考として、冒頭で設定した「6000位」の解答時間を見てみると、2:39-24:12-36:13の3完となっていた。周辺順位の一通り目を通したが、今回においては3完を36分程度で完了することがボーダーだったようだ。
ちなみに、前回のABC347の6000位ボーダーを見てみると「AB2完を10分で終えた上で、C問題にミスを数回出している」層。
毎回C問題の難易度に差があるので、6000位ボーダーが2完になるのか3完になるのかは問題次第というところか。
今回においてはC問題ACまでの時間を後8分短縮できていれば、という感じではある。これは、B問題で5分程度の短縮を見込めることを考えると、C問題で後数分短縮すれば良かっただけということになり、わりかし現実的なラインに思える。
改めて、来週は6000位を目標に、今週の過去問解きに取り組んでいこう。
話が逸れたが、C問題において詰まった箇所を振り返る。
まず、単純な全探索ではTLEすることがすぐにわかる。最も単純な全探索は2×10^5を2周することだと思うが、それはO(10^10)となる。計算の工夫が必要だ。
この問題のポイントはmap変数の使い方。色Ciをキーとして、値に「Ciに対応するAiのうち最大のもの」を格納する。この操作はO(10^5)で実施され、各色の中でのおいしさの最大値を格納することができる。
自分は当時の時点でmap変数を知らず、最初ベクトルで同じことをしようと考えた。しかしCの最大値が10^9ということで、長さ10^9のベクトルを定義して探索するという方式は明らかにおかしいということになり、Pythonにおける辞書的なものをcppで書く方法をChatGPTに聞いたところmapを教えてもらった。
mapさえ分かればあとは実直に実装するのみ。最終的なコードは以下。
#include <iostream> #include <algorithm> #include <string> #include <set> #include <vector> #include <bitset> #include <map> using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) using ll = long long; int main() { int N; cin >> N; vector<int> A(N), C(N); rep(i, N) { cin >> A[i] >> C[i]; } map<int, int> minAForC; rep(i, N) { if (minAForC.find(C[i]) != minAForC.end()) { minAForC[C[i]] = min(minAForC[C[i]], A[i]); } else { minAForC[C[i]] = A[i]; } } int maxA = 0; for (const auto& pair : minAForC) { if (pair.second > maxA) { maxA = pair.second; } } cout << maxA << endl; return 0; }
D(43:31-2:00:00)
atcoder.jp
BFS（幅優先探索）の知識があることが前提の問題。自分はBFSの勉強をしていなかったため、解けずに終了。
さて、BFSとは何だろうか？ いい機会なのでここで勉強することに。
すごくわかりやすそうな記事があったため、知識をここから収集する。対応するものとしてDFS（深さ優先探索）もあり、こちらも勉強が必要そうだ。
まず、この問題を見て「これはBFSをしようすべきだ」と判断するためにはどのような知識が必要だっただろうか。BFSに関する基本的な知識は勿論必要。その上で「どのような問題にBFSを導入しがちか」という知識が必要だっただろう。すなわち「BFSは「最短経路問題」を解くのに適している」ということを知っていれば良かったことになる。今回のD問題はまさに最短経路問題（獲得可能なエネルギーの総量が、経路長より大きいかを判断するために最短経路を知る必要がる）であった。
次にBFSの実装について。通常は「グラフ上」のBFSがベースなようで、グラフ構造を定義する必要が別途ある。今回は「グリッド上」のBFSになるため、グリッドの定義を単に2次元ベクトルで行えば良い。グラフの定義は不要だ。と、思ったが「薬」の制約があるため単に2次元ベクトルを作るだけではダメらしい。
「薬iを使った後他の薬を使用せずに薬jに到達できる」ことを「頂点iからjに辺がある」と定義した有効グラフを作成するのが今回のベースであるようだ。
つまり全ての薬iについて、BFSを行い、薬jに対する最短経路を求める。ゴール地点に薬があれば、スタート地点の薬からゴール地点の薬まで辺が繋がっているかどうかを調べて"Yes"か"No"を出力すれば良い。ゴール地点に薬がない場合は？ 解説では「ゴール地点に仮想の薬」を追加してしまうのが実装上楽であると紹介している。確かに、ゴール地点の薬に関してはエネルギーがいくつであっても影響しないので、勝手に追加してしまっても問題ないということだ。
解説を読み、内容を理解しても、ここまでを本番の1時間程度で解けるようになるためには中々ハードルがありそうだと感じる。単純に問題を読み解き、条件を整理した上で、必要となる知識を引っ張ってきて、それを実装という形に落とし込み、更に細かい制約条件を踏まえた上で、正しい答えを出力する必要がある。
一朝一夕でできるようになることではないなと思う。茶コーダーを目指す上でD問題への必要性はさほど高くなく、優先度については後回しでいいと思っているが、いずれ向き合う必要がある。
E問題以降
D問題の理解で頭一杯になってしまったので、今回E以降はスキップとする。
今日の記事は以上。来週は3完の速度を高め、6000位・パフォ400以上を目指す！
