📝

AtCoder青色を目指してみた#7

に公開
AtCoder
tech

はじめに

非情報系の大学院生（M1）が、AtCoder青色（Rate 1600）を目指す記録です。
今週は ABC453 のコンテストに参加しつつ、典型90問にも本格的に着手しました！
だんだん考察力がついてきて、D・E問題を解ける機会が増えてきているのでとても楽しいです。

今週のコンテスト結果

項目 内容
コンテスト ABC453
結果 3完 (A, B, C)
現在レート 642(+51)
パフォ 997

振り返り（KPT）

今回のコンテストではD問題を解くことができなかった。
しかし、WA になっても考察自体の精度は確実に上がってきていることを実感しています。

  • Keep（良かったこと）:

    • A〜C問題を素早く解くことができた
    • D問題について、正確な考察をすることができた

  • Problem（課題）:

    • DFSの訪問管理においてsetを使ってしまいTLEをしてしまった
    • 再帰関数の終了の伝播の実装ができずTLEをしてしまった

  • Try（今後の改善策）:

    • 訪問管理においては必ず配列を使う
    • グローバルに終了フラグを管理して、再帰関数の呼び出し直後に必ず終了判定を行う

今週取り組んだ学習

今週はメインとして典型90問を進め、コンテスト前後に過去問精進も行いました！

取り組んだ問題数

今週は計 25問 に取り組んだ。

カテゴリ 問題数
典型90問 14問（001〜021 のうち 14問）
コンテスト（ABC453） 4問
過去問精進（ABC） 7問

典型90問

001〜021 の番号帯（一部飛ばし）に取り組んだ。二分探索・スタック・BFS・累積和・DP・Dijkstra・UnionFind・SCC など幅広いアルゴリズムを確認できた。

コンテスト・過去問の振り返り

✅ ABC452-E ― 解説AC

  • E は累積和を活用した計算量削減の問題（各 j に対し \sum_k \lfloor n/(kj) \rfloor を高速に計算）。
  • 学び： ガウス記号はとりあえず外してみる。「j の倍数ごとのブロック和」をまとめる整数除算テクニックを復習。

✅ ABC453-C（グリッド・全探索） ― AC

  • 長さ N の配列の全ての部分集合を試し、飲み物の残量が 0 を跨ぐ回数を最大化する問題。
  • ビット全探索 + シミュレーション。
  • 学び： 「符号が反転する回数を数える」には 前フラグと現フラグを比較 するパターンが有効。

✅ ABC453-D（グリッドDFS・バックトラック） ― 解説AC

  • グリッド上を特定の方向制約に従って移動し、ゴールへの経路を出力する問題。
  • バックトラック DFS で方向情報 (visited[r][c][d]) まで状態に含めることで無限ループを回避。
  • 学び： グリッド DFS で方向も状態に含めることで、同じマスへの再訪を方向別に管理できる。

✅ ABC440-D（二分探索） ― AC

  • ソート済み配列から「[x, ?] の範囲に含まれない整数がちょうど y 個以上ある最小の右端」を求める問題。
  • 二分探索 + 区間内の配列要素数を lower_bound/upper_bound で計算。
  • 学び： 「個数 ≥ k」の条件を二分探索に落とす際、区間内の存在数を upper_bound - lower_bound で O(\log N) で求める。

✅ ABC164-D（累積和・剰余） ― AC

  • 部分文字列が 2019 で割り切れるペアを数える問題。
  • 累積和を 2019 で割った余りの cnt 配列を作り、同じ余りのペア数を \binom{cnt[r]}{2} で数え上げ。
  • 学び： 部分和の余りが等しい = 区間和が割り切れる。cnt[r] * (cnt[r]-1) / 2 で O(mod) に集計できる。

✅ ABC230-E（数学・整数） ― AC

  • 1 \le i \le N の総和 \sum_{i=1}^{N} \lfloor N/i \rfloor を求める問題。
  • \lfloor N/i \rfloor の値が等しい i の区間をまとめる整数除算テクニック（商の連続性）。
  • 学び： \lfloor N/i \rfloor = q となる最大の i は \lfloor N/q \rfloor → O(\sqrt{N}) で計算可能。

❌ ABC449-E（数学） ― WA（未解決）

  • 先週から持ち越し。全ての要素を均等化する構造は見えているが、式への落とし込みが不完全。
  • → 要復習。

今週の教訓まとめ

  • 🛑 （行動ルール）: DFS では訪問管理に visited[r][c][direction] 配列を使うことで TLE を防ぐ
  • 🧠 （思考パターン）: 「個数 ≥ k」の条件は二分探索に落としやすい。区間内要素数は upper_bound - lower_bound で O(log N)
  • 🧠 （思考パターン）: 部分和の余りが等しいペアを数えるには、余りごとの cnt 配列 + 組み合わせ数の公式
  • 🧠 （思考パターン）: \lfloor N/i \rfloor が同じ値を取る i の区間をまとめる整数除算テクニックで O(\sqrt{N})
  • 🧠 （思考パターン）: 符号が反転する回数を数えるには「前フラグと現フラグの比較」パターンを使う

来週の目標

  • 典型90問を 040 番台まで進める
  • ABCのD問題を初見で解き切る
  • ABC449-E を解き直す

まとめ

今週は ABC453コンテストに参加しました！ABC453 では D 問題まで考察できましたが惜しくも 3 完。典型90問にも本格着手し、基礎アルゴリズムの引き出しが着実に増えています。引き続き頑張ります！

Discussion