AtCoder Beginner Contest 285 に参加しました＆反省会
- AtCoder Beginner Contest 285 の振り返り
- A問題
- B問題
- C問題
AtCoder Beginner Contest 285 の振り返り
- A問題のみ解けた
- A問題で
識別されないトークンですと全角が入っているらしきエラーが出て、その原因を探すのに時間が溶けた。結局別のファイルにコーディングすることで解決した→リネームしたらエラーが解消された！？（一応の対策として全角スペースを検知するvscodeの拡張機能zenkakuを導入した。全角スペースが原因とは確定していないが）
上とは別に別の箇所で==と=を間違えていた - B問題：問題文が理解できない
- C問題：アルファベットを数字に置き換える。26進数として扱えそうだが
- 紙に書き出して問題文、考えをまとめる
- A問題のエラーが解消できない・時間が溶ける・B問題が理解できないでパニックになった
AtCoder Beginner Contest 283 に参加しました＆反省会
- AtCoder Beginner Contest 283の振り返り
- A問題
- B問題
- C問題
- D問題
AtCoder Beginner Contest 283の振り返り
- コンテスト前にC++の開発環境を入れたコンテナにvscodeからアクセスできなくなり、miでコーディングした
- A、B問題は解けた
- A問題：for文で入力の回数だけ乗算する（提出時間04:42）
- B問題：配列の添字と問題文とのずれに気が付くのが遅かった（提出時間41:15）
- C問題：入力値を文字列として扱い処理する。２ケースだけWAになった
- D問題：整数ｊをどう求めるかで手が止まった。入力値を変数に格納し忘れるミスを犯した
AtCoder Beginner Contest 278にバーチャル参加しました＆反省会
AtCoder Beginner Contest 278の振り返り
- A、B問題は解けた。
- A問題：配列の先頭の要素を削除するメソッドが分からず検索に時間がかかった。
- B問題：実装に時間がかかったが考え方は正しかった。
- C問題：連想配列でフォロー、被フォロー関係を管理していくのだろうが、相互のフォローをどう確認するかがわからなかった。
- D問題：愚直に配列の要素を変更するクエリを実行する実装にしたが、２ケースでTLEになった。要素数が一定以上になると制限時間に引っかかるようだ。別の実装を思いつけず断念した。
A - Shift
考えたこと
- 配列の先頭の要素を削除する
- 末尾に0を挿入する
//aはvectorの変数 a.erase(a.begin()); //aの先頭の要素を削除 a.push_back(0); //aの末尾に0を追加
erase関数は要素の位置・範囲を指定して削除できる
std::vector<int> v = {1, 2, 3, 4, 5}; // 2番目の単一要素(値3)を削除 v.erase(v.begin() + 2); // {1, 2, 4, 5} std::vector<int> v = {1, 2, 3, 4, 5}; // 範囲[v.begin(), v.begin() + 2)の要素を削除 v.erase(v.begin(), v.begin() + 2); //{3, 4, 5}
https://cpprefjp.github.io/reference/vector/vector/erase.html (C++日本語リファレンス)
配列を出力する
for (int i = 1; i <= N; i++) { cout << A[i] << (i == N ? "\n" : " "); }
B - Misjudge the Time
考えたこと
- hの10の位Aと1の位Bを整数除算と剰余算を利用して求める
- mの10の位Cと1の位Dも同様に求める
- ACとBDを加算・乗算を利用して計算する
- 0≤AC≤23 かつ 0≤BD≤59 が成り立つかを調べる
- 成り立たない場合、ループ構造で1分ずつ加えて、繰り上がり処理に注意する
C - FF
考えたこと
- 連想配列でフォロー、被フォロー関係を管理する
解説*1より
フォロー関係を集合Sに保持することを考える。与えられるクエリは次のように言い換えられる。はじめ、S=∅ 。
1. 集合 S に順序対 (A,B) を追加する。つまり、S←S∪{(A,B)} とする。
2. 集合 S から順序対 (A,B) を取り除く。つまり、S←S∖{(A,B)} とする。
3. 順序対 (A,B),(B,A) がいずれも S に含まれているかを判定する。
// フォロー関係を保持する集合 set<pair<unsigned, unsigned>> follows; // 順序対 (A, B) を追加 follows.emplace(A, B); // 順序対 (A, B) を削除 follows.erase({A, B}); // 順序対 (A, B), (B, A) がどちらも含まれるか判定 // count()は引数を要素に含む場合１、含まない場合０を返す。それぞれtrue/false (follows.count({A, B}) && follows.count({B, A}) ? "Yes" : "No" )
D - All Assign Point Add
考えたこと
- クエリ１を愚直に実行し、配列を初期化する
→今回の要素数Nは2×105、クエリ１を実行するたびに最大2×105操作することになる
→クエリ１も最大2×105なので計算量は4×1010
→実行できる計算量の目安が108なのでTLEになる
対応
- クエリ１で全要素を初期化するのではなく、初期化する値を保持するだけに留める
- 変数baseだけで配列の情報を管理する
- クエリ２で増加する値を差分diffsとする
- クエリ３で出力されるのはbaseとdiffsの和となる
int main() { int N; cin>>N; int base = 0; map<int, long long> diffs; //mapだと初期値が0になるので都合が良い for (int i = 1; i <= N; i++) cin >> diffs[i]; //クエリ実行前の入力値を保持 int Q; cin>>Q; for (int q=0; q<Q; q++) { int query; cin >> query; if (query == 1) { int x; cin >> x; base = x; diffs.clear(); //baseに代入したため } if (query == 2) { int i, x; cin>>i>>x; diffs[i] += x; } if (query == 3) { int i; cin >> i; cout << base + diffs[i] << endl; } } }
AtCoder Beginner Contest 282に参加しました&反省会
AtCoder Beginner Contest 282の振り返り
- A・C問題は解くことができたが、B問題は落とした
- A・C問題ともに方針こそ合っていたがスムーズな実装とはいかず、時間がかかった
- B問題でエラーの発生箇所を見誤り時間を浪費した
A - Generalized ABC
考えたこと
- 入力に応じてchar型のA、B、Cと結合し最後にまとめて出力する（実装例では都度出力）
→char型の初期値をAにし、for文で回す
→for文の初期値を誤ったために、いらないif文が必要になった
実装例
for(int i = 0; i < k; i++) {
cout << char('A' + i);
}
string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
cout << s.substr(0, K) << endl; //Kは出力する個数
B - Let's Get a Perfect Score
考えたこと
- 与えられた文字列をfor文で回す
- ２つの文字列を比較し、文字列すべてでどちらかが'o'だったらカウントアップする
実装例
// nは人数、mは問題数、resは解答を格納する変数
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
bool ok = true;
for (int k = 0; k < m; k++) {
if (s[i][k] == 'x' && s[j][k] == 'x') ok = false;
if (ok) res += 1;
}
}
}
C - String Delimiter
考えたこと
"が１つのときは括られた文字列扱いする"でtrue/falseを切り替える- 括られていない
,の位置を配列に格納しまとめて.に置換する
→replaceメソッドを使ったが、for文中で代入するだけで済むようだ
AtCoder Beginner Contest 281に参加しました&反省会
AtCoder Beginner Contest 281の振り返り
- A,B問題は解くことができ、C,D問題は解答方針だけ立てることができました
- B問題に時間を取られました
- コンテスト開始前にエディタの起動など必要な環境を準備しておく
B - Sandwich Number
考えたこと
- 入力サイズは８
- 入力値の１文字目と８文字目がA-Z
- 入力値の２文字目から７文字目は数値
- 入力値の２文字目は0を除く
だめだったこと
- for文で入力の各文字について受け取り一文字ずつ判定する最初の方針に固執した
- 数値になる文字列を切り抜いて文字列から数値にする転換できるかを調べようとした
- 都度条件を満たすかで真偽値を切り替えており、一度falseになっても後の条件でtrueになることで誤答になった→初期値をtrueに、条件を満たさない場合にfalseに設定する
実装例で覚えておきたいもの
- char型は文字コードに対応した英数字を格納する
'A' <= c and c <= 'Z' '0' <= c and c <= '9'
- 配列の先頭・末尾を取得する
std::string s; s.fornt(); s.back();
- Yes/Noの出力に三項演算子を利用する
bool flag; cout << (flag ? "Yes" : "No") << '\n';
- 存在しない配列の要素にアクセスする（今回だと要素数が8より小さい場合）
string s = "hello"; s.at(7); //例外が発生 s[7]; //例外は発生しない
C - Circular Playlist
考えたこと
- 楽曲のループについては、与えられた時間をプレイリストの総時間数で割ることで解決できる
- 上で導いた残り時間からプレイリストの楽曲の時間だけ引いていけば曲と時間を導けられそうだが →残り時間と楽曲を比較：超過した場合残り時間-楽曲で求められる
考慮漏れ
- 入力値がintの範囲を超える数値になるのでlong long型を使う
実装例から覚えておきたいもの
- 範囲を集計する関数：accumlate()
accumulate()は、範囲を集計する関数である。 初期値(init)に対して、範囲[first, last)の各要素iを前から順番に、任意の二項演算関数binary_opをinit = f(init, *i)のように適用していき、範囲の< 全ての要素を集計した結果を戻り値として返す。
const std::vector<int> v = {1, 2, 3, 4, 5};
// (1) : 合計値を求める
int sum = std::accumulate(v.begin(), v.end(), 0);
std::cout << "sum : " << sum << std::endl; //sum: 15
