LoginSignup
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@tomo0211goo(ともはる)

【AtCoder】入水しました！！

Posted at

この記事はKCS Advent Calendar 2024の25日目の記事です。

24日目
↑
この記事

はじめに

今年の11月23日、サークル内専用の MissKey にてこんなノートを出しました。

KCSKey.png
▲ 入水宣言　当時はレート1108

そして、12月7日のABC383にて、

入水.png

無事に入水を達成しました！！！
この記事では、入水までにやったことや、苦戦したことについて書きたいと思います。

目次

  1. 自己紹介
  2. 競プロ開始前のこと、はじめたきっかけ
  3. 現在のこと
  4. 効果のあった精進など
  5. 終わりに

自己紹介

AtCoder：Tomo271828
Codeforces（やってない）：Tomo271828
yukicoder（やってない）：Tomo271828
MojaCoder：Tomo271828

情報工学科　2年
使用言語：C#
KCSではゲーム開発班、CG班、音楽班、競プロ班、映像制作班に所属し、ゲーム開発班と競プロ班の班長をしている。

競プロ開始前のこと、はじめたきっかけ

競プロは今年の4月2日にはじめた。
Unityでのゲーム開発を高1のときからやっていたため、競プロ開始時点でC#の基本的な文法は知っていたが、アルゴリズムはほとんど何も知らなかった。

KCS 春合宿にてサークルメンバーが以下の問題を解いているところを見て、もともと数学が好きだったこともあり、競プロに興味を持った。

D - At Most 3 (Contestant ver.)

ちなみに上の問題はまだ解いてない。
合宿後、帰宅中に C# でも競プロに参加できることを確認し、参加を決意。
その数日後、AtCoder を始めた。

現在のこと

入水時点での記録は以下の通り。

Achievement.png
▲ Achievement

問題別AC数.png
▲ ABC の AC 数

diff別AC数.png
▲ diff 別 AC 数

Climbing.png
▲ Climbing

こう見ると灰diff解きすぎだとわかる。ちなみに記事執筆時点では灰diffを全完している。
基本的に簡単な問題ばかり解いてしまうため、入水のためには難しい問題を解く習慣が必要だった。

効果のあった精進など

あまり難しい問題をじっくり考える習慣がなかったため、そこを解決するのが一番の課題。

1. 自作ライブラリの整備

7月の入緑後、やっと Visual Studio で競プロ用の環境構築を行ったため、そこからは自作ライブラリを作りまくっていた。
C# は標準入力の受け取りでも文字数が多いため、簡単な内容でもライブラリを作って文字数を減らしていた。

using System;
class Program{
    static void Main(string[] args){
        int[] a = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
    }
}

▲ int型配列を受け取るだけのコード　4行目が配列の受け取り

using System;
using TomoLibrary;
class Program{
    static void Main(string[] args){
        int[] a = TomoLibrary.Input.IntArray();
    }
}

▲ 自作ライブラリ版　大して短くなっていないが、予測変換で打ちやすい

また、二分探索などの単純なアルゴリズムは、ライブラリを作って何も考えずに実装できるようにしていた。他言語で標準に実装されているけれど、C# にはないものがいくつかあるのも理由。（lower_bound , next_permutation などがない）

using System;
class Program{
    static void Main(string[] args){
        int[] a = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
        Array.Sort(a);
        int ok = -1;
        int ng = a.Length;
        int num = int.Parse(Console.ReadLine());
        while (ng - ok > 1)
        {
            int mid = (ok + ng) / 2;
            bool check = false;
            if (mid == -1)
            {
                check = true;
            }
            else if (mid != a.Length)
            {
                if (a[mid] <= num)
                {
                    check = true;
                }
            }
            if (check)
            {
                ok = mid;
            }
            else
            {
                ng = mid;
            }
        }
        Console.WriteLine(ok + 1);
    }
}

▲ 配列 a の中から num 以下の要素の個数を求めるコード

using System;
using TomoLibrary;
class Program{
    static void Main(string[] args){
        int[] a = TomoLibrary.Input.IntArray();
        Array.Sort(a);
        int num = int.Parse(Console.ReadLine());
        Console.WriteLine(TomoLibrary.BinarySearch.EqualLessThanCount(a,num));
    }
}

▲ まったく同じ内容　ここまで単純化した

ライブラリを持っておくだけで役立つことは多いため、明確に強くなれたように感じるし、アルゴリズムの理解にもつながるため、個人的には一番お勧めできる。
自作ライブラリの一覧は以下の通り。

  • 入力
    • int,long,float,double,decimal の配列
    • string 1文字ずつの配列
    • int,char,string の2次元配列
    • int,long,char のjag配列
    • int,long,float,double,decimal,string,char の List
  • 出力
    • bool 値に応じて Yes,No を出力
    • bool 値に応じて YES,NO を出力
    • bool 値に応じて Takahashi,Aoki を出力
    • int,long,char の2次元配列を出力
    • bool 値の2次元配列を o と x に置き換えて出力
  • 配列操作
    • 2次元配列を時計回り90度回転
    • 2つの配列の全要素が一致しているか判定
    • 2つの2次元配列の全要素が一致しているか判定
    • 配列の最大値
    • 配列の最大値をとる最小の index
    • 配列の最小値
    • 配列の最小値をとる最小の index
    • 配列の全要素に指定した値を加算
    • 一次元累積和
    • 座標圧縮
    • char の List を string に変換
    • int,long,float,string,char の配列、List を指定回数右巡回シフト
  • 数学系
    • 最小公倍数
    • 最大公約数
    • 素数判定
    • 素因数分解
    • 10進法に変換
    • 約数の個数
    • 約数列挙
    • 桁数
    • 10進法 → N 進法に変換
    • 2つの閉区間に共通部分が存在するか判定
    • 繰り返し2乗法（n^k mod p）
    • エラトステネスの篩（素数列挙）
  • 二分探索（配列、リスト）　配列と数値 x を指定
    • 同じ値の index 、個数
    • 最も近い値の index
    • x 以下となる index の最大値、個数
    • x 未満となる index の最大値、個数
    • x 以上となる index の最小値、個数
    • x 超過となる index の最小値、個数
  • bit演算
    • popcount
  • 順列
    • 次の順列
    • 前の順列
    • 最初の順列か判定
    • 最後の順列か判定
  • 組み合わせ
    • （詳細）配列 $A$ を受け取り、各要素 $B_i$ が $0 \leq B_i < A_i$ となるような配列を全列挙するためのライブラリ　使い方は NextPermutation などと同じ
    • 次の組み合わせ
    • 最後の組み合わせか判定
  • 総和組み合わせ（造語）
    • （詳細）総和がある一定値 $K$ 以下となる要素数一定の配列を全列挙するためのライブラリ　使い方は NextPermutation などと同じ
    • 次の総和組み合わせ
    • 最後の総和組み合わせか判定
  • Union-Find
    • 根が同じか判定
    • 連結成分の個数
    • 全頂点の根の配列
  • 重み付きUnion-Find
    • 根が同じか判定
    • 連結成分の個数
    • 全頂点の根の配列
    • 2頂点間の重みの差
    • 頂点の重み
  • 最短経路
    • ダイクストラ法
    • ワ―シャルフロイド法
  • 二項係数
    • nCk (mod p)
  • Segment Tree
    • 区間最大値
    • 区間最小値
    • 区間和
  • Lazy Segment Tree
    • 区間更新
    • 区間最大値
    • 区間最小値

ちなみに、自作ライブラリの環境は Source Expander を使っている。提出用のコードが簡単に作れるため、C# を使っている人はぜひ使ってみてほしい。

今後は文字列処理のライブラリを増やしたい。（Trie木、Suffix Array など）

2. AIC競プロ講習会

AICとは：慶應にある学生主体の AI・プログラミング学習団体

AIC公式
競プロ講習会

AICで春と秋に競プロ講習会が行われていたため、主に秋の方に参加していた。
かなり難しいバーチャルコンテストが開催されていたため、難しい問題を解く習慣のない僕にとっては一番勉強になったように感じる。
また、強い方々と話す機会にもなったため、知らなかったものを多く知ることができた。
Mo's Algorithm、Segment Tree Beats などはここで知った。（本番で使ったことはまだない）

3. 作問

競プロの作問をして、学祭にて展示していた。
上 2 つと比較するとそこまで役に立ってはいないが、難しい問題を思いついてしまった場合自分で解かなければならないため、難しい問題を考えるきっかけにはなった。

以下、現時点での自作問題集（難易度順）。

4. バーチャルコンテストの開催

競プロ班の活動として、ほぼ毎週 AtCoder Problems 上でバーチャルコンテストを開催していた。
そこまで難しい問題は出題していなかったが、競プロする習慣にはなったように感じる。

終わりに

今後は、来年中の入青を目指そうと思います。

入青に向けて、

  • ライブラリの強化（ACL にあるやつは全部作るぐらい）
  • EDPC 攻略
  • 典型90攻略
  • 数学の勉強

をしたいと思っています。

ここまで読んでくださり、ありがとうございました！

Computer SocietyAdvent Calendar 2024

Day 25
3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?