投稿者: ガナリヤ

こんばんえるえる〜

研究が一向に進まない四年生のガナリヤです。
本当に進まないです、どこから手を出していいかも分からず、そういう状況になるとさらに研究のやる気がアになります。

そいういう状況なのでTNPのブログに逃げています（おい）
久々のポエム枠です。

競技プログラミングとは

上記を参考にしてください。
日本でいちばん有名な競技プログラミングのサイトのAtCoderが去年書いたブログです。
競技プログラミングの説明や、最近の社会の変化に対する流れが出てきました。

https://atcoder.jp/contests/abc142/tasks/abc142_b

初めて競技プログラミングの問題を解くなら上の問題などがよいです。

– for
– scanf
– printf

が使えれば解ける問題ですね、意外と競技プログラミングは他のアプリ制作やウェブ制作に比べると簡単だったりします

月間競技プログラミングは役に立たない

このブログのタイトルは「月間競技プログラミングは役に立たない」に関するものです。

この#月間競技プログラミングは役に立たない とはなんでしょうか？

競技プログラミングは、いわゆる「アルゴリズム」や「計算量」を考えて、如何に素早くコーディングするか？を競うスポーツです。

例えば上記に上げた問題なら

– forを書ける
– ifを書ける
– scanfが使える

をどれぐらいのスピードで間違いをすることなく書けるか？
という力が身につきます。

また、競技プログラミングはいわゆる「プログラミング筋肉」が身につきます。
どういうことかというと
「ぷよぷよ作りたいんだけど、ぷよが繋がっている判定どう作ろう」
というのが、一瞬で書ける力です。

昔はさっぱり出来ませんでしたが、競プロを初めて一年半ほどたった今は、迷うことなく書けるようになっています（実際に書いていないのでおそらくですが（おい））

競プロの楽しさといえばやはり、土曜日の夜21:00~22:40のコンテストで、リアルタイムに順位が変化するところと、それの結果によって、レートがダイレクトに決まるという点だと思います。
出るだけだとレートは伸びないし、下がることのほうが多く、強くなるしかレートは伸びないです。
ただ、それだけレートが伸びると非常に嬉しい気持ちになれまｓ

そんなこんなで、ハマると楽しい競プロなのですが、10年ほどまえから「競技プログラミングは実務で役に立たない」という論争が毎月のようにTwitterで行われていました。

特に、このころはまだ競技プログラミングの名前が世間で非常に薄く、情報オリンピックもまだ影が薄かった時代です。

そのため、いわゆるアルゴリズムを得意としない（得意分野がアルゴリズムではなく、他の開発系に向いている人）としばしばTwitterで論争が起きていました。

役に立たない時代から(一部)必要とされる時代へ

そんな論争もこのまえもまたTwitterで起きてました。

「競技プログラマーのコードは簡潔で、計算量のためなら可読性を下げたコードを書く。実務にとって、邪魔だし読み辛い」

みたいな論争でした。

ここらへんが勘違いされやすいところですが
「競技プログラマーはできるだけ計算量を減らす人間」ではないです

どちらかというと「計算量考えなくていいなら、簡単な実装・読みやすい実装を選ぶ」人間に、強くなるほどなっていきます。

理由は単純で、計算量の制約ないなら別にどんな解法でも良いからで、楽に書いて早めに提出したほうがレートが上がるからですね。

そんなこんなで、競技プログラマーはたしかに「アプリ」や「システム」「ファイル構成」などは苦手ですが、「汚い」コードとは必ずしもは言えないかもしれないです。

話がそれてきたので戻します（何も考えないで書いているので）

最近（僕はまだ二年弱しかやっていないですが）、非常に競技プログラミングの幅が就活・社会で広がってきているなと感じています。

先週の日曜日、コンテストで東京に行ってきました。

スポンサーは軒並みに太いです（僕は頭わるいし開発がガバなので入れませんが･･･）

競技プログラミングのスポンサーは、ここ数年非常に強いところが揃っています。

• Google
• Yahoo Japan
• KEYENCE
• MUGEN（画像処理＋ロボットアーム　三ヶ月で収入が倍になってるらしい、こわいね）
• Sky（人工知能）
• Free
• KLab(ラブライブの開発とか)
• Future(アルゴリズム、人工知能)

今回のコンテストのスポンサーもYahooと電通で太い感じでした。

どうしてコンテストのスポンサーが比較的強いのかというと、新しい企業ほど（成長率の高い企業ほど）、より強い改革・そして海外に勝つための新しい技術を必要としています。

特に、競技プログラマーの

• アルゴリズム力
• 考察力
• 実装力

を必要としています。（これは罠で、別に競技プログラミングやってない天才のほうが多分多いのですが）

また、DeepLearning系の会社も競技プログラマーを非常に欲しています。

新しいDeepLearningの開発や実装をするとなると、論文の公式を読んでそれを再現すること、そしてさらに拡張することが必要になります。
そういう力が競技プログラマーはすでに持っているため、必要とされるわけです。

先週のコンテストでFutureの人も、競技プログラマーを取る率が高く、競技プログラマーは他のこともできると言ってました

海外だとHackerRankを筆頭に、既に競技プログラミングで就職・転職することが当たり前になってきています。
日本だと情報の流通と、そもそもやる気の差が激しいので広まりません。

ただ、競技プログラミングが求められている仕事があるので
全員がそれにつくべきでないし、ウェブもアプリもゲームもありとあらゆるジャンルが必要であるため、そういうことになってほしくはないのですが
やはりこれからのプログラミングの３大テーマ

• 人工知能
• ビックデータ
• IoT

を考えると、さらに競技プログラミングをやっている人間ほど有利になっていくんじゃないかと思います。
月間競技プログラミングが役に立たない　が　簡単には否定できない時代が来たように思えます。
僕は開発ができないのでアですが･･･

やる気の話

ポエム枠なので、あとまだ寝る時間にははやいのでやる気の話をします。

というのも現在研究室で新しく入るB3と勉強会を一緒にしたい、といろいろとねっているのですが、結局「やる気」の話に陥ってしまうからです。

大学生は結構プログラミングができる子・できない子が非常にはっきりします。
文法が分からず、アプリなど動くものを作ったことがない子も居て、いわゆる下から上まで幾度となく居ます。

ただ、僕が思っているのはみんなプログラミングができないということはなく、むしろ「そういうプログラミングができるようになる機会がなかった」
が正しい表現だと思っています。

僕は１，２年生のころ、文法を暗記することに必死で、無駄な努力をしていました。

当然楽しくありませんし、しょうもないこと（C#のIE系とか）で時間を無駄にしていました。（これは無駄）ラムダ

ただ、僕はゲーム制作、そしてなにより競技プログラミングに出会って、レートが伸びて、オンサイトにいって、ある程度の満足感を得ることが出来ました。

プログラミングができない、やる気のないという人はおそらく、この「成功体験」や「承認欲求」を満たしたことがないんだと考えています。

一度、レートが伸びる、ゲームをプレイしてもらう、アプリを作ってTwitterにあげてFavをもらう、Qiitaに投稿する

こういう成功体験　をしているかいないかで、プログラミングに対する目的意識などが変わるんだなぁって思っています。

話がまとまらないので、まとめるとB3との勉強会でどうやる気を引き出すか？や、そもそもやる必要がないんじゃないか、迷惑なんじゃないか

など色々考えて、僕は何が楽しいんだろうなぁって考えるようになったということです

僕はやる気が他の人よりも強い人間ではなく、趣味もなく、お金をかけたいと思うことがないので（にゃん）

僕はゲームジャムは非常に賛成で、きっかけさえあれば、プログラミングが嫌い・できないが少しずつ変わると思っています。（コンテストがあって出れませんでした、ごめんなさい（次は是非出たいです！））
ゲームジャム・アプリ制作・競技プログラミング・Qiita・ウェブ制作、など、何でもいいのでなにか作ると決めて、それを外部に公開して遊んでもらう、成功体験をするのが大事なのだなぁと（終りが見えなくて焦っています）

寝る時間になったのでにじさんじ見て寝るます

グダグダ書きましたが、研究が進んでいません。
こういうダメ人間にならないように、やる気がモテる人間になってください
僕はそういう人になれなかったので、きょうも進んでいません

なんかつまらない話・ポエムすぎるのと、暗いので次の記事では「本当の技術系（Neo4jらへん）」か「にじさんじの推しライバー」を書きます

見返してないので、結構変なこと書いてるかも

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

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

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

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

追伸

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

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

ここから下の内容は一個人の意見・推論です

来たる新入生へ

合格おめでとうございます。

これから始まる新生活に、新入生の方々は胸踊らせ、日々楽しみ、もしくは多少の不安を感じていることでしょう。

そう、４月は始まりの季節。

楽しいことや不安なことが一気に押し寄せ、この時期はかなり精神的にブレが生じる時期でもあります。

そして、この時期はパソコンを買い換える時期で、大学に入学準備に行くとパソコンを勧められます。

彼らは学生の味方です。しかし、営利団体でもあります。
儲けを出さないといけません。
そこは理解しないといけません。

パソコンの話

合格が決まると、彼らは大学にきて、彼らの一員になることを強いてきます。
これは仕方ありません。彼らの意見を飲みましょう。
ここは気持ちを抑えてスパイになるのです。

ただし、生協パソコンは買う前には色々と考え直してみましょう。
多くのTNP部員が被害にあっています。

彼らはかなり低スペックのPCを高い値段で売ってきます。
おそらく彼らの言い分は

「保険がつく」だの
「パワポがつく」だの
「頑丈」だの

電気店でも言われることを言ってきます。
鵜呑みにしてはいけません。自分で考えて行動しましょう。

同じ値段でどれ位のパソコンが買えるでしょうか？

例えば、「MacBook　Pro」が買えます。

ほぼ同じ値段で、保険がつき、Macというかっこいいものが買えます。
Macはプログラミングのおける環境構築がWindowsに比べて遥かにしやすくUIも統一されています。
･･･Linux?そういうのもあるのか

僕はMac派なのでMacを押します。
現在、キャンペーン中なので、割引＋二万円キャッシュバックがついてきます。

さらにMacのいいところは、売るときの値段が大体買った値段の半分です。
これが強い

持ち運びじゃない、デスクトップならiMacが買えますね。
そこそこのスペックが買えます。
四年間のプログラミングには有り余る性能があります。

Windowsがいい？？
ならば、Surfaceなどの選択肢があります。
薄くて使いやすく性能もいい。
生協パソコンが駄目とはいいませんがなにかと入らないものがついていたり、彼らの懐にはいるお金がおそらく多い。

BTOもありです。

私がいいたいのは、生協パソコンに甘んじてはいけないということです。

最後になりますが、まだ間に合うのなら、他のMac製品や、Windowsパソコン、BTOなどを見てみるといいです。

大学では優しい人もいますが、汚い大人がうじゃうじゃいます。
自分で考えて行動すると良さそうです。

ガナリヤでした

追伸

自分で選んだパソコンでのプログラミングは非常に楽しいです！！！
四年間付き合うと思って大事に選んであげてください！！！
Macはいいぞ！(後方彼氏面)

こんにちえるえる〜〜

なんか久しぶりですね。

ガナリヤです。新しいバージョンにしたせいか、色々と不具合が起きて辛いです･･･なんとかします･･･

WordPressのバージョンが上がった話、使い方とLaTeXの話をします

WordPressのバージョンが上がった話

WordPressというシステムを現在、TNPでは使っています。

WordPressはPHPで構成されているフレームワークであり、拡張しやすく、これまでブログよりも使いやすい点があります。
また、WordPressに移行した理由として

• 全員が使える。
• HTMLを知らなくても書ける（ビジュアルで書ける）

という点があります。

現在、そのバージョンが上がり、新しいエディタGutenbergというものが導入されました。

このエディタでは、ブロック構造が採用され、各段落を一つのブロックとして構成します。

上記の段落は、以下の図のようなブロックとしてなっており、ブロックは自由に移動できます。

今回のエディタによって、よりノンプログラミングにブログをかけるようになりました。

ただ、これまでのブログのエディタに慣れていた人には辛いですが(現在辛いです･･･)

使ってみると分かると色々と分かると思います〜

マークダウンを使うときは

プログラマーには、マークダウンというものに慣れている人がいます。
僕もその一人です。
マークダウンを使うとより高速にブログを書くことが出来ます。(ビジュアル操作を気にしなくていいと言うと伝わりやすいでしょうか･･･)

現在のエディタでマークダウンを書くには以下のようにしてください。

自分のパソコンの「Boostnote」などでマークダウンを書き、ブロックにコピペしてください。

すると、自動でマークダウンから、普段どおりの大きさやリスト、水平線に変換されます。

よって、現在は、このWordPressエディタ上でマークダウンはかけません。(一部はかけます。)
これからWordPress上で書けるようにする方法はないか模索します。

改行の仕方

ブロックごとに書きますが普通に改行すると(エンターを押すと)

このように一行多く空きます。

なので、ブロックないで改行しようかな〜〜ていうときは「Shift + Enter」をしてください。
すると、一行多く空けない通常の改行ができます。

コード挿入の仕方

ソースコードを挿入したい時があると思います。
そのようなときは以下のようにしてください。

「フォーマット」に入っている「Highilghing Code Block」というものを選び、ソースコードを挿入してください。

すると、ソースコードを挿入できます。

LaTeXの使い方

プログラミングの記事を書くときは
変数を$x$としたり、
$$ y = 10x + 2$$

のように数式を使いたくなると思います。

これはLaTeXというもので実現できます。(TeXがもとであり、それを拡張したものがLaTeXだと思っていいかと思います。)

LaTeXを書くには半角の「ドルマーク $」でLaTeXしたいものを囲ってください。

つまり、　＄x＄と言った感じです。(これは、ドルマークを全角で表現しています。ここで半角にしてしまうと、LaTeXになって、どのようになるかが表現できないので･･･)

よって、LaTeXしたいときは、半角のドルマークで数式などを囲ってください。

また、中央に
$$ y = x$$

のように表示したいときは半角のドルマークを
＄＄ y = x ＄＄

のようにすると、中央寄せができます。

最後に

多分伝わらないと思います･･･(すいません）

今度部室で使い方をきちんと説明したいと思います。
また、実際に触ってみると使い方がわかると思います。

自分もまだこれに慣れてないので、大分読みづらいかと思います。すいません。

改善できるようにいろいろ工夫していこうと思います。

ガナリヤでした〜

こんばんえるえる〜〜〜〜
ガナリヤです
大学の後期がついに始まりましたね
今週一週間は毎日しんどくて未だに体の疲れが取れません。
コミュニケーション能力を付けないとこのままではまずい気がします。

今回は、AtCoderBeginnerContest112に出ました。
結果としては、ABCD4完は出来ましたが、Cで4WAしているのでもうちょっと細かい部分に意識をしないといけませんね･･･
早速内容を振り返っていきましょう！

A 「Programming Education」

問題文

AtCoderはクソデカ年商となり、プログラミング教育をするようになった。
入力から自分の年齢Nが入力される。
N=1なら”Hello, World”と出力せよ。
N=2ならA+Bの答を計算せよ。

解法

やるだけです。
もう20秒ぐらい早くとけるようになりたいです。

B 「Time Limit Exceeded」

問題文

Xさんは、外から家に帰ろうとしています。
現在位置から家に帰るルートは、N個存在しますが、それぞれに係る時間tiと、かかるコストciがあります。
時間T以内に、帰らなければいけない時、最小のコストを求めてください。

解法

時間T以内なので、時間T以内のルートのみを列挙して、さらにその中でも一番コストの低いものを出力してしまえばいいです。
気をつける点としては、ルートが一つもない場合はTLEと出力しないといけないので、最初の変数の初期化で上限いっぱいにしておいて、値が更新されてなければTLEとしないといけません。
実装に2分もかかったので半分ほどにするひつようがあります。

コード

int main() {
 
    LL N, T;
    cin >> N >> T;
 
    LL cost = LONG_LONG_MAX;
    for (int i = 0; i < N; i++) {
        LL c, t;
        cin >> c >> t;
        if (t <= T) {
            S_MIN(cost ,c);
        }
    }
 
    if(cost == LONG_LONG_MAX){
        OUT_L("TLE");
    }else{
        OUT_L(cost);
    }
 
    return 0;
}

Pyramid

問題文

問題文長すぎるのでここを見て→ https://beta.atcoder.jp/contests/abc112/tasks/abc112_c

解法

内容としては簡単だったのですが、3つ特殊ケースがあり、そのケースに気づくまで時間がかかってしまいました。

制約を見るとCxもCｙも0~100以内なので、全探索しても余裕で間に合うことが分かります。
中心のCx、Cyを仮に全探索してみます。
すると、中心の高さHを求めたいわけですが、この高さは他の点1つを選んでしまえば逆算することが出来ます。
そうして求めたHと他の点を全て比べて、条件を満たせばそれが答えになります。

しかし、この解法だけだとうまくいかない場合があり、参考にする点が高さ０の場合です。
高さ０の場合、もともと高度は(H -|X – Cx| – |Y – Cy|, 0)のため、マンハッタン距離で0だったのか、最初から0だったのか判断することが出来ません。
よって、関係ない答を出力してしまう可能性があります。
よって、そのケースは省いて計算する必要があります。
体感的にBレベルでしたが、特殊ケースだけはDレベルな感じがしました。

コード

int main() {
 
    int N;
    cin >> N;
 
    VLL x(N), y(N), h(N);
    REP(i, N) cin >> x[i] >> y[i] >> h[i];
 
    for (LL i = 0; i <= 100; i++) {
        for (LL j = 0; j <= 100; j++) {
            LL H = 0;
            for (LL k = 0; k < N; k++) {
                if (h[k] != 0) {
                    H = h[k] + ABS(i - y[k]) + ABS(j - x[k]);
                    break;
                }
            }
            if (H <= 0) continue;
            bool good = true;
            for (int k = 0; k < N; k++) {
                LL _h = C_MAX(H - ABS(i - y[k]) - ABS(j - x[k]), 0LL);
                if (_h != h[k]) good = false;
            }
            if (good) {
                cout << j << " " << i << " " << H << endl;
                return 0;
            }
        }
    }
 
    return 0;
}

D Partition

問題文

整数N, Mが与えられます。
a1 + a2 + ･･･ + aN = Mとなるような長さNの数列aにおいて、a1~aNの最大公約数となる最大値を求めてください。

解法

Mが与えられるので、可能性のあるaの組み合わせを作成し、その最大公約数を求める必要があります。
最大の最大公約数であるため、少し工夫しないといけません。なぜなら、制約でNが10万のため、計算量的にNlogNが最大であるためです。

そこで、最大公約数について一度考え直して見ます。
最大公約数は、a全てにおいて、共通の約数を持っており、共通の約数ということは同じ倍数を持っているということに等しいです。
共通の倍数をKとすると
Kb1 + Kb2 + ･･･ + KbN = Mということになります。
つまりM = K * (b1 + b2 + ･･･ + bN)というわけで、Mは因数としてKを持つことが分かります。
よって、Mに対して、約数を列挙し、その約数の中で、NをかけてもMを超えないものが答となります。
約数をTとして、TN < Mのとき、数が余らないか？というう話になりますが、Mも因数Kを持つため、うまく配分すれば全ての変数がKを因数に持つことが分かります。

素因数分解はO(√N)でできるので、計算量的にも間に合うことが出来ます。

今回のDは3分で通せたので、成長を感じます。(なお、C)

コード

//nの約数
template<typename T>
vector<T> DIVISOR(T n) {
    vector<T> v;
    for (LL i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            v.push_back(i);
            if (i != n / i) {
                v.push_back(n / i);
            }
        }
    }
    sort(v.begin(), v.end());
    return v;
}
 

int main() {
 
    LL N, M;
    cin >> N >> M;
 
    auto divisors = DIVISOR(M);
    LL maxV = 1;
 
    for (int i = 0; i < SZ(divisors); i++) {
        if(divisors[i] * N <= M){
            maxV = divisors[i];
        }
    }
    OUT_L(maxV);
 
    return 0;
}
 
 

###　感想

今回の問題は、Cが一番難しかった感じがあります。
4WAは流石に出しすぎなので、もうちょっとミスを減らさないといけませんね･･･

ガナリヤでした！