TNP競プロ支部の活動結果と今後(春のポエム枠)

あいさつ

114514810
ガナリヤです〜

自己紹介しなくても書いてるの大体ガナリヤなので、要らない気がしてきた・・・

今日はとことんやる気が出ないので、AGCまで時間つぶしに今後のTNP競プロ支部の展望とか書こうかなと思ってます

あと一週間で春休みが終わり、このぐうたらな毎日が終わって、毎日研究と考えると・・・
たぴゃ〜〜〜〜〜〜〜〜〜(一部界隈にしか伝わらないやつ)


競プロ支部って?

競プロ支部って何ぞってなるお気持ちになるので説明します。

我々TNPでは主にゲーム制作やイラストを書いたり、音楽制作などを行うのが主な活動ですが、最近は色々なツール・言語の増加によって、これまでよりも幅が広がった活動内容になってきました。

最近勢力を増しているSiv3D支部や、3Dやクオリティの高い2Dを作るUnity支部。
そして、新しいツールが増える今なお、古のDXライブラリで命を削っている支部もあります。(彼らは特殊な訓練を受けており、精神的ストレスと引き換えに圧倒的デバッグ能力とコーディング能力を身に着けています)

そして、去年の2~4月頃に幾人かで構成された競プロ支部が発足しました。(といっても、ガナリヤが勝手にそう読んでるだけですが・・・

現在は三年生が約3人? と一年生が1人で構成されています?(疑問系なのは、特に競プロ支部集まれ!ってやっていないのとで・・・)


そもそも競プロってなんだよ(哲学)

競プロってなんなんだろう・・・

自分でもたまに迷いますねこれ・・・

競プロは「競技プログラミング」の略で、与えられた問題を制限時間以内に解いてコーディングし、それを提出するやつです。

上のスライドとかが競技プログラミングを物語っている資料でこれを書いた人はすごい人で、競プロ界隈だと知らない人はいません。

例えば、以下の問題を考えてみましょう。


https://yukicoder.me/problems/no/800

問題文(四平方定理)

整数$N$, $D$が与えられる。
以下の2つの条件を満たす正の整数の組$(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;
 }

競技プログラミングは以上のように、まず3つのパートに分かれます。

まず、問題を読むパートです。Writerがどのようなことをさせたいのかを出来るだけ早く読み取ります。

そして、次に考察パートです。ここが苦しいところです。
僕はアタマが悪いので、ここでだいたい解けないです。

そして、もし考察が出て解法が生えたら、それを実装する必要があります。

この、「考察が出来る」と「実装が出来る」が別なのが難しいところで、
「考察が出来た!」ってなっても実装がゴミクソめんどくさいときがあります。
また、「実装は得意!」でも考察が全く出来ないときがあります。

数学オリンピックなどでは、この考察が出来るパートが要求され、さらに競技プログラミングではここに「プログラミング」の要素が追加されるわけです。

先程の問題と、解法を読んでピンと来る人は少ないだろうなと思います。
自分もまだまだ弱いですが、始めたてはプランクトン並でした(さっきの問題の解法なんてINF時間座っても生えません。)

でも練習次第で、ある程度は解けるようになります。


競プロのメリット・デメリットって何?

最近情報業界でかなり人気になってきている競技プログラミングですが何が楽しく、何がメリットなのでしょう・・・

自分もたまに、やっぱつれぇわ・・・ってなりながら競技プログラミングをしています。
それでも一年は続けていられているので、自分の性分にあっているのかな〜〜と思っています。

メリット

競プロを通して得られることは多いです。

まずは、「実装能力」が挙げられると思います。
競プロでは、あらゆるデータ構造とアルゴリズムを使用します。
競プロ以外のアプリ開発やゲーム開発は、競プロの実装と比べると明らかに楽なので、これまでより、楽にコーディング出来たりします。
また、実装できなさそう・・・と感じることがかなり減ると思います。

次に、考察力があがると思います。
競プロではあらゆる問題に対し、
1. 仮説を立てる
2. コードを書く
3. デバッグをする

という課題解決のステップを非常に細かく踏みます。
色々な知識がつくのも競技プログラミング特有のものだと思います。

そして、レートが出て、客観的に自分の実力がわかるがあると思います。

以上は自分のAtCoderでのレート推移です。
グラフの伸びを見る限り、天才型ではないのはひと目で分かります。(くやしい

でも、だからこそ、練習をして色んなアルゴリズムを覚えて、レートがあがり、初めて400点の問題をコンテスト中に解けたときは、人生でかなり楽しかった瞬間に入ります。

やはり楽しい!!!!!!!
っていうのが根幹にある感じです。
(ただ、楽しい!っていうのはコンテストに出てレートがつかないとわからない部分ですね・・・)
承認欲求が満たされる音がします。


デメリット

デメリットも色々とあります。

まず、「アプリ開発やフレームワークの知識はつかない」
という点です。
競プロで学べるのはアルゴリズムや実装・考察力なので、なにかアプリ開発が出来たり、フレームワークが使えるかは別になります。

ただ、アプリ開発出来て競プロ出来ない人は見かけますが、競プロ出来てアプリ開発出来ない人はほとんどいないです。
ただ、競プロもアプリ開発もやらないとアプリ開発の知識はつかないです・・・

2つ目に、競プロで生活をかなり支配されます。
AtCoderは土曜日の夜九時から二時間ぐらいなので良いですが

Codeforcesというサイトはロシアで運営されているコンテストであり、深夜12:35から二時間ぐらいあります。
普通に生活リズムが乱れます。

また、たぴ〜〜〜や、AC、tourist語録など、競プロ用語に支配される日が来ます。
知らないうちに「おきもち」という単語を永遠に使い続けることになります。


競プロに向く人・向かない人

競プロですが、誰しもに向いているものではないです。

競プロが好きな人はいかのようなことが好きな傾向にあります。

  • 人と争うのが好き
  • 承認欲求が強い
  • 数学・アルゴリズムが好き
  • 順位が好き(レートが好き)
  • 考えることが好き(パズルが好き)
  • 快感を欲している
  • 自分が好き
  • アプリ開発などの長期的スパンが続かない
  • ツイッターが好き
  • 音ゲーがすき(音ゲーマーみんな競プロ強いんですがなぜ・・・)

特に、アプリ開発などの長期的スパン開発が続かない人には向いてますね・・・
1問1問が短いので、さらっと解くを何回も繰り返しているうちに強くなります。

競プロが好きでない人は個人的に以下のようなものがある気がします

  • 順位をあまり気にしない
  • 承認欲求が少ない
  • 上昇志向がない
  • 数学・アルゴリズムよりも、開発でプロダクトを作るのが好き
  • 短い努力を繰り返すより、長い努力をしたい
  • アプリ開発が好き

結構、好きな人と好きでない人は正反対の位置にある気がしています。

やりたいことがない人は競プロを始めてみるといいかもしれません。


去年一年の活動について

去年一年、競プロ支部では基本的に個人活動でした。
競プロは基本的には個人競技なので致し方ないところではあります。

ただ、去年7月に行われたICPCというチーム大学対抗競プロ大会で

TNPの三年次かつ、同じバイト先の自分含む計三名でICPCインターネット予選に参加し、色々な奇跡が重なってアジア大会に出られることになり、去年の12月に参加しました。

これまでの人生で一番満たされた3日間だったと思います。
もっと競プロに打ち込んで実力をつけたいと思いました。


4月からの一年の展望

競プロ支部はどのようになっていくのでしょうか・・・
正直ようわからんです・・・

現在、現一年生(新二年生)の一人が昨年から競プロを始めており、競プロが広まって嬉しいなぁというお気持ちになっています。
レートもみるみる上がっているので、将来抜かれそうで怖いなぁとなっています。(特に数学が好きなのが非常に怖いポイント)

これからどんどん、新一年生にも広まって、ゲーム開発もできて、競技プログラミングもできる学生が増えればいいなと思っています。

とりあえず今年の7月のICPCに向けて日々精進して行きたいです。

まずはそこからはじめて、普通の国立の中では、秋田大学が競技プログラミングである程度強い大学と言えるように頑張っていこうと思います。

あと、にじさんじの卯月コウってやつエモいから見てくれよな(後方


追伸

どんどんブログを、新入生歓迎に向けて活性化させていきたいお気持ち

みんな書いて♡俺も書いたんだからさ・・・(いやです・・・)

ICPC2018国内予選参加記 Tech-ONC

こんばんえるえる〜〜
毎度ガナリヤです!
部室行かなくてすいません!活動はしてるんです!集中力の問題で家でやってます・・・(お兄さん許して・・・)
今日は、ICPC国内予選に参加したので、来年のリベンジのために参加記を残しておこうとおもいます。
 
 

チーム Tech-ONC

チームTech-ONCはTNP部員かつ、同じ競技プログラミングバイト先の三人で構成されています。
思考力・実装力担当の我らが部長!こしょう!
C++の魔法使い!サバ!
手広無力おじさん!ガナリヤ!
の三人です。
このチームの特徴として

  • 普段アルバイトで、競技プログラミング問題制作を行っている
  • 得意なことがそれぞれ違い、バランスが取れている
  • 三人共コーディングを担当できる
  • いい意味でも悪い意味でも、そこまで競技プログラミングコーディング力が離れていない(他チームは、一人だけ無茶苦茶強いところが多かったりする)

という点があります。
僕が誘わせていただき、引き受けていただきて本当に嬉しかったです!


参加記

事前準備

統計の授業を三人で抜け出してご飯を食べる。
チョコレートがおいしかった。
その後、コーディング場に移動し、それぞれマクロや本の準備をしていた。
その間、サバがVisualStudio設定RTAしてて面白かったです、来年は僕も設定できるようになりたい

16:10頃、監督の先生が到着(本当に引き受けていただきありがとうございます!)
雑談をしつつ、そわそわしながら開始を待つ。
  

ICPC予選開始

16:30から予選開始。
サバニキが印刷をぶん回しつつ、僕がA問題の紙を読み、こしょうがB問題の紙を読み始めました。
その間、サバがVisualStudioの設定やマクロの準備をしており、縁の下の力持ちでした!(またnext_combinationの実装もしてもらってしまった・・・来年までにはもっと簡単な実装にします・・・)サバありがとう!

A問題 所得格差は、N人の合計の平均を取って、平均より小さい人数を数えるだけの問題で非常に簡単でやるだけでした。年々A問題は簡単になっている気がする・・・
ハラハラしつつ、doubleのガバに気をつけてAC

  

B問題とC問題

A問題を解いた後、こしょうがB問題へ。
僕とサバでC問題に移動。

こしょうにきが解いている間、C問題を二人で話し合う。
C問題 みなとハルカス

C問題は、整数bが与えられ、1~Nまでの中で連続した整数の和がbに一致する中で、最長のものを出力せよという問題でした。
二人で話し合った結果、部分累積和で10^8までぶん回すか、しゃくとり法で実装するかの二択になりました。
ここで壮大なミス。
絶対に部分累積和じゃ通らないのに、部分累積和の案を採用。ふたりともしゃくとり法はあまりお得意なお気持ちではないため、部分累積和に逃げてしまった・・・、このミスが無ければDの実装が間に合ったかもしれない(申し訳ない)

間違った部分累積和の実装が行けそうになったとき、こしょうの実装でエラーが発生していた模様。
コードを印刷してもらって、エディタを空けてもらって入れ替わりで僕が嘘解法を実装。
ちなみに、今回のB問題はCよりずっと難しかったようで、さらっと解いてるこしょうやっぱやばい。

嘘解法のCを実装した僕
「できた!天才か〜〜〜?」←嘘解法で喜んでいるクズの図
10^9の実装のため、テストケースだけ通して、もう一度こしょうと交代。
こしょうがB問題の添字ミスと、問題文の勘違いに気づいたらしく難なくAC。こしょうにきは、問題文読み間違い以外基本的にすべて通している(すごい(すごい))

その後、こしょうに変わってもらって、投げていたテストケースを見ると、数が合っておらず、嘘解法であったことに気づく(当たり前だよなぁ?)
急いで、しゃくとり法で実装してAC。やっぱ最初からしゃくとり法にするべきでした、チキっちゃだめやね・・・
  

D問題

ここから毎回僕たちが苦戦しているD問題以降パートへ。

サバニキがD問題とE問題に目をつけていて、問題概要や、解き方のコツを教えてもらった。
D問題 全チームによるプレーオフは、サッカーの試合をするとき、すべてのチームの勝敗が一致し、全員で仲良しになる総数は何個あるか?という問題だった。

僕とサバでDはやべえな・・・となり、他の問題をいろいろ見ていた。よくよく考えるとこれが悪手だった気がする。最初からずっとDのみに取り組んでいれば、時間が間に合ったかもしれない(悔しい・・・)

その後、こしょうもDに参戦し、こしょうとサバが解き方の方針を教えてくれた。(5人なら、必ず全てのチームが2勝2敗とか、普段の自分一人のコーディングなら絶対に気づけてない・・・)

その後しばらく三人でDにうなり続け、うだうだ言いながら、意見を出しつつ、next_combinationで1と0の組み合わせを求めれば計算量はあまり増えないということに気づく(正直合ってるか分からん)
よくわからないまま、時間が無いため、僕が突発的に考えた多分正攻法ではない、汚いアイディアを実装することに。
僕とこしょうでペアプロしつつ、サバがnext_combinationの実装をしてくれた(来年までにはもっと分かりやすいライブラリつくる許して・・・)
こしょうとサバのこしょうを借りつつ、ガバガバ実装を行い、時間と戦いつつ、コーディングが完成。
奇跡に祈りつつ、実行したところ、添字エラー。添字エラーを解消している中で、時間になってしまった・・・

  


振り返り

ICPCに参戦してみて、すんごい楽しかったです。
他の人と、問題を解くためのアイディア出し合ったり、ふざけながら問題通すのって、学生のうちしかできない気がする(仕事になると、ふざけることはできない・・・)
また、自分の実装の弱さに気付かされた回でもありました・・・。他の二人の実装がすごい綺麗で、僕のコーディングがかなり汚いので、デバッグしづらくて二人がかなり僕のコードを追うの辛かったと思います。もっと簡潔なコーディングできるよう目指していきたいです。

何はともあれ、すごい楽しかった
来年もこの三人でTech-ONCとして出るという話をした。
来年は三人共、競技プログラミングがうまくなり、僕はAtCoder年内中に青色、来年のICPCまでに黄色になっているはずなので(希望的観測)、来年のチーム名はTech-ONS(O(N^2))でしょうか・・・

何も考えず、今日あったことをそのまま書いているだけで、読みづらいと思います。すいません。
それぐらい楽しかったです
明日はSoundHound頑張ろうと思います!

ガナリヤでした!