あいさつ
114514810
ガナリヤです〜
自己紹介しなくても書いてるの大体ガナリヤなので、要らない気がしてきた･･･
今日はとことんやる気が出ないので、AGCまで時間つぶしに今後のTNP競プロ支部の展望とか書こうかなと思ってます
あと一週間で春休みが終わり、このぐうたらな毎日が終わって、毎日研究と考えると･･･
たぴゃ〜〜〜〜〜〜〜〜〜(一部界隈にしか伝わらないやつ)
競プロ支部って？
競プロ支部って何ぞってなるお気持ちになるので説明します。
我々TNPでは主にゲーム制作やイラストを書いたり、音楽制作などを行うのが主な活動ですが、最近は色々なツール・言語の増加によって、これまでよりも幅が広がった活動内容になってきました。
最近勢力を増しているSiv3D支部や、３Dやクオリティの高い２Dを作るUnity支部。
そして、新しいツールが増える今なお、古のDXライブラリで命を削っている支部もあります。（彼らは特殊な訓練を受けており、精神的ストレスと引き換えに圧倒的デバッグ能力とコーディング能力を身に着けています）
そして、去年の2~4月頃に幾人かで構成された競プロ支部が発足しました。(といっても、ガナリヤが勝手にそう読んでるだけですが･･･
現在は三年生が約3人？ と一年生が1人で構成されています？(疑問系なのは、特に競プロ支部集まれ！ってやっていないのとで･･･)
そもそも競プロってなんだよ(哲学)
競プロってなんなんだろう･･･
自分でもたまに迷いますねこれ･･･
競プロは「競技プログラミング」の略で、与えられた問題を制限時間以内に解いてコーディングし、それを提出するやつです。
上のスライドとかが競技プログラミングを物語っている資料でこれを書いた人はすごい人で、競プロ界隈だと知らない人はいません。
例えば、以下の問題を考えてみましょう。
https://yukicoder.me/problems/no/800
問題文(四平方定理)
整数$N$, $D$が与えられる。
以下の２つの条件を満たす正の整数の組$(x, y, z, w)$の個数を求めてください。
1. $x, y, z, w$はそれぞれ$1$以上$N$以下の整数
2. $x^2 + y^2 + z^2 = w^2 + D$
上記の問題の$N$, $D$は問題から与えられます。
例えば、$N=3$, $D=2$のときは
$(x,\ y,\ z,\ w) = (1, 1, 1, 1), (1, 1, 2, 2), (1, 1, 3, 3), (1, 2, 1, 2), (1, 3, 1, 3), (2, 1, 1, 2), (3, 1, 1, 3)$
が条件を満たします。
勘の良い方、またはプログラミングをした人なら
全探索すればいい
と思うと思います。
これは間違っていないです。
但し、この問題は
$N{\leq}2*10^3$
$D{\leq}10^6$
という制限が与えられています。
全探索をすると、これの計算量は$(2*10^3)^4 = 8*10^{12}$です。
実は$10^8$回計算すると$1$秒の実行時間で、上記の全探索をすると、
これは44時間もかかってしまいます。
全探索すると$44$時間かかってしまう計算をするわけにはいきません。
この問題を$2$秒以内に解かないとAC（Accepted）がもらえないからです。
以下、解法です。
$x, y$を全探索することを考えてみます。
するとこれは$2000^2 = 4000000$であり、実行時間は$0.004$秒ぐらいなので間に合います。
$2$つめの式を変形すると
$w^2 = x^2 + y^2 + z^2 – D$で
先程$x, y$を全探索したため、定数とみなせます。
よって、$x^2 + y^2 – D = T$という定数に置くと
$w^2 – z^2 = T$
と表せます。
このようにすると、$w, z$を全探索して、$T$という計算結果になるような個数を保存すれば良さそうとなります。
あとは、この$w, z$の計算を先に前計算しておき、その後、$x, y$を計算しておけば、これは計算量は$O(N^2)$に抑えることができ、ACを貰うことができます。
using LL = long long;
//~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~
int main() {
int N, D;
cin >> N >> D;
int base = 100000000 / 2;
vector<int> cnt(100000000, 0);
for (int w = 1; w <= N; w++) {
for (int z = 1; z <= N; z++) {
cnt[base + w * w - z * z]++;
}
}
int ans = 0;
for (int x = 1; x <= N; x++) {
for (int y = 1; y <= N; y++) {
int d = x * x + y * y - D;
ans += cnt[base + d];
}
}
cout << ans;
return 0;
}
競技プログラミングは以上のように、まず３つのパートに分かれます。
まず、問題を読むパートです。Writerがどのようなことをさせたいのかを出来るだけ早く読み取ります。
そして、次に考察パートです。ここが苦しいところです。
僕はアタマが悪いので、ここでだいたい解けないです。
そして、もし考察が出て解法が生えたら、それを実装する必要があります。
この、「考察が出来る」と「実装が出来る」が別なのが難しいところで、
「考察が出来た！」ってなっても実装がゴミクソめんどくさいときがあります。
また、「実装は得意！」でも考察が全く出来ないときがあります。
数学オリンピックなどでは、この考察が出来るパートが要求され、さらに競技プログラミングではここに「プログラミング」の要素が追加されるわけです。
先程の問題と、解法を読んでピンと来る人は少ないだろうなと思います。
自分もまだまだ弱いですが、始めたてはプランクトン並でした(さっきの問題の解法なんてINF時間座っても生えません。)
でも練習次第で、ある程度は解けるようになります。
競プロのメリット・デメリットって何？
最近情報業界でかなり人気になってきている競技プログラミングですが何が楽しく、何がメリットなのでしょう･･･
自分もたまに、やっぱつれぇわ･･･ってなりながら競技プログラミングをしています。
それでも一年は続けていられているので、自分の性分にあっているのかな〜〜と思っています。
メリット
競プロを通して得られることは多いです。
まずは、「実装能力」が挙げられると思います。
競プロでは、あらゆるデータ構造とアルゴリズムを使用します。
競プロ以外のアプリ開発やゲーム開発は、競プロの実装と比べると明らかに楽なので、これまでより、楽にコーディング出来たりします。
また、実装できなさそう･･･と感じることがかなり減ると思います。
次に、考察力があがると思います。
競プロではあらゆる問題に対し、
1. 仮説を立てる
2. コードを書く
3. デバッグをする
という課題解決のステップを非常に細かく踏みます。
色々な知識がつくのも競技プログラミング特有のものだと思います。
そして、レートが出て、客観的に自分の実力がわかるがあると思います。
以上は自分のAtCoderでのレート推移です。
グラフの伸びを見る限り、天才型ではないのはひと目で分かります。(くやしい
でも、だからこそ、練習をして色んなアルゴリズムを覚えて、レートがあがり、初めて400点の問題をコンテスト中に解けたときは、人生でかなり楽しかった瞬間に入ります。
やはり楽しい！！！！！！！
っていうのが根幹にある感じです。
（ただ、楽しい！っていうのはコンテストに出てレートがつかないとわからない部分ですね･･･）
承認欲求が満たされる音がします。
デメリット
デメリットも色々とあります。
まず、「アプリ開発やフレームワークの知識はつかない」
という点です。
競プロで学べるのはアルゴリズムや実装・考察力なので、なにかアプリ開発が出来たり、フレームワークが使えるかは別になります。
ただ、アプリ開発出来て競プロ出来ない人は見かけますが、競プロ出来てアプリ開発出来ない人はほとんどいないです。
ただ、競プロもアプリ開発もやらないとアプリ開発の知識はつかないです･･･
２つ目に、競プロで生活をかなり支配されます。
AtCoderは土曜日の夜九時から二時間ぐらいなので良いですが
Codeforcesというサイトはロシアで運営されているコンテストであり、深夜12:35から二時間ぐらいあります。
普通に生活リズムが乱れます。
また、たぴ〜〜〜や、AC、tourist語録など、競プロ用語に支配される日が来ます。
知らないうちに「おきもち」という単語を永遠に使い続けることになります。
競プロに向く人・向かない人
競プロですが、誰しもに向いているものではないです。
競プロが好きな人はいかのようなことが好きな傾向にあります。
- 人と争うのが好き
- 承認欲求が強い
- 数学・アルゴリズムが好き
- 順位が好き(レートが好き)
- 考えることが好き(パズルが好き)
- 快感を欲している
- 自分が好き
- アプリ開発などの長期的スパンが続かない
- ツイッターが好き
- 音ゲーがすき（音ゲーマーみんな競プロ強いんですがなぜ･･･）
特に、アプリ開発などの長期的スパン開発が続かない人には向いてますね･･･
１問１問が短いので、さらっと解くを何回も繰り返しているうちに強くなります。
競プロが好きでない人は個人的に以下のようなものがある気がします
- 順位をあまり気にしない
- 承認欲求が少ない
- 上昇志向がない
- 数学・アルゴリズムよりも、開発でプロダクトを作るのが好き
- 短い努力を繰り返すより、長い努力をしたい
- アプリ開発が好き
結構、好きな人と好きでない人は正反対の位置にある気がしています。
やりたいことがない人は競プロを始めてみるといいかもしれません。
去年一年の活動について
去年一年、競プロ支部では基本的に個人活動でした。
競プロは基本的には個人競技なので致し方ないところではあります。
ただ、去年７月に行われたICPCというチーム大学対抗競プロ大会で
TNPの三年次かつ、同じバイト先の自分含む計三名でICPCインターネット予選に参加し、色々な奇跡が重なってアジア大会に出られることになり、去年の12月に参加しました。
これまでの人生で一番満たされた3日間だったと思います。
もっと競プロに打ち込んで実力をつけたいと思いました。
４月からの一年の展望
競プロ支部はどのようになっていくのでしょうか･･･
正直ようわからんです･･･
現在、現一年生(新二年生)の一人が昨年から競プロを始めており、競プロが広まって嬉しいなぁというお気持ちになっています。
レートもみるみる上がっているので、将来抜かれそうで怖いなぁとなっています。（特に数学が好きなのが非常に怖いポイント）
これからどんどん、新一年生にも広まって、ゲーム開発もできて、競技プログラミングもできる学生が増えればいいなと思っています。
とりあえず今年の７月のICPCに向けて日々精進して行きたいです。
まずはそこからはじめて、普通の国立の中では、秋田大学が競技プログラミングである程度強い大学と言えるように頑張っていこうと思います。
あと、にじさんじの卯月コウってやつエモいから見てくれよな(後方
追伸
どんどんブログを、新入生歓迎に向けて活性化させていきたいお気持ち
みんな書いて♡俺も書いたんだからさ･･･(いやです･･･)