AtCoder Beginner Contest 290 に参加しました＆反省会
AtCoder Beginner Contest 290 の振り返り
- A、B問題を解くことができた
- A問題：
を配列で受け取り、
の数字を添え字として
で総和を計算する(0相対に直す)- B問題：受け取った文字列を先頭から見ていく
- C問題：手が出ず
- D問題：愚直に問題文に沿って実装すると5ケースがTLEとなった
A問題
方針
- 変数
を準備し、
で初期化する
- 各
に対して、
に
]を加算する
B問題
方針
- 文字列を前から見て先頭から
個以降の
oをxに書き換える
解説*1から
実装例
for(auto &nx : s){ if(nx=='o'){ if(k<=0){nx='x';} k--; } }
&nxとすることで書き換え- 書き換えるたびに
の値を減算する
C問題
解説*2から
を
以上にするには
を
まで、以下を繰り返す。
- もし
以上となることが確定する。
- そうでない場合、
- もし
- 上記が終了しても答えが判明しなかった場合、
の並べ替えとすることができているので、答えは
である。
実装例
int main(){ int n,k; cin >> n >> k; set<int> st; for(int i=0;i<n;i++){ int a; cin >> a; st.insert(a); } for(int i=0;i<k;i++){ if(st.find(i)==st.end()){ cout << i << "\n"; return 0; } } cout << k << "\n"; return 0; }
D問題
方針
- 問題文を愚直に実装する
int main () { int t; cin >> t; for (int i = 0; i < t; i++) { int n, d, k; cin >> n >> d >> k; vector<bool> mark(n, false); mark[0] = true; int count = 1; int last_mark = 0; for (int j = 0; j < n; j++) { if (count == k) { cout << last_mark << endl; break; } int x = (last_mark + d) % n; while (mark[x]) { x = (x + 1) % n; } mark[x] = true; last_mark = x; count++; } } return 0; }
解説*3から
- この問題を解くには以下の事実を知っておく必要がある。
を正整数とし、
の最大公約数を
とおく。
と表されるとき、
の個数
の中には、
(すなわち
以上
回ずつ現れる。
- 最大公約数が
のときマスは一度もかぶらずに印をつけられる。それ以外のとき既に印がついているマスになり、
したマスに印をつける。
- 最大公約数
が
以上のとき次の通りになる
番目に印をつけるマスは
であり、これによって
であり、これによって
であり、これによって
- (以下同様)
というように操作が進む。よって
]
と計算できる。
実装例
#include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n, d, k; cin >> n >> d >> k; --k; int a = n / gcd(n, d); cout << (long long) d * k % n + k / a << '\n'; } }
