CODE FESTIVAL 2018 参加記
「参加記」というのはエンジニア方言のようです。気づかないうちに語彙が侵食されていくのはこわいですね。
DTM班長のLgeuです。
11月17日(土)に開催されたCODE FESTIVAL 2018に参加したので、参加記を書きます。
CODE FESTIVAL 2018とは?
これです。 www.recruit-jinji.jp
予選
予選A(9/22)
CODE FESTIVAL 2018 qual A - AtCoder
500点が解けず惨敗。解答見たらDPだったので今までDPを全然勉強して来なかったことを反省しました。
予選B(10/14)
CODE FESTIVAL 2018 qual B - AtCoder
100点と200点は順調に突破。さて500点問題は……
え、これただ十字型のペントミノを敷き詰めるだけじゃん?
ぱぱぱっと実装。2回バグらせつつ22分でAC。
700点問題……はまるでわからず、3完で終了。
結果は61位。500点を早解きできたのことと、700点が難しくて解けた人が少なかったこととで思いがけず良い順位を取ることができ、本戦に進出することができました。
当日
8:30ごろに会場着。10分位かけて交通費精算を終え自分の席に着くと、朝ごはんが用意されていました。
あさごはん! #code_festival pic.twitter.com/TUf2Y3s0LG
— 何もわからん (@lgeuwce) 2018年11月16日
机の上にはチームリレーのルールの紙やらWi-Fiの設定の紙やら色々なものが置いてあり、どれが重要なんだ…と手間取っていたら開会式が始まる。OPムービーに自分のTwitterIDが映ったときは胸熱でした。
机を整理してPCを準備していると「コンテストページにアクセスできましたか?」とアナウンス。待ってまだブラウザひらけてない!
そんなこんなで本戦まであっという間に時間が過ぎました。
本戦
配点は300-300-300-500-600-600-700-900-1000-1200、制限時間は3時間で、1400点以上取るとでパーカーがもらえるようです。ABCDの4完が目標ですね。
開始後、まずはAに取り掛かります。が、なかなか解けない……
自分がWAを出して焦っている中で周りが「カタカタカタカタカタカタカタカタカタ!!!!!!!!!!!!!」とさくさく解き進めていたので地獄を感じました。
その後結局3回提出してもACできなかったので、一旦諦めて次に進むことにしました。
BとCは問題なく解けて、Dを見ましたが全く開放の見当がつかないのでEを見ました。問題を眺めていると後ろからしゃくとり法みたいなことをすれば良いと気づきました。この時点では1時間以上残っていたはずです。しかし、「区間の最小値を求めるのってどうやるんだっけ…」とか本質的でないことをしばらく考えて時間を浪費し、結局セグ木をググりながら実装してバグらせていたらタイムアップになりました。
最終的に2完600点で94位でした。かなしい。後で気づいたのですが、Aは問題を誤読していました。
パーカー欲しかったです。
本戦後
昼食は3種類くらいのお弁当から1つ選んで自分の席に持っていく感じでした。
自分が取りに行ったときに残り1個になっている弁当があったのでそれを選びました。
おひる #code_festival pic.twitter.com/0StaEONe0f
— 何もわからん (@lgeuwce) 2018年11月17日
あさりご飯がすごく美味しかったです。冷たいご飯なのに美味しい謎の技術でした。
表彰では「すごいひとはすごいんだなあ」と思いました。
A.I. Challenge
表彰の後、同じ大学の先輩であるreminさんに声をかけましたが、もふふといった感じでしたので一旦別れて会場を彷徨っていました。
しばらくの間ふらふらと漂う人になっていましたが、14:00にセッションエリアでA.I. Challengeが始まるのでそちらに着地しました。
A.I. ChallengeはゲームAIのプログラミングコンテストで、ゲームはいつぞやに流行った「2048」を対戦型にしたものでした。こどふぇす開催までの1週間ほどの期間に作品が募集されており、自分は(こどふぇす本戦参加者の中で)予選5位になっていたので決勝トーナメントに進めました。
自分のAIのアルゴリズムは、
- アルファベータ法(モンテカルロ法は信用できなかったので)
- 評価関数はググって出てきたものをそのまま使用(調整する時間がありませんでした)
- 評価関数は「メインフェーズ終了後(アタックフェーズの前)」のタイミングで適用する(評価が正確になりそう・負けた判定がしやすそうなので)
- 基本的にアタックフェーズで1つしか置かない前提で探索する(そうでないと探索空間が爆発するので)
- 直近の自分の手のみ、2つで1つ以上のブロックを挟み込める場合(例えば、[0 4 16 0 0]という行を[2 4 16 2 0]にできる場合)を探索する
という感じでした。あまり変わったことはしていないですが、これで決勝トーナメントまで進むことができました。
実装している時間のうち体感8割がバグ修正でした。予選での対戦を眺めていると、自分のAIか相手のAIかに関わらず終了間際の動きが怪しいことが多く(まだ動かせるのに動かせない方向に動かそうとして負けるとか、ちゃんと動かせば大きい数字を消せて安全になるのにそうしないとか)、ここのバグをしっかりと直したことも良い結果に繋がったのかもしれません。
挟み込める場合の探索は作品受付の最終日に実装しましたが、これで予選でのレートが300くらい上がった気がします。
決勝トーナメントの結果は初戦敗退でした。相手が2個以上置きをばりばり使ってくるタイプだったので厳しかったです。
その後上位の対戦を眺めてAI作者の解説を聞いてはえ~となっていました。
決勝に参加したので世界に8個しかない物体を頂きました。スマホにつけて使うものらしいです。大事にします。もらった! #code_festival pic.twitter.com/GQP4akJR2D
— 何もわからん (@lgeuwce) 2018年11月17日
和エリア
同じ大学の先輩で黄コーダーであらせられるtossyさんにお声がけいただいて、早稲田生のたまり場に入れてもらいぼっちを回避しました。ありがとうございます。
reminさんがすやすや眠っていたのが印象的でした。
のんびりしながら「りんごの挑戦状」を見たりしていました。あれって本当に微塵も競プロ関係ないんですね。
Team Relay
1人1問までしか解いてはいけないチーム戦です。自分はGチームでした。
GチームにはA.I. Challengeの優勝者のさはらさんもいたのでテンションが上りました。
最初に作戦会議タイムがありましたが、自分はコミュ力不足により完全に挙動不審になっていました。
自分はA問題を担当し、1WAを生み出したり解き終わって戻って来たのを報告せずコーディングスペースに誰もいない時間を生み出したりとチームの足かせとして活躍しました。(本当にごめんなさい……)
自分の担当問題を終えて手持ち無沙汰になっていると、チームメンバーにI問題の説明をされたのでしばらく考えていました。
mod 5が3か4になるのをマージするしか得をする方法がないのと、3と4をマージするのが最も効率がいいので他との組み合わせを考えずこれを最優先に処理して良いのに気づいて、解答の方針が頭の中で定まったときにはもう残り15分くらいしかありませんでした。
チームメンバーの間では、残りの問題で解法が判っているもののうちいかに実装が楽そうなのを解くかという話になっており、新しい問題の解答の方針を共有する暇は無く、チームに貢献することはできませんでした。
最後の走者がコーディングスペースに向かい話し合うことも無くなったときに「I問題が解けた」とイキりながら話していましたが、あのときは筋道を立てた説明が全くできていなかった気がします。恥ずかしい。
sigmaさんが最後に10分もかからずF問題を実装していたのは完全にプロでした。
Gチームは最終的に6完でした。3位以内に入ったチームにはディナーの良い肉を贈呈されましたが、残念ながらGチームは良い肉にたどり着けませんでした。
チームリレーの後、さはらさんにA.I. Challengeのお話を聞くことができました。かなり幸福度が高かったです。
ディナータイム
良い肉は得られませんでしたが、寿司肉寿司寿司肉えび寿司ピザ肉という感じで最高でした。
寿司の無くなる早さを見誤ったのは失敗でした。
よるごはん! #code_festival pic.twitter.com/0YLVQm96YW
— 何もわからん (@lgeuwce) 2018年11月17日
閉会式
ダイジェスト映像が完成していてびっくりしました。自分は最後の方に0.2秒くらい映ってた気がします。
まとめ
楽しかったです。
参加前の時点では顔を合わせたことのある人が全く居ない状態でしたが、先輩に声をかけて頂き、同じ大学の競プロerと知り合うことができました。
あと、面白いことを言う人は面白いことを言うのが上手いなあと思いました。
帰宅
こどふぇすでもらったものたち #code_festival pic.twitter.com/H90oyIVjod
— 何もわからん (@lgeuwce) 2018年11月19日
Tシャツとかトートバッグとか色々もらえる上に3食ついてくるこどふぇす最高ですね。
M3-2018秋 参加記
理工展・早稲田祭を終え、世代交代・エモ・ムードの香る時期となりましたが、皆様いかがお過ごしでしょうか。(時候の挨拶)
7代DTM班長のLgeuです。
先月の28日、WCEは音系の同人即売会であるM3にて同人CDを頒布しました。
後輩への引き継ぎ資料も兼ねて、申込みから当日までの流れを参加記としてまとめておこうと思います。
【DTM班】
— WCE(早稲田コンピュータエンタテインメント) (@WCE_official) 2018年10月28日
設営完了しました!ス-22aでお待ちしております! pic.twitter.com/YsamjeXuz4
申込み
新歓が終わった5月~6月、この時期にCDのテーマを決めて参加申し込みをします。
テーマ決めはめちゃくちゃ重要です。CDの頒布枚数や制作のモチベーションに大きく関わります。
WCEでは、一昨年はゼルダのremix、去年はカービィのremixと作っており、(これらは結構需要が大きいという知見のもと、)今年もゲームアレンジでいこうという話になりました。(WCEの過去の資料によると「和風」などのテーマも需要があるようです。)
最終的に、DTM班の全員が知っているポケモンと、知らない人もいるが好きな人が多いUndertaleの2つの案が残り、
激闘の末Undertaleのremixに決定しました。英断だったと思います。
申込時にサークルカットが必要なので締切には注意が必要です。早めにテーマを決めて絵が描ける人にお願いしましょう。
申し込んでしばらくすると当落通知が来ます。
【DTM班】
— WCE(早稲田コンピュータエンタテインメント) (@WCE_official) 2018年7月29日
貴サークルのスペース配置を以下のように決定しました。
サークル名 早稲田コンピュータエンタテインメント
配置場所 第二展示場2階
スペース番号 ス-22a
M3-2018秋に当選しました!
「Undertale」楽曲アレンジCDの頒布を予定しています!
(サークルカット:NYLON) pic.twitter.com/zzFNn1SFeZ
曲を作る・曲を集める
曲が集まらないとCDはできません。がんばって曲をみんなに作ってもらいましょう。
夏休みが終わると忙しくなるので9/30を締め切りに設定しました。
少し早い感じもしますが、DTMerは締切りがないと行動できないので、早く動いてもらうためにこのくらいが丁度いいです。
また、収録曲は多いほど最高になるので、MIS.Wの皆さんからも曲を募集しました。
Undertaleというテーマにティンときてくれたようで、4人ものMIDI研民に協力して頂けました。ありがとうございます。
CDジャケットを作る
絵が描ける人に絵をお願いしましょう!
- 解像度は350dpiが目安(CDジャケットのサイズはおよそ120mm*120mmなので1650px*1650px程度は必要)
- トンボを付ける
- RGBじゃなくてCMYK
これらの項目には注意します。
CDジャケットを作るには、自力で印刷する方法と業者に発注する方法がありますが、業者に発注するほうがコスパが良さそうです。
自力で印刷するとインクの減りがすごいです。多くの業者は初回1000円引きとかやってるので活用すると結構安く出来上がります。
業者に発注する場合は、絵描きさんには入稿用テンプレートを渡しましょう。
【DTM】
— WCE(早稲田コンピュータエンタテインメント) (@WCE_official) 2018年10月22日
ジャケット無事入稿できました✨
参加して頂いた皆さん誠にありがとうございます。
詳しいM3情報はまた追って公開します。 pic.twitter.com/XUDbcJUWQm
CDを作る
曲が全て集まりマスタリングも終わったら、いよいよCDを焼きます。今回はiTunesを使って手焼きしました。
手焼きの場合、人為的ミスにより頒布物に空のCDが混入することがかなりの確率であります。最後に必ず確認しましょう。
また、盤面が白いと味気ないので、できれば何か印刷するか、何かを書きたいです。今回は8代NYLONが頑張ってくれました。
【DTM】
— WCE(早稲田コンピュータエンタテインメント) (@WCE_official) 2018年10月28日
tEMMIX!の盤面はNYLONが1枚1枚手描きしています! pic.twitter.com/YlZoOowpIK
CDとCDケースはこのあたりが無難だと思います。
CDが音楽用である必要は無いです。
Verbatim バーベイタム 音楽用 CD-R 80分 50枚 ホワイトプリンタブル 48倍速 MUR80FP50SV1
- 発売日: 2016/01/13
- メディア: Personal Computers
サンワサプライ 1枚収納×50枚セット スリムBD/DVD/CDケース クリア FCD-PU50C
- 発売日: 2013/10/01
- メディア: Personal Computers
それと、後で知ったのですが、どうやらCDDBというものに登録するといいようです。
当日に向けて
- 宣伝をしましょう。
明日のM3で頒布予定のコンピレーションアルバム「tEMMIX!」鋭意製作中です!
— WCE(早稲田コンピュータエンタテインメント) (@WCE_official) 2018年10月27日
当日は是非第二展示場 2階 ス-22aにて! pic.twitter.com/O0A4q6RWYZ
- クロスフェードを作りましょう。
クロスフェードを公開しました!
— WCE(早稲田コンピュータエンタテインメント) (@WCE_official) 2018年10月26日
Have you heard ‘【Undertale】M3-2018秋 新譜『tEMMIX!』XFD【WCE vs. MIS.W】’ by WCE_DTM on #SoundCloud? #np https://t.co/BGFwJpmDaq
- お品書きを作りましょう。(スペース番号は大きく入れましょう!)
遅くなって大変申し訳ありません!こちらM3のお品書きになります! pic.twitter.com/JE0Rv6O8HF
— WCE(早稲田コンピュータエンタテインメント) (@WCE_official) 2018年10月27日
当日
持ち物
サークルチケットと頒布物だけは忘れないようにしましょう。
当日あると良いものは、
- お品書き
- 試聴用のPC等とヘッドホン
- 小銭入れと小銭
- 布、値札、お品書きを掛けるやつ、頒布物を立てかけるやつ、筆記用具、スケッチブック
- 食糧と飲み物
このあたりです。
結構大荷物になるので、会場に向かいながら周りの人を見て「キャリーバッグいいなあ…」とか思いました。
入場
サークルチケットのおかげで長い列に並ぶことなく会場に入れます。
会場には自分、NYLON、9代のみずみくんの3人が行きました。自分が会場に着くとみずみくんがもう待っていました。早い。
会場で
設営を終えたら設営完了ツイートをします。11:00に開場したらあとは人が来るのを待つだけです。
売り子はみずみくんが頑張ってくれました(ありがとう)。
途中で慶應のサークルがご挨拶に来て、新譜を交換するイベントがあったりしました。
会場を散歩していると時々自分のと同じヘッドホン(AKG K240 MkII)があったりしてニコニコしたりしました。
閉場
15:30になったら閉場です。お疲れさまでした。
Undertaleというテーマもあり、知名度のないサークルとしてはそこそこの枚数を頒布することができたと思います。ありがとうございました。
追記(2018/11/22)
M3お疲れさま会をしました。
AtCoder青になるまでにやったこと
今日は競技プログラミングの話です。
先日のAtCoder Grand Contest 028で、(pythonで300点問題を早解きしたら)青coderになることができました。
この機会に、今までにやったことをまとめてみます。
ABC/ARC/AGCの400~600点問題を埋めた
5月くらいにAtCoderにハマり、ひたすら過去問を解いていた時期がありました(AtCoder ProblemsやAtCoder Scoresは便利ですね。)
過去問を埋めていると、同じ得点帯の問題を解くのに必要な知識や考え方が分かってきます。
400点くらいの問題を安定して(8~9割くらい)、あわよくば早く解ければ青になれるようです(なれました)
400点~600点の問題を解くために必要だった知識
・累積和、いもす法
・しゃくとり法
・modの世界での四則演算
・Union-Find木
・ダイクストラ法、ベルマンフォード法、ワーシャルフロイド法
・bisectを使った二分探索
・bit演算
・素因数分解のアルゴリズム
・素数列挙のアルゴリズム
・組み合わせの数nCrを計算するアルゴリズム
・高校数学(最小公倍数と最大公約数の性質、等差数列の和、重複を許す組み合わせの数など)
・各アルゴリズムの計算量
・pythonのあれやこれや
だいたいこんな感じだと思います。
コンテストに出て考えて何もわからず解説読んで知らないアルゴリズムが使われてると「は~~~~~~」ってなるので、とりあえず知識は身につけておきたいです。
pythonのあれやこれや
データ構造系
・set (集合型。C++でのstd::unordered_set)
・collections.deque (両側キュー)
・heapq (優先度付きキュー)
・collections.defaultdict (デフォルトの値を決められる辞書型)
便利系
・pow(a, b, m) (aのb乗をmで割った余りを求めてくれる)
・fractions.gcd() (最小公倍数を求めてくれる)
・itertools.product() (直積を求めてくれる)
・itertools.permutations() (順列を全列挙してくれる)
400点~600点の問題を解くのに必要だった考え方
・計算量を意識する(制限時間に間に合うようにするのはもちろんだけど,過度に高速にしようとしないのも重要)
・3つの点を求める問題は、真ん中を固定してみる
・複数の操作が行われる問題は、操作をゴールから逆順に考えてみる
・マンハッタン距離が出てくる問題は、座標を45度回転させてみる(x'=x+y, y'=x-y)
・絶対値の和を小さくする問題は、中央値が使えないか考えてみる
考え方の言語化はむずかしい…
黄色に向けて
700点問題がまあまあの確率で解けるようになれば黄色になれるらしいです。
700点問題になると解くのに必要な知識が増えてきます(動的計画法とかBinary Indexed Treeとか)。まだ過去問を全然埋められていないので、そこからやっていこうと思います。
また、700点問題になるとpythonの実行速度では辛くなることがあるようです。10^7回もループ回せないしもっと早くなるんだろうと考察してたのにそれが想定解で「は~~~~~~」ってなったりします。pythonは素早く書けるので難易度の低い問題には向いていますが、実行制限時間に間に合わなくてはどうにもなりません。しかたないのでちょっとずつC++も勉強していきます(つらい)