今回の成績
AB 正答
（全体的に難しかった）
A問題
自分の回答
int main()
{
int N;
cin >> N;
vec<str> S(N);
FOR(i, N)
cin >> S[i];
int X;
str Y;
cin >> X >> Y;
cout << ((S[X - 1] == Y) ? "Yes" : "No") << endl;
return 0;
}
振り返り
前回の反省を活かして、少し丁寧に見直した。
無事一発正解。
B問題
自分の回答
static ull calc_next(ull lhs, ull rhs)
{
ull x = lhs + rhs;
str x_as_str = to_string(x);
reverse(all(x_as_str));
ull rev_x = stoull(x_as_str);
return rev_x;
}
// index : 1-based
static ull calc(ull a1, ull a2, int index)
{
if (index == 1)
return a1;
if (index == 2)
return a2;
FOR(i, index - 2)
{
ull next = calc_next(a1, a2);
a1 = a2;
a2 = next;
}
return a2;
}
int main()
{
ull X, Y;
cin >> X >> Y;
ull lhs = X;
ull rhs = Y;
ull ans = calc(lhs, rhs, 10);
cout << ans << endl;
}
振り返り
やることをメソッドに分割して、整理しながら作れた印象。
無事一発正解。
C問題
途中までの回答
ull impl(const str &s, int length)
{
vec<char> c(all(s));
ull cnt = 0;
while (true)
{
bool should_do = false;
FOR(i, length)
{
if (c[i] == c[i + 1])
{
should_do = true;
break;
}
}
if (!should_do)
break;
std::set<int> sep_left_indexes;
FOR(i, length - 1)
{
if (i == 0)
continue;
if (c[i - 1] == c[i] && c[i] != c[i + 1])
{
if (sep_left_indexes.find(i + 1) == sep_left_indexes.end() && sep_left_indexes.find(i - 1) == sep_left_indexes.end())
sep_left_indexes.insert(i);
}
}
cnt += sep_left_indexes.size();
for (int i : sep_left_indexes)
{
char tmp = c[i];
c[i] = c[i + 1];
c[i + 1] = tmp;
}
cout << "===\n";
for (int i : sep_left_indexes)
cout << i << " ";
cout << "\n";
for (char ch : c)
cout << ch;
cout << "\n";
cout << "===\n";
}
return cnt;
}
int main()
{
int N;
cin >> N;
str S;
cin >> S; // 2N
cout << impl(S, N << 1) << endl;
}
振り返り
どういうアルゴリズムでやればいいのか、分からなかった。
解説にあった「2パターン試し、最小の方を取る」考えはあったが、そこからが詰まってしまった。
残り60分くらいになったので、解くのは諦め、DEFG問題に移る。（これはいい判断だと思う）
DEFG問題をザッと見てみる
難しいの多くね？？と困惑。
クエリ系のアルゴリズムが比較的得意なので、F問題に狙いをつけ、残り時間を使って取り組む。
コンテスト後の解説を見ても、F問題以外は言っていることがよく分からなかった。
F問題
自分の回答 1回目
案の定、実行時間超過。
int main()
{
vec<int> A;
A.reserve(1e5);
A.push_back(0);
int Q;
cin >> Q;
FOR(j, Q)
{
int type;
cin >> type;
if (type == 1)
{
int x;
cin >> x;
for (int i = 0; i < A.size(); ++i)
{
if (A[i] == x)
{
A.insert(A.begin() + i + 1, j + 1);
break;
}
}
}
else
{
int x, y;
cin >> x >> y;
auto it_x = find(all(A), x);
auto it_y = find(all(A), y);
if (it_x > it_y)
swap(it_x, it_y);
int sum = reduce(it_x + 1, it_y);
A.erase(it_x + 1, it_y);
cout << sum << endl;
}
// cout << "A: ";
// for (auto a : A)
// cout << a << " ";
// cout << endl;
}
}
自分の回答 2回目
find系の処理を軽量化しようと、インデックス配列的なものにしてみた。
結果、全く高速化されなかった。残念…。
時間が経つのは早く、この提出でコンテスト時間終了。
int main()
{
int Q;
cin >> Q;
// jがAのインデックスの何番目にあるかを記録するメモ
// int index = indices[i] : 数字iがAのindex番目にある
// -1なら無い
vec<int> indices(Q, -1);
indices[0] = 0;
for (int j = 1; j <= Q; ++j)
{
int type;
cin >> type;
if (type == 1)
{
int x;
cin >> x;
int idx = indices[x] + 1;
for (int k = 0; k < j; ++k)
{
if (indices[k] >= idx)
++indices[k];
}
indices[j] = idx;
}
else
{
int x, y;
cin >> x >> y;
int x_index = indices[x];
int y_index = indices[y];
if (x_index > y_index)
swap(x_index, y_index);
int sum = 0;
for (int k = 1; k < j; ++k)
{
int idx = indices[k];
if (x_index < idx && idx < y_index)
{
sum += k;
indices[k] = -1;
}
}
cout << sum << endl;
}
// vec<int> A;
// A.reserve(j);
// for (int idx = 0; idx <= j; ++idx)
// {
// for (int k = 0; k < indices.size(); ++k)
// {
// if (indices[k] == idx)
// {
// A.push_back(k);
// continue;
// }
// }
// }
// cout << "A: ";
// for (int a : A)
// cout << a << " ";
// cout << endl;
// cout << "I: ";
// for (int i = 0; i <= j; ++i)
// cout << indices[i] << " ";
// cout << endl;
}
}
振り返り
解説にあった連結リストの方法を使いたかった。
自分に解ける難易度ではあったが、けっこう頭を使って書かなければいけないので、そんなにたくさん試行できないのが辛いところ。
DEFG問題に関しては、「方針を立ててやってみる」サイクルを3回くらいしか出来ないものと思ったほうが良いか。
総括
難しい問題が多かったので、とりあえず最初の2問を完答出来たのはヨシ！
C問題に見切りを付けたのも、いい判断だと思う。（F問題の方が簡単だった）
思ったより時間は短く、そんなに試行できない ので、一回一回の方針立て・提出を丁寧にしたい。
次回も頑張ろう！