ゲームジャム(夏休み編)

はじめに

 こんにちは。2年次のまんじゅうです。
記事を書くのは初めてなので、変なところとかあるかもしれないですが、どうか温かい目で読んでくれればと思います。

 今回のゲームジャムは8月14日と15日に開催しました。お盆でしたがそこそこ参加者がいて嬉しかったです。
 また14日、15日のどちらも猛暑日だったので、誰も熱中症にならなくて良かったと思います。

 今回はお題に沿って何か作るのではなく、なるべく自分で考えて制作する、という方向で企画していました。
 そのため、お題ではなく、あくまで何を作るか思いつかない人への救済措置として「倉庫」、「火」、「駐車場」、「重力」、「落とす」という単語を提示しました。

作品紹介

1年次 UMA

開発環境 DXライブラリ

 初年次講義で扱った「フラッピーバード」のソースコードを元に作ったそうです。
飛んでくる敵を避けたり、うまく弾を当てたりしてスコアを稼ぐゲームとなっています。
 元にしたゲームがある、という点を加味しても、初めての制作物としては完成度が高いと思いました。

2年次 たか

開発環境 DXライブラリ

 卍型の自機が卍の先端から放つ攻撃を敵に当てる、というゲームのようです。
攻撃を放つと、次の攻撃が可能になるまでの待機時間が発生したり、敵がランダムで生成してされた瞬間に攻撃されないよう、
敵の攻撃不能時間を設定していたりと、細かいところまで作り込んでいると感じました。

2年次 まんじゅう

開発環境 Siv3D

 「街コロ」というボードゲームを作ってみようと頑張ってました。
ダイスを振る機能と、出た目による建物の効果の処理は実装できたのですが、
 時間が足りなかったために建物購入の処理が完成せず、ゲームとしてはまだ成り立っていない状態です‥。

2年次 ズッキー

開発環境 Unity

 今年の夏コミに出した迷路ゲームを改良したものだそうです。
ランダムで壁を生成するようにし、それによって起こりうる詰み状態を防止するために壁を壊す機能を追加したそうです。
 また、壊した壁の種類と枚数によってゲーム終了時のスコアが増減するようにして、高いスコアを出すにはしっかり迷路を歩かないといけないようになっていました。

3年次 いっちー

開発環境 Unity

 なんと時間内に2作品完成していました。
 1つが火事の建物から人を避難させるゲームで、円形の足場を操作して障害物を避けつつ、小島まで避難させる、というものでした。
足場で人がバウンドする上に、小島が小さいため、難易度は高そうに見えました。


 2つめが、人を前に飛ばして、乗るとジャンプするキノコを駆使して停止するまでの距離を競うゲームでした。
地面に人がぶつかって転がり、その先のキノコに当たってまたジャンプ、という動きをしていたので、見ていて面白かったです。

3年次 うおちー

開発環境 Unity

 下に重力がかかっている空間で、上下に移動して火の玉を避けるゲームです。
当たり判定が実装できていないとのことですが、ゲームとしてはほとんど完成しているように感じました。

最後に

 やっぱりゲームジャムは良いですね。
他の人のアイデアやコードの組み方などを見て学べる機会になりますし、自分の制作活動への意欲も高まります。
 夏休みは長いのでだらけてしまいがちですが、今回の会でのやる気を思い出して頑張って制作していこうと思います。

ICPC2019国内参加記 Tech_ONS編

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

今回は,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編も見たいなぁ|・`ω・)

ICPC国内模擬戦2019 Tech_ONS参加記

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

最近,いろいろと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年生d絵構成されています.

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

  • 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座標の絶対値の足し算に,+1か−1かそのまま,みたいな感じがある(優しいね)

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

すると大体の場合は上手くいくが,偶数と奇数のときに例外が発生する感じがある.(偶数が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完しないと厳しい感じがします

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

ゲームジャム(GW編)

はじめに

こんにちは、会長のいっちーです。

今年のGWは10連休ということで、4/30と5/1の2日間でゲームジャムを行いました。

今回のテーマは「秒殺」「通り魔」「結ぶ」「昇天」「でくのぼう」。

前回もそうでしたが、ゲームジャムのテーマとしてこの選択はどうなんでしょうね。


作品

2年次 ずっきー

開発環境「Unity」

「秒殺」をテーマとしたホラーゲームです。

女の子を操作して、迫りくる化け物から逃げようとしますが...。

とあるゲームを参考にしたようで、テーマの「秒殺」もそれに関連しているとか。

綺麗なグラフィックが臨場感溢れるホラーな雰囲気を醸し出しています。完成が楽しみですね。


2年次 でんそん


開発環境「DXライブラリ」

「秒殺」「結ぶ」をテーマとした謎解きゲームです。

プレイヤーを操作して、マップに描かれている白いサークルを正しい順番で触れていくと次への道が開かれます。また、色付きのブロックには

  • 緑ブロック:触れるとヒントが得られる
  • 青ブロック:取ると復活時に”寿命”が延びる
  • 赤ブロック:通り抜けられない壁

というように謎を解く上での重要な要素となっています。

なお、”寿命”とはこのゲームにおける制限時間のことで、プレイヤーの頭の上にあるカウントがそれを示しています。寿命は移動している間も減り続け、0になるとゲームオーバーとなります。

ゲームオーバー時にはその場で復活してやり直すことができますが、初期状態での寿命は”3秒”だそうで、まさに「秒殺」といえますね。


2年次 まんじゅう

開発環境「DXライブラリ」

「結ぶ」をテーマとしたボードゲームで、”カルカソンヌ”というゲームを参考にしたようです。

草原や道、城などが描かれたパネルを一枚絵になるように配置し、そこに人を置いていくことで得点が得られるようです。

マップのスクロールやパネルを置く・回転させるといった、ゲームの基本要素を完成させました。

しかし、パネルや人の置き方にはかなりの自由度があるようで、本人曰く「大変なのはこれから」とのことでした。


3年次 いっちー

開発環境「DXライブラリ」

「昇天」をテーマとしたアクションゲームです。

幽霊を結界で囲み、結界を強化することで幽霊を昇天させることができます。また、幽霊は結界の境界線で反射するようにしました。

前回のゲームジャムでは時間内に完成できなかったため、今回はとにかく完成させることを目標に取り組んでみました。

素材は”いらすとや”でお借りしたのですが、統一感を出そうとした結果、ハロウィンテイストになりました。


おわりに

ゲームジャムはいいものですね。

テーマと時間が縛られている分、普段よりも集中して取り組めたように思いますし、他の人のゲームのアイデアやその実装方法にはとても興味が引かれ、良い刺激になりました。

今回は3年次が私1人、2年次が途中参加を含めて5人とまだまだ参加率は低いですが、初参加の方もいたので、この調子でサークル内で少しずつ広まっていければなと思います。

また、今月からは本格的に初年次講義が始まります。今度は1年生も含めてペアプログラミングなんかもやってみたいですね。

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

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

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


追伸

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

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

C++が使えたい 項目7(現行のC++への移行 – 1)

サバです。
3章にはいります!

今回も、表とその下の解説は無駄に長いので、適当に流し読みしてください!

 

 

<以下長い注意>
ここの内容は、サバが適当な自己解釈を重ねた結果、攪拌され白濁してしまった知識の泉から、沈殿物を素手で持ち上げようとした結果です。保証はしかねます。ご了承ください。

内容はEffectiveModernC++をわざわざ書き写したような何かです。
題名にEffectiveModernC++が入っていないのは更新が途中で止まる自信があるからです。

また、もしよろしければ、間違い、気になったところ、分かりづらいところなどを指摘してもらえると、サバがピチピチ跳ねて喜びます。喜びすぎてプログラミング言語C++第四版をあなたに投げつけるかもしれません。
(ぜひ教えてください。よろしくお願いします。 < ( _ _ ) > 何でもするとは言いませんから…

 

 

 

項目7 オブジェクト作成時の()と{}の違い

結論:{}を使うならstd::initializer_listコンストラクタに気をつける

 

C++11はオブジェクト作成時の初期化に(){}を使い分けられます。ただし、組み込み型(プリミティブ型)変数の初期化には = も使えるため、初期化代入がごっちゃに理解されることが多いようです。自分もそうでした。

 

 

 

 

・初期化方法まとめ

重要なのは組み込み型の = 初期化特殊であることです。
ここではユーザ定義型(構造体・クラス)の例として Widget という型名を用います。

組み込み型
(クラス・構造体以外)
int Integer1 = 0;
int Integer2( 0 );
int Integer3{ 0 };
すべて同じ意味
0 で int 型変数を作成・初期化
= でも初期化をすることができる
初期化であって代入ではない
ユーザ定義型
(クラス・構造体)
Widget widget1( 0 );
Widget widget2{ 0 };
すべて同じ意味
Widgetのコンストラクタに 0 を渡して、Widgetオブジェクトを作成・初期化
  • ここにでは省略しましたが、{} の代わりに = {} も使用できます。全く同じ意味です。
  • ちなみにユーザ定義型で、下コード widget5 のように初期化をしない場合、デフォルトコンストラクタによって暗黙的に初期化されます。個人的には初期化を忘れたバグの根源なのか、デフォルト初期化したいのかが分からないので、widget6 の明示的初期化が良いと思います。
    Widget widget5;
    Widget widget6{};
    どちらもデフォルトコンストラクタで初期化

  • コンパイラによっては1変数を受け取るユーザ定義型のコンストラクタなら = でも初期化できるようです。

 

 

 

 

 

・初期化の統一記法

C++は変態なので変数を初期化する場所・場合がたくさんあります。
そんな中でも {} だけは統一的にすべての初期化を行うことができます。{}すんごい!!

組み込み型int integer1 = 0;
int integer2();
int integer3{};
= () {} 全てで初期化できます。
全てデフォルト値0での初期化です。
ユーザ定義型 Widget widget1();
Widget widget2{};

// NG : 二度手間
Widget widget3 = Widget{};

= では期待通りの初期化はできません。一時オブジェクトを作成し、ムーブコンストラクタでムーブ初期化するという二度手間になります。
(最適化されなければ)
宣言初期化子 class Widget
{
    int member1 = 0;
    int member2{};

    // メソッド?
    int member3();

};
() では初期化できません。
コンパイラにとってはメソッド
(メンバ関数)宣言にしか見えません。
コンストラクタ初期化子class Widget
{
    int member1;
    int member2;

public:  
    Widget(int value)
        : member1{ value }
        , member2( value )

    {}
};

= では初期化できません。
メンバを初期化するためのもので、代入するためのものではありません。(適当に理由を付けました)
コピーできないオブジェクトstd::atomic<int> ai{ 0 };

// Error : 関数は削除されてる
std::atomic<int> ai =
        std::atomic<int>{ 0 };

コピーやムーブを出来ないように設計されたオブジェクトは = 等を使えません。

左の例ではムーブコンストラクタが消されているため、エラーとなります。

template
との組み合わせ
template<typename T> decltype(auto) func()
{
    // どっち?
    return T::Whats();
}
こんな状況で () 初期化を使うのはやめましょう。Whats という static 関数呼び出しにしか見えません。
このコードで Whats オブジェクトの初期化をしていた時は、
バグの発見に大分骨を折りそうです。
  • 上の例を見ると {} だけいつでも初期化に使えることが分かります。

 

 

 

 

 

 

・ {} 初期化の型チェック機能

{} 初期化は統一記法以外にも型チェックという利点があります。
縮小変換(精度が落ちる変換)が必要な初期化が行われた場合、コンパイラがエラーを出してくれます。(コンパイラによっては警告)

int  pi { 3.14 };              // Error

double
  x{}, y{} z{};
int  sum { x + y + z };    // Error
 double 型から int 型への暗黙的な縮小変換
 (精度が落ちる・値が壊れるような型変換)
bool flag { 2 };               // Errorint 型から bool 型への暗黙的な縮小変換
  • エラーを避けるためには static_cast を使いましょう
    int pi{ static_cast<int>( 3.14 ) };

 

 

 

 

 

・{} 初期化の落とし穴

{} は凄い!ですが、致命的な問題があります。
それは std::initializer_list との相性問題です。
std::initializer_list を取るコンストラクタを持つオブジェクトを {} 初期化すると、縮小変換をしてでも、力ずくでこの std::initializer_list コンストラクタを使おうとします。

class Widget
{

    // コンストラクタ1
    Widget( int value )
    {}
    // コンストラクタ2
    Widget( std::initializer_list<bool> list ) 
    {}

};

int main()
{
    // コンストラクタ2を呼び出す
    Widget w{ 100 } // 縮小変換 Error も

    return 0;
}

main 関数内で、Widget の
コンストラクタ1
を呼び出しているように見えますが、
コンストラクタ2
が呼び出されます。
 

コンストラクタ1 を呼び出すには () を使った初期化をする必要があります。
 

また、{} 初期化は型チェックを行うため、この場合 Error や Warning が発生します。

  • コンパイラには {} が std::initializer_list にしか見えないのでしょうか…
  • 力ずくで変換できない場合、つまり、暗黙の型変換方法がない場合は、こんなことになりません。 例えば、std::initializer_list<bool> ではなく、 std::initializer_list<std::string>であった場合は、int 型から std::string 型への暗黙の型変換方法がないため、コンストラクタ1 が呼び出されます。

 

残念ながらこの相性問題の代表例は STL です。
std::vector も std::initializer_list をとるコンストラクタを持つため、こんな頭痛が痛い問題が起きます。

// { 10, 1 }
std::vector<int> vec1{ 10, 1 };
要素数2で、それぞれの値が 10, 1 となる
std::vector を作成
// { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
std::vector<int> vec2( 10, 1 );
要素数10で、すべての値が 1 となる
std::vector を作成
// { 100 }
std::vector<int> vec3{ 100 };
要素が 100 のみで要素数1となる
std::vector を作成
// { 0, 0, 0, … ( x 100) }
std::vector<int> vec4( 100 );
要素数100で、すべての要素をデフォルト値( 0 )で初期化した std::vector を作成
  • std::vector は {} だけじゃすべての初期化ができない… {} は初期化の統一記法じゃなかった!!!

 

初期化するオブジェクトに std::initializer_list をとるものがないか事前に確認しましょう。std::initializer_list をとるコンストラクタを定義するときは本当に必要なのか考えましょう。

 

 

 

 

 

 

Effective Modern C++ の中では、(), {} どちらの初期化も長所・短所を持つため、いずれかの記法を優先して使うように決め、必要に応じてもう一方を使おうとまとめられています。

 

 

 

 

< 前の項目へ   次の項目へ >  // そのうち…

C++が使えたい 項目6(auto – 2)

サバです。
autoについては最後の項目です(まだ二つ目)

 

<以下長い注意>
ここの内容は、サバが適当な自己解釈を重ねた結果、攪拌され白濁してしまった知識の泉から、沈殿物を素手で持ち上げようとした結果です。保証はしかねます。ご了承ください。

内容はEffectiveModernC++をわざわざ書き写したような何かです。
題名にEffectiveModernC++が入っていないのは更新が途中で止まる自信があるからです。

また、もしよろしければ、間違い、気になったところ、分かりづらいところなどを指摘してもらえると、サバがピチピチ跳ねて喜びます。喜びすぎてプログラミング言語C++第四版をあなたに投げつけるかもしれません。
(ぜひ教えてください。よろしくお願いします。 < ( _ _ ) > 何でもするとは言いませんから…

 

 

項目5 auto が期待とは異なる型を推論する場面では ETII を用いる

 

結論:autoは明示的キャストと併用しよう

ETIIはC++的で明示的な型キャスト、static_cast を使ってauto変数を初期化する方法です。

auto itsInteger = static_cast<int>(64 * 0.2);    // キャストでint型変数として推論させる。
  • これを使ったらauto使えるし、どんな型と目的でキャストしてるのか明示的でわかりやすいよね!って話です。

 

また、std::vector<bool> を使うときにこの操作が必要な場合があります。
というのもstd::vector<bool>の [ ] 演算子は bool& ではない変な型を返してくるからです。

std::vector<int> vecInt = {1, 2, 3};
decltype( veclnt[0] );
auto front = vecInt[0];
decltype → int& // 分かる。内部要素への参照。
front       → int   // 期待通り。
std::vector<bool> vecBool = {true, true};
decltype( vecBool[0] );
auto front = vecBool[0];
decltype → std::vector<bool>::reference // WTF
front       → std::vector<bool>::reference // WTF

うーんこの…。そこでこの std::vector<bool> 使う時だけETIIしよって話です。

std::vector<bool> vecBool = {true, true};
auto front = static_cast<bool>( vecBool[0] )
front → bool   // 期待通り
  • もちろんbool型以外のstd::vectorはこんなことないです。ふつうです。こいつが変態なだけです。
  • めんどい…
  • 今にでもstd::vector<bool>に殴り掛かれそうなら、殴り掛かる前に下の内容を読んでみてください。

 

 

 

・深淵を覗きに行くために…

std::vector<bool>はうん○こ。ではなくちゃんと理由があるみたいです。

bool型のベクターはメモリを節約するため、内部でビット演算を使用して値を保持しています。となると、要素一つあたりのサイズは1ビット。でもC++の参照が指し示すことができるのはバイト単位…(参照は内部的にはポインタであるため)あれ? ビット単位な各要素への参照ってできないじゃん。じゃあ参照受け取って、各要素の値を直接変更するとかもできないじゃん! って当然なるわけです。

そこでstd::vector<bool>::reference君の登場です。下記のコードのように、ぱっと見いい感じに動作するよう彼は実装されています。この書き方だけならいつもの通りです。

std::vector<bool> vecBool = {false, false};
vecBool[0] = true;
vecBool[1] = true;
{false, false} // vecBool の中身
{true, false}
{true, true}

 

しかし、上記の注意点だけでは終わらず、追加でもう一つが紹介されています。
それは[]演算子の戻り値は値渡しでも、実質的には参照渡しであるということです。
例を挙げると、以下のようなコードは未定義動作です。

auto first = std::vector<bool>{false, false}[0];   //参照渡しと実質的に同義な値渡し
first = true;                                                        // 死んだオブジェクトに代入する未定義動作
  • std::vector<bool>::reference 君は、各要素を参照してるっぽく動作するため、ビットとして存在する実態にアクセスするための情報を持っています。実装方法によっては、ポインタとそこから何ビット目かといった感じの情報です。
  • 上記例では、std::vector<bool>::reference を first は受け取ります。そのため first は std::vector<bool>{false, false} と宣言された右辺値の内部を指し示すポインタを持つことになります。
  • 右辺値は一行だけの命です。つぎのセミコロンが来たらそこで死にます。
  • つまりfirst = true と代入している時点で、first 内部のポインタは、すでに死んだvectorが存在していた位置を指し示します。このコードは代入によってメモリ空間をぐちゃぐちゃにできるわけです。
  • このようなバグは、関数の戻り値(値渡し)でももちろん起こりえます。
  • std::vector<bool>怖い…

 

std::vector<bool>::referenceのような、ほかの型の模倣や拡張を目的としたクラスを、プロクシクラス(proxy class)とか言うらしいです。

このようなクラスの存在に気づくためには、ヘッダファイルの実装を自分で見ようねという話みたいです。C++楽じいなぁ…

 

C++は楽しい。

 

 

< 前の項目へ   次の項目へ >  // そのうち…

C++が使えたい 項目5(auto – 1)

サバです。
前回の記事は投稿後に大分変更・加筆をしたので、チラ見してくださいお願いします。
それに加えて、詰め込みすぎたので今回から1項目くらいずつで行きたいと思います。

 

<以下長い注意>
ここの内容は、サバが適当な自己解釈を重ねた結果、攪拌され白濁してしまった知識の泉から、沈殿物を素手で持ち上げようとした結果です。保証はしかねます。ご了承ください。

内容はEffectiveModernC++をわざわざ書き写したような何かです。
題名にEffectiveModernC++が入っていないのは更新が途中で止まる自信があるからです。

また、もしよろしければ、間違い、気になったところ、分かりづらいところなどを指摘してもらえると、サバがピチピチ跳ねて喜びます。喜びすぎてプログラミング言語C++第四版をあなたに投げつけるかもしれません。
(ぜひ教えてください。よろしくお願いします。 < ( _ _ ) > 何でもするとは言いませんから…

 

 

 

項目5 明示的型宣言よりも auto を優先する

 

結論:いいものはどんどん使おう!

IDEあるならとりま使いましょう。ぐう有能。
(もちろん注意するとこもあるみたいですが…

具体的な使用例(特に変数宣言範囲for文!!)

変数宣言auto value = 0; int
範囲for文for (const auto& content : container) { }範囲for文 + auto&は最強
関数の戻り値auto func(){ return “auau”; }const char *
ラムダ式の引数 auto lambda = [](auto& arg)

    std::cout << arg;
};
これはC++14以降の機能

 

 

 

 

・auto ? なにそれおいしいの?

    つ autoはおいちい。(前回の記事)
   もし良ければ下にある「autoの利点」もどうぞ…
     ( このサイトが大好き。 : cpprefjp) // 神様です。いつもありがとうございます。
  

 

 

 

 

・深淵を覗きに行くために…

 auto の利点

 ・変数の初期化忘れがなくなる

    auto i = 0;
  • 型推論のために必ず初期値を指定する必要がある。

 

 ・コンパイラが適切な型を選んでくれる

    std::vector<int> vec;
    auto size = vec.size(); 
  • std::vector<int>のサイズを表す非負整数型は std::vector<int>::size_type だけど、そんな長いの覚えてコーディングする必要がなくなる。

 

 ・労力が減る

    std::vector<int> data(10)

    for (auto& val : data)
        std::cin >> val;

    for (auto ite = data.crbegin(); ite != data.crend(); ++ite)
        std::cout << *ite << std::endl;

  • 入力から10個の整数を受け取って逆順で出力するプログラム
  • std::vector<int> の int を書き換えるだけでどんな型にも対応できる(double, std::string, long, etc…)
  • イテレータの型指定で悩むこともなくなる
  • コンパイラに任せた方がヒューマンエラーは減る。楽しよう!

 

 

私は脳死して使うようにしています。autoだいしゅき。
C++に追加されたということは、いいからだまって使えという機能のはずですから。(盲信)

 

 

< 前の項目へ   次の項目へ >