ABC162に参加しました
AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら
解いた/挑んだ問題
A問題
問題の概要
3桁の整数N(100 ≤ N ≤ 999)が与えられる。
Nのいずれかの桁に'7'が含まれたら'Yes'を、含まない場合'No'を出力する
どのように考えたか
Nを受け取り、if文の中で一の位、十の位、百の位をそれぞれ比較してあげればいい。
条件式に当てはまったら'Yes'、それ以外(当てはまらない)なら'No'を出力する。
結果
WA一回した後にACしました。
各桁から、7を抽出する際の計算ミスにより、1WAを出しました。
・問題のコード
if (n % 100 == 7 || n % 10 == 7 || (n / 10) % 10 == 7) { cout << "Yes" << endl; } else { cout << "No" << endl; }
ifの条件式の中身ですが、左から百の位と7を比較、一の位と7を比較、十の位と7を比較 と実装したつもりでした。
ですが百の位の抽出の仕方に誤りがあり、下二桁の数値を抽出してしまいました。
コンテスト中で最近伸び悩んでいる点もあり、比較順序も百の位、一の位、十の位となんだかすっきりしません。
焦りからくるミスだと思っているので、ぜひ改善していきたいです。
ACまでの時間
ACしたのはコンテスト開始から12分後です。
ジャッジサーバが重く、判定の最中にB問題をやっていたため、遅れてしまいました。
B問題
問題の概要
整数N(1 ≤ N ≤ 10^6)が与えられる。
Nまでの数で、3でも5でも割り切れない数の和を出力せよ。
どのように考えたか
1からNまでfor文で回し、if文で3でも5でも割り切れない数の場合、変数sumにその数を足す。
結果
一発ACでした。
条件式はA問題より簡単なのではないかと思います。
提出したコード
#include "bits/stdc++.h" using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) int main() { long long n; cin >> n; long long sum = 0; for (int i = 1; i <= n; i++) { if (i % 3 != 0 && i % 5 != 0) sum += i; } cout << sum << endl; }
repマクロの初期値などを自分で調整できるものを書いておこうかと思いました。
ACまでの時間
ACしたのはコンテスト開始から9分後です。
今後もっと早く解けるようになりたいです。
C問題
問題の概要
整数K(1 ≤ K ≤ 200)が与えられる。
1 ≤ a,b,c ≤ Kを満たすすべての整数a,b,cの組に対してのa,b,cの最大公約数の総和を求めよ。
どのように考えたか
一番初めに頭に浮かんだのはTLEの3文字でした。
3重ループなんかして大丈夫なわけないし(これが間違い)計算量削減か法則性を見つけようと思いました。
とりあえず全列挙してみたり、素数が含まれていたら1を返させたり、、、
最大公約数に関してはgcd(gcd(a,b),c)で求まることを確認しました。(実装しなくて済むから楽ちん)
結果
悩み悩んだ末2完はつらいと思い意を決して計算量削減していない3重ループで提出したらあっさりACしました。
出してみるもんですね、、、
・提出したコード
#include "bits/stdc++.h" using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) int main() { long long sum = 0,tmp = 0; int n; cin >> n; for (long long i = 1; i <= n; i++) { for (long long j = 1; j <= n; j++) { for (long long k = 1; k <= n; k++){ tmp = gcd(gcd(i, j), k); //cout << i << " " << j << " " << k << " " << tmp << endl; sum += tmp; } } } cout << sum << endl; }
最大公約数の全列挙の跡が残っています。
変数tmpはその為です。
ACまでの時間
ACしたのはコンテスト開始から76分後。
200^3ではTLEにならないといういい経験となりました。
D問題
問題の概要
'R','G','B'のみからなる長さN(1 ≤ N ≤ 4000)の文字列Sが与えられる。
・文字列から'R','G','B'をそれぞれ重ならないよう選択
・選択した各文字の、Sでの位置の間隔が等しくない
を満たす組の数を答えよ。
どのように考えたか
盛大な勘違いをした問題で、この後読まなくていいレベルです。
Sでの各文字の位置を配列に格納(間違い)した後三重になったfor文で配列の中身を全部出力、一番内部で問題の制約を確認(この後のコードではしていません)
結果
ACは出ずWAのままコンテスト終了を迎えました。
コンテスト終了後に気づくのですが、おかしいコードを書いていました。(配列が全要素出ない)
また、文字列中の特定の文字を数える場合の簡単な方法をACした方のコードから学びました。
・提出したコード
#include "bits/stdc++.h" using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) int main() { vector<int>R, G, B; string S; int N,sum=0; cin >> N >> S; rep(i, N) { if (S.substr(i, 1) == "R") R.push_back(i + 1); if (S.substr(i, 1) == "G") G.push_back(i + 1); if (S.substr(i, 1) == "B") B.push_back(i + 1); } rep(i, R.size() - 1) { rep(j, G.size() - 1) { rep(k, B.size() - 1) { sum++; } } } cout << sum << endl; }
ACまでの時間
コンテスト終了から約3時間後。
ACした人のコードや解説を見ながら問題の本筋を理解し何度もトライしました。
結果
コンテスト結果
ABCの3完でした。
最近3完しかできておらず伸び悩んでいるのでDも安定して解けるようになりたいです。
順位、パフォーマンス変動
順位は前回より1000近く下がり7804位、レーティングも下がってしまいました。
反省点
条件式を間違ってしまったことや、TLEになる目安を把握していなかったこと、問題文の理解を誤ったこと様々ありますが、これもすべて焦りからくるものだと思っています。
茶色が見えてきて早くなりたい、最近伸び悩んでいるという思いから、早く解いてレーティングをあげようと張り切り、その結果ミスを連発してしまいました。
焦らず、着実に力をつけて茶色を目指していきたいと思います。