ご挨拶
初めまして、競技プログラミング練習会2021 Normalの担当(の1人)のid:Flkanjin(KMCID: flkanjin)と申します。つい先日までGWでしたが、いかがお過ごしでしょうか? 昨年の前期はずっと自宅で授業で、今年は最初の2週間は対面授業も実施されましたが、殆どの科目が京大内の対応レベルの引き上げによりリモート授業となりました。私はというと、実験科目があるので、毎週大学に行っているのですが、定期を買った方が良いのか、ICチャージさせた方が良いのか...という感じで迷っています。
KMCの先輩と話しているときに「このブログ更新してみない?(意訳)」と言われましたので、活動ブログとして、今年のこれまでの競プロ練習会や、そもそも競プロとは何ぞやについて書きたいなと思います。
競技プログラミングって何?
競技プログラミングとは与えられた問題について、それを解くための適切なアルゴリズムを速く正確に書くことを競う競技です。競技プログラミングという名前は少し長いのでよく競プロと呼ばれます。数学やパズルのような要素があり、そのようなものが好きな競プロerは多いですが、そうでない競プロerもたくさんいます。
また、数学などの試験のような形式だけでなく、長時間(ものによっては1ヶ月など)でおこなうマラソンという形式のコンテストも存在します。こちらは与えられた問題に対してなるべく良い解をとれるようなぷトグラムを作り、その点数を競うものです。こちらの記事のゲームAI系と近いものがあります。
KMCでの競技プログラミング練習会について
KMCでは競プロ練習会としてNormal(未経験、初心者向け)とAdvanced(上級者向け)の二種類が開催されています。
Normalでは主に初めての方向けにC++というプログラミング言語やアルゴリズムの基礎についての講座を行い、その内容に関する(バーチャル)コンテストを行います。初心者向けというのもあって質問対応なども丁寧に行っているつもりです。Advancedの方では毎回コンテストを行い、いくつかの解では講座も行っているようです。
今年のこれまでの軌跡(Normal)
去年から続くコロナ禍のため、例年の通りの部室での活動ができないため、Discordを用いてオンラインで行っています。今年は講座の担当を奇数回は私(KMCID:flkanjin)が、偶数回はKMCID:replica君が担当しています。コンテストは基本的にはAtCoderの過去問やAOJに存在する問題を用いて開催しています。
第1回(2021/04/09(金)) 担当: flkanjin
初回であったため、簡単に競プロとは何かということを話し、いくつかのオンラインコンパイラを紹介、自前での環境構築について少し触れたのち、C++の基礎(コメント、変数、入出力、if, while, for)についての講座を行いました。
コンテストでは今回の講座の内容だけで解くことのできるAからD問題(ただし、CDは難易度高め)と経験者向けのEからK問題を出題しました。難易度的には後半の問題は特に難しいものを集めていたので、解ける人いるだろうか、みたいにドキドキしていていたところはあります。
第2回(2021/04/16(金)) 担当: replica
2回目は1回目に引き続きC++の基礎(型についての詳しい説明、配列(vector)、関数(再帰も))についてやったのち、競プロにおいて重要な概念である計算量と一番単純なアルゴリズムである貪欲法について学びました。コンテストは少し難易度が高めでABでWA(不正解)などを出している人が結構いたなという印象でした(AもBもペナルティなしで正解した人が1人ずつでした)。この回からコンテストの内容は講座の内容にリンクしたものになっています。
第3回(2021/04/23(金)) 担当: flkanjin
この回のテーマは累積和で、派生してimos法や尺取り法も取り扱いました。今回からのアルゴリズムは基本的に高速化するためのもので、コンテストも素直な実装では間に合わないという問題が多くなっていますが、殆どの参加者か解け形るようで安心しました。
第4回(2021/04/30(金)) 担当: replica
ソートや二分探索、そしてSTLのデータ構造についての講座でした。pairのソートについて少し複雑だったかもしれません。二分探索について慣れていってほしいなと感じました。
第5回(2021/05/07(金)) 担当: flkanjin
今回は全探索回でした。線形、順列、DFS、BFS、bit全探索(とそれに必要なbit演算)についても勉強しました。ちょっと講座部分が長かったかもしれないです。線形探索や順列探索は単純なものでしたがその他のものは少し複雑でとっつきにくいものだったかもしれません。分かり易い説明を考えないとなぁと感じさせられました。
感想
人に何かを教えるというのは難しいなぁ、と感じさせられます。特にリモートで行っていると顔が見えなかったり、どこで困っているのかが見えにくく、早く部室でできるようになってほしいなと思います。
6回目やります
翌週の05/14(金)に競プロ練習会Normal第6回を行います。この記事を読んで興味を持った方やこの春に何かしら新しいことを始めたいと思った方など、奮ってご参加ください。
参加方法
KMC自体の宣伝
KMCではパソコンでゲームを作ったり、音楽を書いたり、お絵描きしたり、競プロをしたりしています。興味のある方は是非下のリンクからどうぞ!! www.kmc.gr.jp
