見出し画像
Photo by growseeds

2023年1月時点においてAtCoder茶色になるために必要だと考える能力

Yuta


私は2022年の中頃からAtCoderに本格的に取り組もうと考え、2022年の11月にAtCoderにおいてようやく緑色になることができました。(AtCoderアカウント)


そこまでかなり苦労しましたが、茶色に入った後に停滞感を感じて挫折ししばらくして復活した時には一度灰色まで戻ってしまいました。


AtCoderのコンテストは私個人としては近年のIT企業の就職人気もあり、どんどん参加者のレベルが上がっているように感じています。


それによりコンテストに参加してみようと思った競プロの初心者が茶色までいくのはかなり難しいことだと思います。(ちょくだいさんのブログによると茶色は上位50%)


そこで今回は最近のコンテストの問題などをみながら、AtCoderで茶色になるために必要な能力について考えてみようと思います。


前提


まず最初に私は茶色になるためには、茶diffの問題を本番で解けるようになることが一番の近道であると考えています。


それができたら苦労しないという声が飛んできそうですが、早解きによるレートの上昇は問題と問題の間に難易度の壁がないと難しいですし、何より安定したパフォーマンスにつながりません。
そこで2023年1月21日時点でAtCoder Problemsなども見ながら、直近10問の茶diffの問題からどのような知識が必要になるかを見てみようと思います。


これより下には問題の解法や考え方のネタバレが含まれますので、自分で問題を解きたい方はご注意ください。


直近の茶diff10問を解くためにキーとなるポイント


ABC285 D - Change Usernames(Difficulty: 663)


この問題はグラフの閉路存在判定が鍵となります。


制約に注意しながらDFSやUnionFindをすると解けますが、ある程度の考察が必要になるでしょう。


必要になる知識、能力


  • 深さ優先探索(DFS)

  • UnionFind

  • グラフの閉路判定


ABC284 D - Happy New Year 2023(Difficulty: 658)


この問題の鍵は、少なくとも1つの素因数はNの三乗根以下にあることに気づくことです。


よってNの三乗根まで試し割りをすることで答えを導くことができます。


必要になる知識、能力


  • 素因数分解


ABC283 D - Scope(Difficulty: 453)


この問題は括弧の括りごとにStack(もしくは配列)を用意して、括弧の終わりで今の括弧の括りに入っている文字を未使用に戻す、文字を既に箱に入れたかの判定を行うことで解くことができます。


ある程度の考察力が必要な問題と言えるでしょう。


必要になる知識、能力


  • Stack(vectorのpush_back, pop_backでも良い)

  • map(連想配列)

  • 考察力


ABC279 D - Freefall(Difficulty: 766)


この問題は与えられた関数が凸関数であることに気づいて、三分探索を行うことで解くことができます。


必要になる知識、能力


  • 関数に関する知識

  • 三分探索


ABC278 D - All Assign Point Add(Difficulty: 559)


純粋にシミュレーションすると、クエリ1において毎回配列サイズの処理が走るためTLEしてしまいます。


この問題はさまざまな解き方があると思いますが、例えば下記の手順で解くことができます。


ある程度の考察力が求められる問題だと思います。


  • クエリ2で各インデックスの差分と、差分が追加された配列のインデックスの集合を保持しておく-

  • クエリ1でその集合をリセットし、変更後の値を保存しておく

  • クエリ3が呼ばれた時にクエリ1が呼ばれていなければ、A[i] + diff[i]、呼ばれた後で差分が追加されたインデックスの集合にクエリの値があればA[i] + diff[i]、なければA[i]


必要になる知識、能力


  • 集合を表すデータ構造(set)

  • 考察力


ABC277 C - Ladder Takahashi(Difficulty: 540)


この問題はvectorを使った隣接リスト方式だとTLEするのでmapを使ってグラフを表現し、DFSをすることで解くことができます。


必要になる知識、能力


  • map(連想配列)

  • 深さ優先探索(DFS)


ABC277 D - Divide by 2 or 3(Difficulty: 645)


この問題は下記の手順で解くことができます。


  • まず配列の最大公約数gを求める

  • 各配列の値をgで割ったあと、それぞれ2と3で割り切れる限り割りながらそれらの操作回数を求める

  • もしも割り切った後に配列の値が1でないものがあれば実現不可能

  • そうでなければ操作回数の合計を出力


必要になる知識、能力


  • 最大公約数

  • 素因数分解


ABC275 C - Counting Squares(Difficulty: 760)


この問題はset<set<pair<int, int>>>のようなデータ構造を作って正方形の頂点が重複しないように気をつけながら全探索をすることで解くことができます。
うまくやらないとめちゃくちゃ面倒くさい問題です。


私自身何回かWAを出しながら何とかコンテスト中にACすることができました。


必要になる知識、能力


  • 考察力

  • 全探索


ABC275 D - Yet Another Recursive Function(Difficulty: 606)


この問題はN=0なら1をベースケースとしてメモ化再帰を行うことで解くことができます。
引数の種類数が限られているので、保存しておけば大きな数にはならないということも計算量解析を行う上で考慮できると良いでしょう。


必要になる知識、能力


  • 再帰関数

  • 動的計画法(メモ化)


ABC270 C - Simple path(Difficulty: 625)


この問題はXから深さ優先探索をしながら今のパスを配列に記録しておくことで解くことができます。
もしYに辿りついたらその時点でのパスを答えとすることでACできるでしょう。


必要になる知識、能力


  • 深さ優先探索(DFS)


上記から推測できる必要な要素、能力


上記の10問を見てきましたが、茶diffの問題を解くためには下記の能力が必要になるだろうと考えます。


  • 深さ優先探索、再帰関数

  • 素因数分解、素数判定

  • map(連想配列)

  • set(集合)

  • UnionFind

  • 三分探索(二分探索も)

  • 問題を読み解く考察力

  • 閉路、パスなどグラフに関する知識

  • Stack


その他に上記の問題にはない下記の要素もある程度抑えておくことが必要だと考えます。


  • 幅優先探索(BFS)

  • Queue

  • 優先度付きキュー(priority_queue)

  • 累積和

  • 比較的簡単な動的計画法

  • bit全探索

  • 順列の列挙


特に最初は補正がかかるため、コンテストでレーティングが上がりにくく大変だと思いますが、地道に問題を解くことで道が拓けてくると思います。


この記事が気に入ったらサポートをしてみませんか？