先日、3/30のABCに約1年と3ヶ月ぶりに参加した。
結果はABの2完。
本記事ではC問題までについて、思考や解法を振り返る。
ただ、初回記事なので先に筆者のプロフィールについて軽く触れておく。
参加の動機・AtCoder歴
参加した動機としては「プログラミング力を向上させたい」「第三者から見て客観的に分かるプログラミング力の評価指標を得たい」の2点。
今後も継続的に参加する所存。
筆者の現状の参加回数は4コンテストでRatingは69。
Rated登録だけして不参加が5回あるので、記録上は9回参加している。
パフォーマンスが100を超えていない時期（23/1/15~23/6/10）が「Rated登録だけして不参加」に該当する。
1問も提出していないのにパフォーマンスが0ではないのは不思議だ。パフォーマンスはどのように算出されてるのだろうか？
なぜ参加しなかったのかは覚えていない。「AtCoderに取り組みたい」という意思はあったものの「何か予定があって参加しなかったか」「当日になってやる気が湧かずに参加しなかった」のだと思う。
今後はこのようなことがないよう「土曜の21時-23時には予定を空ける」「当日になってやる気が湧かなくならない工夫を考える」等をしていこう。
当面の目標はRating400、茶色への到達。
レベル感については正直分かっていないが、高橋氏の過去のポストを拝見するに、短くても「2ヶ月」は掛かると書いてある。
「普通の人が茶色になるにはどれくらい時間がかかりますか？」ってめちゃめちゃ多い質問なんだけど、その人の「普通」によって、マジで違います……。
— chokudai(高橋 直大)@AtCoder社長 (@chokudai) 2020年7月11日
コンテストにある程度数は出ないと無理なので、まぁ短くても「普通は」２ヶ月は見ておかないとダメで、長い方はマジで人によるのでなんとも……。
これを見るに「ある程度の熱意と技術がある人が毎週参加すれば2ヶ月で茶色になれる」のかなという気がする。
現状の自分は「熱意=ある（自認）」「技術=勉強中、初学者」という感じなので、2ヶ月で茶色になるのは85%くらい無理な気はするが、分かりやすさとチャレンジ精神重視で「2ヶ月後までに茶色になる」ことを目標に掲げようと思う。
即ち、3/30のABCを含めて合計8回の参加で茶色になることであり、毎週参加するという前提で「5/18のコンテスト終了時のレートが400を超える」となる。
乞うご期待。
3/30 ABC347振り返り
結果：AB2完、パフォーマンス385。
17分でAB解いた後、C問題に苦戦し、解けずに終了。
AB問題についてはより早く解くために何が必要だったか、C問題については解くためにどのような知識が不足していたのかを振り返っていく。
A問題(0:00~10:53)
提出したコードは以下。
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int main() {
int N, K;
cin >> N >> K;
vector<int> A(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
for (int i = 0; i < N; ++i) {
if (A[i] % K == 0) {
cout << A[i] / K << " ";
}
}
cout << endl;
return 0;
}この問題に10分も掛かった理由としては、シンプルにC++を書くのが久しぶりだったため初歩的な書式からいちいち調べてしまっていたことである。
・vectorの定義方法がわからなくて調べた。
・forの条件文内の書式方法が曖昧だったので一応調べた。
なお、上の方でrepを定義しているにも関わらず、処理部でforをそのまま使っているのに気付いたのは終了後だった。見返すと面白すぎる。
repについては過去に使っていたC++のテンプレをコピペして使っていたのでコードには残っていたものの、当日はそれに気付かなかったのである。
以上を踏まえて、次回のA問題の目標を「5分以内に解く」とし、そのためには
・A問題で要求される範囲の基本的な書式における曖昧さを無くしておく
・for書式を使わずrepを使う
が必要そうなため、来週までに過去のA問題を10問解いて、5分以内に提出できるように書式慣れしておく。
B問題(10:53~17:15)
提出したコードは以下。
#include <iostream>
#include <set>
#include <string>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int main() {
string S;
cin >> S;
set<string> substrings;
for (size_t i = 0; i < S.length(); ++i) {
for (size_t len = 1; len <= S.length() - i; ++len) {
substrings.insert(S.substr(i, len));
}
}
cout << substrings.size() << endl;
return 0;
}当日、この問題を解く際に自分の中で曖昧だった部分は以下。
・C++におけるstd::setの取り扱い方。setは複数の要素を持つデータ構造で、重複した要素を持たないという特徴がある（既に含まれている要素をinsertしてもその操作は無視される）ため、今回のような「重複を除いて個数を数える」タスクで有用。
・C++におけるsubstrメソッドの取り扱い方。string.substr(x, y)によりstringのインデックスx番目から始めて長さyの部分文字列を抽出できる。
これらもA問題と同様、C++における基本的な作法に慣れていないのが原因。
来週までにB問題を10問解き、5分以内に提出できるよう訓練しておく。
C問題(17:15~)
非常に難しかった。最終的に提出したコードは以下だが、42/52AC-10/52TLEで通らず。
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int main() {
int N, A, B;
cin >> N >> A >> B;
vector<int> D(N);
for (int i = 0; i < N; ++i) {
cin >> D[i];
}
bool flag1 = true;
bool flag2 = false;
for (int i = 0; i < A+B; ++i) {
flag1 = true;
if (i == 0) {
for (int j = 0; j < N; ++j) {
if (D[j] % (A+B) > A-1) {
flag1 = false;
break;
}
}
if (flag1) {
flag2 = true;
break;
}
} else if (i >= 1 && i <= A-1) {
for (int j = 0; j < N; ++j) {
if (D[j] % (A+B) > A-i+1 && D[j] % (A+B) < A+B-i) {
flag1 = false;
break;
}
}
if (flag1) {
flag2 = true;
break;
}
} else {
for (int j = 0; j < N; ++j) {
if (D[j] % (A+B) < A+B-i || D[j] % (A+B) > 2*A+B-i-1) {
flag1 = false;
break;
}
}
if (flag1) {
flag2 = true;
break;
}
}
}
if (flag2) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}計算量については非常に理解が浅い。
当日は「適当に書いたらTLEになりそうだな」と思いつつ、「とりあえず叩き台としてTLEになるコードを書きそれを修正していこう」と考えて取り組んでいた。
しかし、思いの外アルゴリズムに悩まされ、ちゃんと動くコードが出来上がったのが終了7分前。提出するも案の定TLE…。残り7分で改善できる訳もなく諦めモードに入り終了。
この問題を解く際に必要だった知識を列挙してみよう。
・計算量に関する理解：制限時間2secと指定有り。実行時間が2secを上回る条件は？
・アルゴリズムに関する理解：「全ての予定が休日である可能性がある」をどう読み解くべきだったか？
計算量に関する理解
どれくらいの計算をすると2secを上回ってしまうのか？ 軽く調べてみたところ1秒当たり10^7の計算量が目安である、という記事を見つけた。
とすると、基本的にはO(10^7)以下の計算に収める必要がある。
今回自分が書いたコードでは、A+B<=2*10^9とN<=2*10^5の2重ループを回していたため、計算量はO(10^14)となる。余裕のオーバーだ…。
であれば、そもそもA+Bをループで回すこと自体が推奨されてないことが問題文に書いてあったということになる。他の多くの参加者はそれに最初から気づいて、アルゴリズムを考える指針にしていた筈。後述するが自分は「今日が1週間のi日目であると仮定し、iを1→A+Bでループ」する方針を取ったが、それが根本的に間違いだったことになる。計算量に関する知識がなかったせいで初動の方針決めの段階で大損してしまったのか。
今回で計算量に関する理解は深まったので、次回は問題を見た時点で気づけるようになっていると思う。
アルゴリズムに関する理解
前提として、DiはA+Bの単位で周期するので、事前に全てのDiをmod (A+B)で置き換えておく。
まず、自分が最初に発想した方針は以下のようなものだった。
・「「N個の予定が全て休日である」可能性を判定する」のだから、「今日」を「1日目」から「A+B日目」までで全て走査し、その内一つでも「N個の予定が全て休日である」ような「今日」があれば即座に"yes"を出力すれば良い。
→しかしこれは前項で挙げたようにO(A+B) = 10^9であるためTLEに引っかかるので方針として不適切である。
であればどうするか？ 次に思いついたのは「存在し得る「今日」の領域」を「予定」によって塗りつぶしていく方針。
例えば、A=2, B=5を考え、D1=3である状況を考える。この時、「今日」としてあり得るのは「5日目」もしくは「6日目」のみとなる。なぜなら他の日付では「3日後が休日」の条件を満たさなくなるため。
つまり、予定Diそれぞれに対し、自然数領域[1, A+B]から「今日」としてあり得る長さAの部分領域[x, x+A-1]が与えられることになる。
全ての予定Diに対して、この部分領域の共通集合を求め、長さが0でなければ題意は満たされる、というわけだ。計算量としてもO(N)で済みそう。
しかし、これを実装するに当たって面倒なのが「部分領域が2分割されることがある」ということだ。
例えばA=2, B=5, D1=1の時、部分領域は[1, 1]と[7, 7]の2つに分割される。これはDiがAより小さい場合に発生し得る。
あとは、C++で「領域の共通集合を求める」という実装をしたことがなく、、、という感じで当日は時間切れもあり断念した記憶。
この辺で一旦、解説を見てみることにする。
atcoder.jp
これを見て、なるほどなーが1つ、よく分からんが2つ。
予定について、重複を削除しソートしてもよいのには気付かなかった。これは、予定の順番が解答に影響ないため。なるほど。
ただ、証明部分がうまく飲み込めない。
ぱっと見るに「ある予定と、それより少し遅い予定について、その差がBより大きいこと」が全ての予定の内1つでもあれば題意を満たす、と主張しているように読めてしまう。これって「あるi」じゃなくて「全てのi」じゃなくて大丈夫なの？ 「全ての予定が休日である」必要があるのに、あるiについてだけ条件を満たせば良いと主張しているのが直感的に納得できなかった。
と、思ったのだが、公式解説放送の方を見に行ったら多少理解できた。
www.youtube.com
この円環を参考に自分で図を描いてみた。
上記の図は「どうしても平日に予定が入ってしまう場合」を描いている。
確かに、これを参考にすると「ある予定の次の予定との差がBより大きい組み合わせが存在しない」のが分かる。
つまり平日に予定が入ってしまうと「平日の予定」と「休日の予定の内、最初のもの」との差がBより小さくなるのだ。
で、逆に全ての予定が休日に収まる場合、差がB以上になる隣接する予定の組み合わせが必ず存在すると。
なるほどー。
理解はできたものの、ではどのような知識が必要だったのかと考えると、正直分からない。
この辺は今後C問題を解く経験を積んで、感覚を磨いていく方針でいくことにする。
実装としては、所定の処理をした後に隣接する予定の組み合わせを取り出していき、差がBより大きいものがあるかを判定していくだけ。簡単だね。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
int main() {
int N, A, B;
cin >> N >> A >> B;
int W = A+B;
vector<int> D(N);
rep(i, N) {
cin >> D[i];
D[i] %= W;
}
sort(D.begin(), D.end());
rep(i, N) D.push_back(D[i]+W);
rep(i, N) {
int l = D[i], r = D[i+1];
if (r-l > B) {
cout << "Yes" << endl;
return 0;
}
}
cout << "No" << endl;
return 0;
}AC出たので満足。
D問題以降
今回はC問題で手一杯だったので、D問題以降は一旦スキップ。
調べる感じ茶色になるにはCまでの3完ができれば十分、みたいな記事がちらほらあったので、とりあえずこれから2ヶ月の間はCまでをキッチリ解けるようになることを目指していく。
今日の記事は以上。
