競プロ初学ログ
素敵な夜ですね。
競技プログラミングの勉強を始めてから少し時間が経ったので競プロの初学についてのログを書きます。
AtCoderを使っています。
対象読者は未経験～灰レベルです。私も灰です。
これを読んだ未経験の貴方はC#で競プロを始めてください。同志がいません。
ただし、解説が大体C++です。
競プロ、AtCoder
競技プログラミングの事で、競技としてプログラミングの問題を解く事です。
AtCoderとは、そのコンテストサービスです。
現代のAtCoderについて
やってみている限り、人口の流入が激化しています。
良いことだと思いますが、なんだか高速で３完（３問完答）するか、４完しないと茶色になれないイメージを受けます。
学習の基本方針
- まず実戦or時間を測って疑似コンテスト、そして間違えたものを直す
- 過去問（教本含む）
の２パターンがあると思います。
ただ前者はC問題まである程度解けてD、Eが解けたり解けなかったりする人向けだと思います。
素人なので後者を選びました。
過去問をどこから追うか
問題傾向が固まった（※ただしレベルは固まっていない）ABC40～
色々な記事でよく例問に上がり始めるABC80～
以降全テストケースが公開されているABC100～
現在の六問制になり始めるABC126～
以上の四つが区切りとして目立ちます。
ABCのC問題全部解くぜ～と進めていた中、一番「こうしておけばよかったな」と思うのはABC080～090の後ABC126～に進む流れです。
特に～ABC125とABC126～ではC問題の難易度や立ち位置が違いすぎるので、先にABC126～をやったほうが良かったです。
いつ受験を始めるか？
１０回受けるまでは正しいレートが出ないとの事で、回数稼いでおいたほうがいいという点もあります。
ただ、勉強で後から実力を上げると、後から結局の所また何回も受験する必要が出ます。
周りを見渡すとバッチリ時間が取れるなら緑パフォまではレートが上がる速度よりも実力が上がる速度が早い気がするので、緑パフォまではABC本番はほっとくのが最適解と考えます。
この限界利益は人によって異なる事になります。
教本について
茶色レベルまでは教本は不要と思われます。ただ各教本の所感は書きます。
逆にAtCoderProblemで茶色レベル表記の問題まである程度解けるようになったら読んだほうが良いと思われます。
チーター本
中級者向け。前半は初心者でも有用。連載記事の纏めなので解説が最低限。C#のコードが有るのは嬉しい！！
ピラミッド本
中級者向け。前半は初心者でも有用。非常にわかりやすい記述だが記述内容が中級者向け。
螺旋本
初心者向け……に見える中級者向け。数学でいうと公式の証明を載せている本に思われ、平易だが初心者向けではない。
もちろん、数学をやるなら自分で公式を証明できたほうが良いのと同様そのうち勉強したいが、どう考えても今ではない。
蟻本
難易度に対して解説が簡単すぎる！！！！！
茶色になる為によく使う/欲しいもの カッコは優先度低
・小学算数、中高数学
・計算量の概念 オーダーキツイっすよ… O>10^9からが危険と言われても10^9という数字が覚えられない
・配列に記録して添字で呼び出して計算量を減らす例のやり方 よく見る
・List、Sort 特に地図の作り方 よく見る
・階乗 作っておくと楽できる
・最小公倍数、最大公約数 本番で必要になった時一から作ると遅い
・素数判定、全約数 本番で必要になった時一から作ると遅い
・全探索 よく見る
・ビット全探索 まれによく見る
（・順列総当たり 頻度は低いがたまに出る 順列を出す関数さえ持っておけば楽でその分差をつけられる様子）
（・いもす法 同じく低頻度ながら、原理が簡単なのに緑問題へのラッキーパンチが期待できる）
（・DP 優先度極低だが、公式解説がトンチの末みたいなC問題をDPで強引に解いた他の方の解答もあったりしたので そもそもダイクストラ法とかもDPの応用らしくなるべく早いうちに概念だけは知っておいたほうが後から得する気がした フィボナッチ数列への適用とか単純にクールでかっこいいし）
深さ優先探索、幅優先探索はあんまり見ないし学習が面倒くさいので後回しにした（勿論D問題からは頻出と思われる）
二分探索もいもす法と同じくラッキーパンチが期待できると思うがヒネった形でしか見たことがなく知識が役に立ったことはない（勿論D問題からは頻出と思われる）
茶色の範囲での対計算量対処（想定O>10^9時の対処）については、配列添字呼び出し、算数・数学を使ったO(1)化、二分探索、いもす法等を見た。
ちまちま作ったライブラリはこちら（ABC60～ABC100 A～C問題用）
インスタンスにして使ってください。
class LittleMethods
{
//整数二つを受け入れ、最大公約数を出す
public long GreatestCommonDivisor(long a, long b)
{
// https://qiita.com/Jane35416555/items/0d9d6dd088049ce64e3d
long x = 0;
while (1 == 1)
{
if (a % b == 0)
{
return b;
}
else
{
x = a % b;
a = b;
b = x;
}
}
}
//整数二つを入れ、最小公倍数を出す
public long LeastCommonMultipul(long a, long b)
{
// https://qiita.com/Jane35416555/items/0d9d6dd088049ce64e3d
long x = GreatestCommonDivisor(a, b);
return a * b / x;
}
//整数一つを入れ、素数ならtrueを返す
public bool PrimeNumberOrNot(long x)
{
if (x == 1) { return false; }
for (long i = 2; i * i <= x; i++)
{
if (x % i == 0) { return false; }
}
return true;
}
//整数一つを入れ、全ての約数をListで返す
public List<long> DivisorAll(long x)
{
List<long> y = new List<long>();
if (x == 1) { y.Add(1); return y; }
for (long i = 1; i * i <= x; i++)
{
if (x % i == 0)
{
y.Add(i);
if (x / i != i) { y.Add(x / i); }
}
}
y.Sort();
return y;
}
//https://stackoverflow.com/questions/4124189/
//sqrtの精度に問題があると聞いたのでいざという時使えるよう調べた。decimalを入れるとルートしてdecimalで返す。
public decimal SuperSqrt(decimal x,decimal epsilon = 0.0M)
{
decimal cur = (decimal)Math.Sqrt((double)x), prev;
do
{
prev = cur;
if (prev == 0.0M) return 0;
cur = (prev + x / prev) / 2;
} while (Math.Abs(prev - cur) > epsilon);
return cur;
}
//階乗して返す
public long Multipul_Fuctrial(long x)
{
long a = 1;
for (int i = 2; i <= x; i++)
{
a *= i;
}
return a;
}
//特定の数で毎回割りながら階乗する。
public long Multipul_FuctrialRemainderer(long x)
{
long a = 1;
long b = (long)Math.Pow(10, 9) + 7 //ここは問題に寄る
for (int i = 2; i <= x; i++)
{
a *= i;
a = a % b;
}
return a;
}
//順列総当り用 戻り値：1 2 3,1 3 2,などなど各順列のリストのリスト
//本番中に作ったので参考URLを紛失。申し訳ございません。
public static IEnumerable<T[]> Make_PermutationList<T>(IEnumerable<T> col)
{
if (col.Count() == 1) yield return new T[] { col.First() };
foreach(var x in col)
{
var selected = new T[] { x };
var unused = col.Except(selected);
foreach (var y in Make_PermutationList(unused))
{
yield return selected.Concat(y).ToArray();
}
}
}
まとめ
ぜひAtCoder一緒にやってください。趣味なら戦場が血に染まるほど戦いは楽しいです。
既にやっている方は仲良くなってください。
twitter:@kisihara_c
Author And Source
この問題について(競プロ初学ログ), 我々は、より多くの情報をここで見つけました https://zenn.dev/kisihara_c/articles/4d78a281aebb645e2cd2著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Collection and Share based on the CC protocol