こんにちは、kurokuです。先月から始めたこの【月一】企画、第二回にして期限ぎりぎりとなってしまいました。先が思いやられますね。とりあえず年度内はこのペースを保っていきたいです。

題材提供

前回ホワイトボードで募集した題材の中に「DxLibで3D」というのがありました。これは厄介だ。なんといってもDxLibは2Dですら結構大変なコードの記述が必要です。例えば当たり判定なんかも、実装自体は軽めですが上下左右に適用したり、足場のふちに当たった際の判定など書かなければならないことが多くなってしまいます。

まぁDxLibのサンプルゲーム見ればなんとなくわかるやろ、と思って以下のページを見てみました。

https://dxlib.xsrv.jp/program/dxprogram_3D.html

その中でもゲームを作るのに重要そうなのは１とか１９かなーってコードを眺めていました。

？？？

いや、それぞれどういう動作なのかはなんとなくわかりそうですが、デバッグ用のオブジェクトを置くのにも大変そう、変数の存在範囲が広すぎてパラメタがどんどん増えそう。といった感じがしてきてア。

そこで今回のタイトルは何だったでしょう？「競技プログラミング」？3Dゲームは？

はい、3Dゲームについての記事は書けませんでしたぁぁぁぁぁ

３Dゲーム作るならUnity使おう！マウス操作だけでオブジェクトが生成できる！（すごい！）Unityちゃんかわいい！

というわけで3Dゲームを作ってみたいって人はUnityをお勧めします。というかUnityなら何でもできます。（Unityがこの世界を作ったといっても過言

https://unity.com/ja

Unityは何といってもAsset storeが充実しています。Assetというのはいわば、物とか材質とかです。月末報告会でのまんじゅう君のUnityちゃんやYutaさんの車がそうです（多分）。これらには基本的なプログラムがあらかじめ作成されており、ゲームの動きさえ書いてしまえばOKという感じです！

ただ、Unityで使われている言語はC#で、バリバリにオブジェクト指向の考えを取り入れています。なのでC言語から入った人だとコードの違いに混乱してしまうかもしれません。幸い、ブログ記事などが多く書かれているので、C#が書けなくても調べさえすれば大丈夫なことが多いです。

本題

やっと前回の言い訳説明が終わったので、競プロの話をば。

競プロとはなんぞやというのは以前ガナリヤさんが書いた記事があるのでそちらを参考に。

http://akitatnp.wp.xdomain.jp/2019/03/23/tnp%e7%ab%b6%e3%83%97%e3%83%ad%e6%94%af%e9%83%a8%e3%81%ae%e6%b4%bb%e5%8b%95%e7%b5%90%e6%9e%9c%e3%81%a8%e4%bb%8a%e5%be%8c%e6%98%a5%e3%81%ae%e3%83%9d%e3%82%a8%e3%83%a0%e6%9e%a0/

（これリンクを短縮形で貼るのどうやってやるんだろうか

こうゆうのもあるよっていう紹介・体験を来週の水曜か金曜にやろうと思ってます。（2019/11/30現在）

冬コミのゲームできて（僕はまだ作ってませんが）当分はすることないやって人や少しでも興味があるって人は挑戦してもらいたいです。

内容としてはごくごく簡単めな問題を実際に解いてもらうって感じにしようと思います。配点としては100-100-100-200-200-300くらい？基本的に標準入力(scanf)、標準出力(printf)、if、for、配列ぐらいがわかっていれば解けるような問題を用意します。（１時間くらいを想定）

100点問題なんかはほんとに入力して、四則演算して、出力みたいなものですし、300点は少し頭を使うような問題と思ってもらえればいいと思います。

日本だとAtCoderが大きいコンテストサイトですかね。（来週の問題もAtCoderの問題を出題します）

https://atcoder.jp/?lang=ja

（ほぼ）毎週土曜21時からコンテストが開催されてます。よかったら参加してみましょう。

まとめ

競技プログラミングは名前からしていかついと思われがち（いや、しらんけど）ですが、やってみると楽しいです。競プロにはまっている人を見るとそんなに時間をとれないと思うかもしれませんが、たまに参加してみるでも全然いいと思います。

毎年夏～秋には大学対抗のICPCという世界規模の大会も開催されます。僕は学部生の内に一回は予選を突破して、横浜大会に出てみたいです。もし、一緒に出てくれる人がいたら全力でサポートするので、来週の回はそれの足掛かりにしてもらえればと思います。

そんな感じでまた来月～

kurokuでした！

初めまして！二年生のkuroku(でんそん)です。サークルのブログをはじめて執筆するのでどんな雰囲気で書けばいいかいまいちわかりませんが、先日行われたICPC国内予選の感想などを伝えられたらなと思います！

我々の先輩方の参加記(Tech_ONS編)もあるのでそちらも合わせてご覧ください！

(ブログ慣れてないのでリンクとか参考とかはTech_ONS編から飛ぶか自分で調べて！)

チーム概要

そもそもチームについてなんですが、他の有名つよつよ大学に比べてうちの大学の競プロer人口が少ないです(それはそう

なので、チームを組むにあたってはサークル内のゲーム制作ニキ(AtCoderにはお触り済み)たちに声をかけて一緒に出てもらうことになりました。

いっちーさん、まんじゅうくんありがとうございました。

準備としては国内模擬の際の１完でやばいと感じつつ、全探索とグラフのおべんきょをがんばったつもりでした(つもりね

国内予選当日

1コマ目の授業が監督の先生の授業だったので終了後挨拶に行って、リハーサルを一通りやって昼食、一つ授業を挟んで14:30にガナリヤさんと同着で会場入り。

なんとなく早く来たものの、普段VisualStudioの設定はそのままでやっているので環境構築RTAの練習もせず、１完はやだなぁとか考えていました。

そんなこんなで16:30になり、コンテストが始まりました。ほとんどのチームはA、Bあたりは分担して解くと思いますが、自分たちのチームはとりあえず３人で１問解こうみたいな感じの方針でした。

A問題は苦戦することなくAC(列が生徒だったのが少し気持ち悪かったですが(転置とったらどーですか

B問題は現在の座標を持って二重ループを回し、始点と終点のマンハッタン距離を測っていきました。しかしサンプルケースの答えが合わずインデックスがずれたか見てると、決定ボタンを押した回数も答えに入れるよと教えてもらい提出。実行時に9sくらいかかってたけど無視して提出したらACでした。

C問題に取り掛かり、mの制約をみて全探索っぺぇ～と思いながら考察へ。見立て通り分銅は「左に乗せる」、「右に乗せる」、「乗せない」の３通りしかないのでO(3^m)だとわかったのですが実装ができん(あれ、全探索。。。

30分くらい詰まったのでいったんDを見に行って、「これ、AtC●derでやったとこだ！」と思いつつよくわかりませんでした。順位表を見てもCを飛ばしてDをACしているチームは少なかったのでまたCに戻って頭を悩ましていました。

長いようで長かった３時間が過ぎ、初めてのICPC国内予選は２完という結果でした。感想としては全探索がしっかりかければ３完できそうだなぁっていうのと、チームでコンテストに参加するのはたのしいってところでしょうか。

今回の後日談(まとめ)

最近競プロ以外のことに目移りしまくりでしたが、ICPCはモチベ上昇にもなってもっと精進したいと思いました。

コンテスト終了後にガナリヤさんにC問題を教えていただいて、そういう勉強会的なのも面白いと思います。(もっと競プロerが増えればやってもいいねっておっしゃっていたのでもっと増えてどうぞ

ぼく個人の目標は今年中にAtCoder水色になることで、来年のICPCでは４完したいですね。(なお今のratingは…

まんじゅうくんも前回のABCでC問題を解けていたので来年は水色行けるでしょ(鼻ほじ←C解けなかったやつ

後輩たちにもどんどん競プロでハラス布教して勉強会できるくらいの人を集めてみたいですね。

来年のICPCに向けていろんな希望をもったところでこの記事を締めたいと思います。

以上、kurokuでした～！(文字だらけでごめんね！

最近，大学で何を学んだんだろう，何をしてきたんだろう，といろいろ複雑なお気持ちな，四年生の老害，ガナリヤです

今回は，07/12(金)に開催されたICPCプログラミングコンテストのインターネット予選の参加記を適当ながら書いていこうと思います

おそらく，あとでYARUDAKEチームからも参加記が上がると思います（上がるよね（老害））

開始前

午前中，授業だったり研究のお話だったり色々と辛いお気持ちになっていました（かなしいね

かなしくなったので，14:30に会場である部屋に先入りしました（今回，監督員の先生には，この時間帯に部屋を予約してもらうなど，多くのご協力をいただきました．頭が上がりません．あとで感謝の品を持っていこうと思います．）

部屋に入る途中，後輩のkurokuくんに出会いました
覚悟がちげえまろ

早く来すぎたかなと思いながら，持参したUSキーボードの準備やパソコンの立ち上げなどをしていました（大学のキーボードはJISなので）

その後，チームメンバーのsiiiecや三年生のいっちーなども来て，時間を無駄にしていました（集合早すぎた，ごめんなさい）

今回，Tech_ONSは全員が四年生で研究室や，自分の場合入試勉強など非常に忙しく，国内模擬予選しか通し練習が出来ていませんでした．
そのため，自作ライブラリはほとんど去年ので，おそらくバグだらけだったと思います（使わなかったので尚良）

今回持ってった本は

の三冊です（普通だな！）

あと，マスコットとして，ニコニコテレビちゃんと，プロ生ちゃんのアクリルスタンドを持っていきました，かわいいね（かわいいので

だらだらsiiiecと話していると，C_avaも来て，打ち合わせをしながら時間を潰しました
全員研究室が違うので，集まるのは大学でもそうそうないんですよね
四年生って研究するけど，研究できなくないか？

そんなこんなしていると，16:30になり，ICPCが始まりました

ICPCコンテスト

問題リンク

順位表リンク

今回のICPCは，去年と同じく最初の方針は同じで

• C_avaがVisual StudioRTAをする
• siiiecがA問題を通す
• ganariyaがB問題を通す
• CはC_avaのC
• Dを三人がかりでなんとかする

みたいな感じでした
あと，誰かが解法を書いている間に，エッチなテストケースを書いて嘘を落とす，みたいな方針でした

プリンターの前でganariyaとsiiiecが待機して，C_avaが印刷をしました

B問題を見ると，あ＾〜ってなる感じの問題でした
簡単じゃ〜んって思いながら，平気でBFS書いていました（無駄）（戦犯）

コンテスト終了後，kuroku君の解法をきいて，マンハッタン距離でいいじゃんってなりました
今回，自分のミスが響いて結構無駄な計算量を書けてしまいました
次のAtCoderなどのコンテストからは，わかっても，一分追加で考察をしてからコーディングを行おうと思いました

B問題の嘘解法（重すぎ）が生えた時，siiiecがコーディングしてました，はやい

C_avaのエッチなテストケースも通ったので，Aを通すと，そりゃもうAcceptでした，嬉しい

（A問題結局どういう問題だったんだろ）

その後，自分がB問題を解いて，当然遅い実行時間でしたが，Acceptはできました
色々と反省が残るコンテストでした･･･

Bをお通ししたあとは，三人でCをいちゃこら考えていました

C問題は，$3^N$で全探索すればいいな〜ってなって，その後ganariyaとsiiiecで詰めながらコーディングしてました

いま思い返すと，このCも実装をミスっていて，実行時間が肥大化してました
本当に思い返すとなんでそんなコード書いてるんだ？ってぐらいしょうもない実装を書いてて悲しくなりました，ほんとだめだめです

C問題を実行しながら，まあ答えが出れば通るやろ〜〜って，言いながらD問題に移りました

D問題は，カウンタをえいえいする問題で，なんかいやらしい問題だなってなりました（ぱっと見簡単だけど，多分むずい）

三人で考察してると，C問題の出力が出たので，投げるとWA（は？

とりあえず紙出力して，自分がCのデバッグ，
siiiecとC_avaでD問題の考察をしていました

Cは結局，分銅を追加しなくてもよい薬は先に取り出す，という操作でうまく行きました
この処理は，最初に提出する前に一度書きかけて「いらないか！」となって消したのですごい悔しい
すべてが裏目に出ている

Cはその後足りない処理を書き足したら，結局通り，再びD問題で停滞しました

三人で色々と考察を行い，C_avaとsiiiecで実装を始め，サンプル地獄になっていました

その後も色々と考え，セグ木＋DP?って思いながら考察してたら非情にも時間になりました

Tech_ONSは今年もまた，3完で幕を閉じたのです

振り返り+老害より

今年のICPCでは，Tech_ONSは
495チーム中，138位で終わりました

お気持ちとしては，悔しいというお気持ちと単純に力不足だったという感覚です

B, Cでガバ考察をしてしまったので，本当に申し訳ないし悔しいです

また，やはり三人がかりでも僕たちだとまだD問題は解けず，これが解けるようにならないと安定してアジアに行けないんだなと思いました（Dの解法は結局DPでした（DはDPのD））

嬉しい点としては，後輩チームが初参加で2完をしていて，頼もしいなと思いました
TNPの競技プログラミングを始めた二年生も合計4人？（自分のおそらくの観測上）になり(最近かなりTNPから増えていて嬉しい)，秋田大学もどんどん競技プログラミングや，他のアプリ制作のコンテストに出て，どんどん秋大が強くなればいいなと思いました

このチームTech_ONSで出場するのはおそらく今年で最後なので，アジアに行きたいなぁと思っていました

結果としては駄目でしたが，非常に貴重な経験が出来たので，競技プログラミングを初めて本当に良かったと思います

来年以降もTech_ONSとして自分が出られるかは現状分かりませんが，来年以降も秋田大学で後輩チームがICPCに参加し，アジア大会への切符を掴んでほしいと思いました．

是非，このICPC・競技プログラミングの文化がTNPに続いて，来年以降の後輩チームが国内大会・アジア大会で活躍する姿を老害として見守りたいなと思います.

ガナリヤでした！

YARUDAKE編も見たいなぁ|・`ω・)

こにゃにゃちは〜〜
ひとまず色々と片付いて，色々と吹っ切れてきたガナリヤです．
将来設計がだいぶ怪しくなってまいりましたねこれは

最近，いろいろとVTuberといい，Twitterといい，ヒリつきすぎていて，嫌な情報社会になってきたなあって感じますね

さて，今回，TNPのメンバーからなる2チーム「Tech_ONS」と「team_YARUDAKE」がICPC国内模擬予選(https://jag-icpc.org/?2019%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8)に参加したので，参加記をまとめておこうと思います（最近投稿も無かったので）

本番一時間前

研究室にこもって面接練習をしていたガナリヤは，ウキウキでTNP部室に向かいました，当たり前ですね
研究室はなんかジメジメしていて，お気持ちが下がるのでア

TNP部室には，すでにsiiiecとkurokuくんがいて，設営が始まってた感じでした

ちなみに僕の所属する四年チームはTech_ONSでganariya, siiiec, C_avaで構成されています．
二年，三年チームはteam_YARUDAKEで2年生二人と3年生ｄ絵構成されています．

設営に取り掛かりましたが，色々な問題が発生してて終始ドタバタしていました．
具体的には

• siiiecのパソコンが印刷機ようになりそうになり，自分のmacbookが候補になる
• 自分のmacbookをディスプレイにつなぐケーブルがない
• C_avaが到着し，Windowsをつけるも，Wifiになぜか繋げない（結局あれはなぜ？）
• siiiecのパソコンをなんとか持ってくる（印刷機PCを別に用意した）
• Visual Studioの設定がうんち（僕はよくわからないので，お気持ち担当していました）

多分，本番当日もグダグダになるので，早めに集まろうね！って思いました，反省

僕はこのグダグダというか，ドタバタしながらコーディングしたり考察するのがICPCの楽しいところなのかな？って気がしますね

デュエル開始！(14:00)

14:00からついに模擬戦が始まりました〜〜
長さは三時間で結構長いねって思うかもしれませんが，全然足りないんですよね（11問でるので，無理）

上記の問題文は(https://jag-icpc.org/?2019%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E5%95%8F%E9%A1%8C%E6%96%87%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E3%82%BB%E3%83%83%E3%83%88)

からお借りしました

僕は印刷係だったので，A・B問題を印刷
C_avaはテンプレートの写経地獄
siiiecはA問題の考察をしてました

A・B問題を印刷し終わったところ，siiiecはA問題の解法が生えたらしい　早い　僕いらなくないですか？

そんなこんなで，C_avaが設定してくれた（縁の下の力持ち）テンプレートで，siiiecがコーディング始める

見た感じ大丈夫そうだったので，僕はB問題に行く

B問題は毒の沼地っていうやつでした．

$100{\times}100$マスのうちに，通れるマスと，毒のあるマスがあります．
あなたは最初$(x_i, y_i)$に居ます．
そして，合計100回$(to_{x_i}, to_{y_j})$に順番に移動したいです．
このとき，毒のあるマスを通る回数を最小にしたいです．合計何回ですか？

みたいな問題です．

0-1BFSじゃ〜〜ん（やるだけか？）ってなり，一応考え直してから，僕0-1BFSの書き方知らないってなる（は？）

C_avaが圧縮しようとしていて，それはつらたんではってなる（ぶん回すのが国内戦だと正義なので）

結局仕方がないので，ダイクストラっぽいBFSで誤魔化す実装をすることにする．
なんとなく書いたところ，案の定プログラムが終わらない．

目grepすると，Q.pop()（priority_queueからポップをしてない）をしてない，これ何回目でしょうか

それを外すと，時間はかかるけどうまく動いているっぽいので，現代のCPUとメモリに感謝を捧げて，siiiecとC_avaが考えているC問題に移る

結局，A問題・B問題はAC出来ました

C問題にうつると，C_avaとsiiiecが唸ってた

C問題もグリッドの内容で
上下左右斜め好きな方向に1マス進むと，その1マス先に，廻小宮が生える．
その廻小宮の太刀筋の位置に入らないように繰り返し移動し，目的にまで行く場合最小回数は何回ですか？

みたいな問題．多分よくわからないと思うので問題文を読んでください

C_avaが図示して，説明してくれた．これ答えでは？

サンプルをみると，なんとなくX座標とY座標の絶対値の足し算に，＋１か−１かそのまま，みたいな感じがある（優しいね）

僕は考えたくなかったので（こういう問題基本的に僕は解けない），とりあえず偶奇で分ける発想に三人で至る

すると大体の場合は上手くいくが，偶数と奇数のときに例外が発生する感じがある．(偶数が0のときと，0以外の偶数のとき)

とりあえずここで，偶奇以外は自分が実装しておいた

すると，C_avaとSiiiecから片方0ならこれ，そうでないならこの処理！みたいな指示が来たので，実装する，実装汚いね（反省します）

ICPCを信じて，お祈り提出をすると通る
テンション上がりますねこれは，これだからICPCやめらんねえんだよなこれ

二回目の提出も通る，嬉しい，サンプルのおかげ　ありがとう全てにありがとう（藤岡弘）

ここで，大体一時間40分経過．ここから地獄のD問題が始まる

D問題は

編集距離のDP問題があるよね！
それに，もう一つの追加で回転（先頭の文字一個を文字列の末尾に持っていくよ）が追加されてるよ！
文字列$X$を文字列$Y$に変形するのにかかるコストを求めてね？

みたいな問題．

ここで発生した問題は，誰一人として編集距離覚えてないことなんですよね（笑い事ではない）

編集距離のアルゴリズムを覚えてないので，その場で自分が編集距離の解法を生やす
半年前の自分が勉強していたので，有能（忘れていたのはぐう無能）

編集距離のアルゴリズムは出たのはいいものの，回転をするDPがよくわからない．

C問題で味をしめた僕たちは，とりあえず回転の回数を全探索しようみたいになって，全探索してみる．

色々試すと，サンプルが合う
これだからICPCはやめらんねえんだよな〜って言いながらSubmitしたら，WAしました

そっからどうしてもD問題の解法が生えない
順位表見ても，また今年もC問題とD問題に大きな崖が出来ていて，やっぱり4完が必須なんだなって思った

C_avaとsiiiecはE問題に行ってしまう（基本的にD解けないときは，Eは絶対に解けないので，今回の国内予選は順位表を見ながらDに専念したい　みんながEを解いてたらEに行く戦法を取りたい）

Eは，最大クリークに落とし込む問題だったみたいです，ライブラリ自体持ってないので（こんなん出してええんか？）

結局Dが解けないまま，三時間が経ちました，無情

結局そういうわけでTech_ONSはABCの3完で180チーム中51位でした．
4完が40チームあるのと，本番は500チームぐらいあるので，やはり4完しないと厳しい感じがします

残り時間もだいぶ短くなってきました．
もう一回アジア大会に出れるように，頑張ろうと思います
ガナリヤでした！

あいさつ

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に向けて日々精進して行きたいです。

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

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

追伸

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

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

こんばんえるえる〜〜
毎度ガナリヤです！
部室行かなくてすいません！活動はしてるんです！集中力の問題で家でやってます･･･(お兄さん許して･･･)
今日は、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頑張ろうと思います！

ガナリヤでした！