GoogleHashCode2020参加記

02/21の2:30~6:30に行われたGoogleHashCode2020予選にleaf1415、edamame88、nayutaの3人とチーム「lens1503」で参加しました。

当日まで

  • チーム名を決める。4人のニックネームの頭文字を並び替えたもの+ニックネームに含まれる数字の合計でlens1503になる。（名前を決めるのって難しくありませんか…？なんかの法則に従って決めようとしてしまう）。
  • AtCoderで日本橋ハーフマラソンがあったので参加する。B問題が貪欲をしっかり実装することで高得点になると知り、基本をしっかり考えることは大事だなあなどと思う。
  • JudgeSystemに公開されていた練習用問題を解いて、提出の方法やルールを知る。あったほうが便利だと思い、提出ファイルを自動生成するスクリプトを書くなどする。 問題は部分和問題そのもので、一瞬dpで解けるやんけ！となるが制約を見て察する(リンク先の例で1<=N<=105,1<=A<=109だった)。ここでビームサーチのような何か（解を少しずつ変えながらpqueに突っ込んで回す）と焼きなましを書く。初期解の質によって最終的なスコアが激変してなるほどなあとなる。頑張ったら理論値が出てうれしくなった。

当日

緊張して眠れなかった（小学生かな？）

糖分補給用に飴を持って大学に行く。一人一台ディスプレイがあり感動した。メンバーの方と合流後なんだかんだで開始まで2時間くらい時間が空いたので、三人+大学に残っていた方たちの前で書いてきたプログラムの解説をすることになる。無事テンパってしまい早口オタクになった（説明がうまくなりたい…）。その後ファイルの共有とかルールの確認とかしていると2:30になる。

問題が見れるのが15分後ということに気づかず「こどふぉった？」みたいな会話をする（ルールを確認したとはいったい…）
15分後

問題を見て、正の点数を得る方法を考える。とりあえず図書館を先頭から見ていって未コピーの本をコピーするコードを書いてAC。誤読してないようでほっとする。
サインアップする図書館の順番を固定すると、その状態での最適なスコアが求まると感じ、本の順番を受け取って最終スコアを計算するコードを書く…が、この処理が最悪でO(LB)ほどかかり（多分）、ほとんどのテストケースで破滅してしまった。状態をpqueにpushしつつ探索するコードを書いたのだが、6秒間かけてpqueの更新が8回くらいしか起きず変な笑いが出る。
残り1時間でスコアは2200万くらいだったと思う。このあたりでりーふさんから「図書館の順番を蔵書のスコア/手続き日数で降順ソートすると伸びそう」といったことを教えてもらう（うろ覚えです…）。その後いろんな基準でソートすると、何かの基準でFのテストケースだけ100万近く伸びた。この時点で貪欲ガチャをすることを決意し、残りの時間でひたすらいろんな基準を試しつつ伸びたものを提出していた。残り時間3分ほどになってえだまめさんがスコアを更新し、最終的に2600万台に乗ることができた。
感想戦でそれぞれのテストケースがランダム生成でないことを知り、無限チームがそれに気づいていたことにつらくなる。

感想

  • 事前に準備をしていて、当日に使いそうな関数やスクリプトを用意できていたので、落ち着いて取り組めた（当社比）と思う。
  • 途中から方針を転換できたのがよかった。ガチャを回さず高速化を頑張っていたら多分冷えていた。
  • テストケースの偏りに気づけなかったのは悔しい。テストケース名がおしゃれだなあとか思いつつ、どうせ中身はランダム生成だろ！という思いがあった。
  • 気づいた/考えたことを共有するのは大事だなあと思った。コンテスト後Twitterを見てるとスプレッドシート使って書き込んでいるチームがいて、とてもよさそうと感じた。

初めてのチームで行うマラソンコンテストだったので緊張しましたが、みんなで集まって問題に取り組むことができてとても楽しかったです。深夜にも拘わらず一緒に参加してくれたりーふさん、えだまめさん、なゆたさん、本当にありがとうございました！

ハル研コン2019の参加記

10/1~10/15に行われたハル研究所プログラミングコンテストに参加しました。
二次元グリッド上にいる複数のカメを操作して同じ盤面にあるエサを食べ尽くす速さを競う問題で、最終的に57,473ターンで18位となりました！

(30位までの人は参加賞としてモバイルバッテリーがもらえます)

問題概要

ハル研究所 プログラミングコンテスト2019 | 問題
ざっくり書くと、

  • 60*30の盤面に複数のカメとエサがある
  • 各ターンごとに各カメは上下左右に移動できる
  • エサにはそれぞれ「高さ」という数値が指定されていて、エサのあるマスにその高さ以上のカメが集まると、食べることができる
  • カメをうまく操作して、すべてのエサを食べるのにかかるターンを最小化せよ

という問題です。240個の異なる盤面に対する、エサを食べ尽くすのにかかったターンの合計でスコアが計算されます。

方針

（当然ですが）すべてのカメの動き方を一つひとつ探索していては時間が足りません。
「最終的に食べられるエサの順番」を決め打ちすると、その順番を守りつつ効率よく食べる操作列が作れそうだと考えました（例えば現在食べようとしているエサに対して、そのエサに近いカメから順に向かわせるなど）。
なので、基本的な方針として「エサの位置に2-optを使って移動経路が少なそうなエサの食べ方を求める」→「実際に掛かるターンを評価する」→「{ターン,順番}のペアをpriority_queueに入れる」→「queueから上位3つまでを取り出して順番を乱択で変える」→「再び評価してqueueに追加する」…というループを回すことにしました。
乱択をする際には（順番的に遠いものを入れ替えても改善する可能性が低いと考えて）、あるエサと、そのrandom(13)+1個隣のエサを入れ替えるようにしました。
また、「あるエサを食べて次のエサを食べに行く際、途中で別のエサを食べることができる」という場合があります。 f:id:sbite:20191015223855p:plain
なので、予め「エサa→エサbという順番で食べるとき、ついでに食べることができるエサ」をすべてのa,bに対して求めておいて、なるべく無駄がない食べ方をさせるようにしました。

やっていたこと

メモを取った

コンテスト開始からしばらくの間は、「自分が何をして、その結果どの程度改善したのか」のメモを取るようにしていました。
f:id:sbite:20191015225034j:plain
個人的にこれがすごい良くて、行き詰まったときに見返して改善が大きかったところを詰めたり、高速化する意味のなさそうなところを判断する指針になりました。
あと、日に日に書き込まれていくため、単純にモチベがとても上がります！

（ある程度）ちゃんとした変数名をつけた

今回のコンテストでは、ステージの生成部やシミュレーション部などのソースコードがはじめから公開されています。
普段僕はとても適当な変数名をつけがちなのですが、そのコードに習って、ある程度しっかりした変数名をつけるようにしました。
その結果、ある程度時間が立ってからコードを読んでも、どういう処理をやっているかが格段にわかりやすくなりました。
（ただ、終盤になってくると変数名と実態が一致しないみたいなことも起こって辛くなりました（は？））

感想

ハル研究所のプロコンには去年も参加していたのですが、その時は何一つ改善できないまま終わってしまったので、今回入賞できてとても嬉しいです。
問題もとてもわかりやすく、付属のソースコードやビューアもしっかりしていて、二週間夢中で取り組むことができました。
来年も参加したいです！

ctf4b2019writeup

ctf4b2019に二人チームで参加しました。これが始めてのCTFだったのですが、最終的に6問を解くことができてとても嬉しかったです。

以下、僕が解いた問題を書きます。

 

[warmup] Welcome

IRCで freenode.netの#seccon-beginners-ctfに接続するとflagが表示されます。クライアントの使い方がわからず少し苦労しました。

[warmup] Seccompare

https://score.beginners.seccon.jp/files/seccompare_44d43f6a4d247e65c712d7379157d6a9.tar.gz にある実行ファイルを解析してflagを得る問題です。適当なバイナリエディタを使って中を見ると、ctf4b{...}みたいな文字列が見えたのでこれを提出しました。

katsudon

問題文中にflagがおいてあるURLが書かれていました(https://katsudon.quals.beginners.seccon.jp/flag)。そこにアクセスすると

BAhJIiVjdGY0YntLMzNQX1kwVVJfNTNDUjM3X0szWV9CNDUzfQY6BkVU--0def7fcd357f759fe8da819edd081a3a73b6052a

という文字列が表示されたので、--までの文字がbase64っぽいと思い base64 -dをしました。するとflagらしきものが現れました。（よくわかっていない） 

 containers

https://score.beginners.seccon.jp/files/e35860e49ca3fa367e456207ebc9ff2f_containersl

からflagを得る問題です。このファイルを開くと、大量の文字化け文字とともに"FILExx.png"のような文字列が一定の間隔で書かれていました。あるFILExx.pngと次のFILExx.pngの間にあるデータをpngにしてやると、flag中の1文字が出てきます。pythonでこれを全てのFILExx.pngに対して行いました。

 Sliding puzzle

nc 133.242.50.201 24912でサーバに接続すると、8パズルが複数与えられます。これを解くプログラムを作る問題です。

最初は愚直にBFS+同一局面を枝刈りで書いたのですが、問題によってはいつまで経っても探索が終わりませんでした。そこで、「最終局面にどれだけ近いか」をスコアとして、priority_queueで盤面を管理するようにしたところ、十分な速度となりました。

また、解答の際、最初はプログラムの出力を見ながら手打ち入力をしていたのですが、サーバとの通信には時間制限があるらしく、何回やっても失敗してしまいました。

そこで、サーバと作ったソルバで直接やり取りをさせるスクリプトを書き、ようやくflagをもらうことができました。（問題とその解答がガーっとターミナルに表示されるのには興奮しましたw）

終わりに 

 こうして振り返ると、（当たり前ですが）自明な問題しか解けなかった感があります。また、Web,Pwnのwarmupを取ることができなかったのは悔しいです。

とはいえ、全体としてはとても楽しかったです。特に、Sliding puzzleのflagが手に入ったときは表現できないくらいの喜びを感じました。

今後もまたコンテストがあれば参加したいなあと思っています。

 

日経コン（のイベント・懇親会）に参加しました

 

2/17に東京ドームホテルで開催された、全国統一プログラミング王決定戦（日経コン）のイベントと懇親会に行ってきました。
競プロ関連のイベントに参加するのも東京へ旅行に行くのも初めてだったので緊張していましたが、とても楽しかったです。

 

当日より前
日経コン予選でギリギリ500位以内に入ることができました。

(スクショでは487位になってますが、最終的に488位になりました)

イベントへの招待メールが届いたとき、すごく嬉しかったことを覚えています。知り合いがいなかったので不安でしたが、弊学erの方が二人参加予定と知り、懇親会でエンカすることになりました。どちらも実際にお会いしたことはなかったので、当日まで結構ドキドキしていました。

 

当日
電車&新幹線に乗って東京へ向かいます。移動中に本戦の問題が公開されたので、ざっと眺めつつ解けそうな問題がないか探していました。Cが全くわからなくて「は？？？300？？？？は？？？？？？？」となったのを覚えています。

東京につきました。

日曜日と言うこともあり人は思っていたより少なかったです。駅の構造が複雑過ぎて一瞬迷いかけたので、駅員さんに道を聞きつつ目的のホームまで行きました（ありがとうございます）。

その後も順調に乗り換えて、無事に会場の最寄り駅につきました。

会場に到着しました。開始時刻まで1時間ほどあったので、周辺で時間を潰すことにしました。twitterをみると懇親会勢が続々と集まっていることが分かり、自分がコミュ症であることを思い出します。テンパってしまって、TLに到着報告が流れるたびにあたりを見回す異常者になってました。

その後辺りを散歩して、少し落ち着いたのでホテルの中へ行ってみました。想像していた10^9+7倍豪華でひょえーってなります。ここで-jさんとエンカしました。エンカ自体が初めてだったので緊張しまくったことを覚えています。（テンパって「あの、スマホ、写真撮りましょう！（早口）」みたいな明らかに伝わらない感じで話してしまって本当に申し訳ない…）。その後近くにいた競プロerの集団に合流しました。強プロerの方がたくさんいて、改めて「競プロのイベントに来たんだなあ」という実感がわきました。

会場が開場（激ウマギャグ）したので中に入ります。本戦がまだコンテスト中だったようで、会場に人はあまりいませんでした。スクリーンに写っていた注意書きが読めず†本戦参加者用の椅子に座る†をしました。本当にごめんなさい…（すぐに別の席へ行きました）。しばらくすると人がどっとやってきて、あっという間に席が埋まりました。

パネルディスカッションが始まりました。iwiさんが「我々が作っているchainerなんですけど…」みたいに話すのを聞いてひたすらすげえってなってました。また、chokudaiさんやPFNのCEOの方など、半年前には生で会えるとは夢にも思わなかったすごい方々が話しているのをみて、改めて参加できてとても良かったと感じました。あと、chokudaiさんの会場の盛り上げ方がとても上手かったです。

パネルディスカッションの後、表彰式が始まりました。普段順位表の1ページ目でしか見たことのない方が次々と登壇するのにひたすら圧倒されていました。アナウンサーの方がAtCoderIDを読み上げている状況にテンションが上がっていました（謎）。

表彰式の後に上位３名の方によるエキシビションマッチがありました。200~500までの8問を20分で通す人外コンテストだったのですが、1位のsemiexpさんが15分で全完していました。３人とも問題を見てからコーディングに入るスピードがすごい早かったです。
chokudaiさんの実況がひたすら面白く、一つ一つの問題にもネタが詰まっていて、20分すぎるのがあっという間でした。

エキシビション後、隣の会場へ移動し、ご飯＆懇親会になりました。乾杯の音頭があるまで、-jさん、toameさんとお話していました。これまで競プロの話題で盛り上がるという経験がなかったので、ひたすら楽しかったことを覚えています。
乾杯後、弊学erのedamame88さん、leaf1415さんとエンカします。普段いる場所から500キロ近く離れた場所で、同じ大学の人と初めて合うという経験に謎に感動していました。
けんちょんさんと握手してもらいました。普段解説記事にお世話になりまくっているので、実際にお会い出来てめっちゃ嬉しかったです。
keymoonさんともお会いできました。こちらも普段Predictorを利用しまくっているので、お会いできてとっても嬉しかったです。
貪欲さんにもお会いできました。少し前に「ご飯の列に並んでいる」みたいなことをツイートしていたんですが、しっかり補足されていてびっくりしました。

ご飯もとっても美味しかったです。なんか肉をいい感じに焼いたやつがあって、それが特に美味しかったです（語彙力がない）。「これが…東京の肉…！」って一人で感動していました。

懇親会は7:15までだったんですが、帰りの電車が混みそうだと思い、15分位前に帰りました。もうちょっといればよかった…。

以上、当日の感想でした。すべてが楽しくて、参加できてすごく良かったです。また、記事ではあんまり触れてませんが、想像以上に僕の社会性がなくて、異常なムーブを何回もしていた気がします。迷惑に思われた方がいたらごめんなさい…。今回は懇親会だけの参加でしたが、もっと強くなって（社会性も身につけて）オンサイトに行きたいなあという気持ちがとても強くなりました。エンカしてくれた方々、AtCoder・日経新聞社はじめ企業の方々、本当にありがとうございました！