FORCIA Summer Internship 2021 に参加しました
フォルシア株式会社にて5日間のサマーインターンに参加してきました。
なるべく応募段階から全体の流れが分かるように書くので、これからインターンに参加する人の参考になれば幸いです。
自分について
こんな感じでかなり競プロに頼って就活してます。
参加までの流れ
フォルシアさんでは過去に「ゆるふわ競技プログラミングオンサイト」というイベントを開催されていたり、競プロ関係で知っている方が何人もインターンに参加したり入社されているのを見て、かなり興味を持っていました。
応募コースはデータクレンジングサービス開発コースにしました。アルバイトや研究でも業務の一部でデータ整形をよくやっているのと、要求されるスキルがPython & pandasでどちらも慣れていたという理由で選びました。5日間では不慣れな技術にキャッチアップしている時間はないのではと想像して、スキル的にいけそうかどうかは結構重視しました。その点を度外視すると、最近Elasticsearchに触れて検索エンジンに興味が湧いてきたので検索アプリ開発コースも面白そうだなと思いました。
選考はESと面接1回でした。面接について特に変わったところはなく標準的な内容でしたが、こちらの話に対して基本的に肯定的なリアクションを取ってもらえたのでとても安心して話しやすかったのが印象的でした。
課題内容
Massteryというデータ整備を自動化するサービスがあります。基本的にはデータをアップロードするだけで自動的に整備されるのですが、事前にデータ変換の設定を人手で行わなければならない場合もあり、大変なのでこの作業を補助するツールを作ってください。
という内容でした。
もう少し詳しく書くと、変換前後のExcelファイルが2つあって、どういうルールで変換されているか(例えば「変換前のA列とB列を結合して変換後のE列を作っている」「変換前のC列の値をそのまま変換後のB列にマッピングしている」など)を読みといてそれを再現できるような変換条件を設定する作業の補助 というテーマでした。
インターン
1日目は課題内容の説明を受けてどういうツールを作るか考えたり、いくつか思いついた中で実装が軽そうな方法を書いて試したりしていました。 初日はとりあえず環境構築をするイメージだったのですがそこはあらかじめ準備されていて感動しました。 お昼ご飯はすき焼き弁当でした。めちゃめちゃおいしかったです(スマホのカメラが壊れてたので写真はないです)。
2日目は、実際に変換設定作業を行っている社員さんにヒアリングを行い、要件定義を行いました。僕の思い付きで良さそうな機能を実装しても、使う方からすると「ｺﾚｼﾞｬﾅｲ…」となりかねないので実装に取り掛かる前にこの工程を踏むのはとても重要だったと思います。後で営業担当の方から聞いた話によると、こんな感じでエンジニアであってもクライアントとの折衝など上流工程に関わるのはフォルシアさんの特徴的な部分でもあるらしいです。
結局、変換前後の列と列の関係性を可視化するという方向ですすめることになり、変換規則のパターンが色々あるので、それらをカバーできるような方法を時間の許す限りいろいろ(文字列の類似度とか統計的な相関とか)実装することにしました。
3日目は中間発表としてこれまでの進捗と今後の方針を話しました。何も準備せずに臨んだらかなりテンパって話の流れとかゴチャゴチャになってしまったので猛反省しました。
その後はモリモリ実装を進めましたが、事前の調査ではうまくいくだろうと思った方法がいざ実装してみたら微妙な結果になって半日無駄にしたかと思い焦りました。
4日目の朝に、昨日ダメだった理由が単純なバグだったことに気づいて事なきを得ました。 この時点で大体良い感じに動くようになったので、コードレビューを頂きつつリファクタリングを進めました。
5日目は最終発表がありました。中間発表の反省もあり今度は気合を入れてスライドを準備して臨みました。学部4年で研究室に配属されてからスライドを作る機会がかなり増えましたがいまだに苦労しますね(気を抜くとすぐに一面真っ黒の箇条書きみたいになってしまう)。同期の2人は自然言語処理コースと検索アプリケーション高速化コースでどちらも性能改善的な内容だったので発表難しそうだなと思いきや門外漢の自分にも分かりやすく発表していてすごいと思いました。発表後は社員の方々からフィードバックコメントをいただきました。全体的に良い感じのことが書かれていてうれしかったです。
その他
環境
まず立地が最強で、フリードリンクも充実していて良かったです。冷凍庫にはピノがたくさん入っていました。 昼食は毎日高そうなお弁当が支給されて各自で食べる形式でした。 キーボードとマウスは持参しました。 コミュニケーションに関してはSlackが中心で、関係ないことを書いても許される雰囲気で発言しやすかったです。あとは社員の方が時々席に様子を見に来てくれました。
座談会
コロナの影響で昼食が個食スタイルになった代わりに、昼食後に毎日様々なポジションの社員さんと話す場を設けてもらいました。日によって話す内容が完全にバラバラで、雑談だったり就活のアドバイスを貰ったり競プロの話をしたりで楽しかったです。
夕会
一日の終わりにインターン生やインターンに関わる社員さんが集まってその日の作業報告をする会がありました。個人的に他のインターン生のやっていることが気になっていたのでこの時間は楽しみにしていました。
感想
課題内容に関しては、5日間でやるには割とハードな課題で若干やり残した感もありますが、事前にどの機能を実装するかの優先順位を付けて取り組んだのは業務っぽくて良かったと思います。 入社手続きから各種イベントに共通して段取りがきちんとされていて、相当リソースを割いて準備してくださったんだろうなと思いました。そのおかげで5日間とは思えないほど充実感がありました。
本当に参加してよかったと思いました。受け入れてくださったフォルシアさん、ありがとうございました。
8月振り返り
よかったこと
夏インターン
- 8/16 - 8/20 フォルシア株式会社
- 8/23 - 10/1 LINE株式会社
のインターンに参加しました(しています)。 どちらもとても楽しくて満足しています。これはまた別に参加記を書きたいと思います。
アプリコンテスト
学科同期と3人で出ようぜとなって
に申し込みました。 アプリ開発経験0なのでFlutterを必死に勉強しながら足を引っ張りまくっています。新鮮で楽しいです。
24時間営業のジムに入会した
大学のトレーニング室は夜20時に閉まってしまいインターン中は行けないことに気づいたのでエニタイムフィットネスに入会しました。 深夜にも運動できるので良いです。
よくなかったこと
生活リズムが不安定
インターンのため平日は朝起きているのですが、土日に入った瞬間昼まで爆睡してそのまま夜更かししてしまい月曜の朝地獄をみるやつを毎週繰り返しています。HELP!
服がない
人と会うことがなくなってTシャツしか持っていなかったのでインターン中着る服に困りました。 毎日退勤後に次の日着る服を買って帰っていて「洗濯という概念を知らない人」になってました。
研究
今月は全然進捗を埋めませんでした。先週学会発表があってその準備をしてたくらいです。 インターン終わったら本気出す
その他
コンテンツ紹介
ynjn.jp ゴールデンカムイを全部読みました。おすすめです。9/17まで全話無料公開されてます。
【original】イミグレーションfeat.Yunomi【周防パトラ / ハニスト】
youtu.be
Yunomiさんもパトラさんも好きなので最高のコラボでした。
6 ~ 7月振り返り
どらめもリスペクトでときどき振り返り記事を書くことにします．
研究
5月から新しく始めたテーマで昨日論文を一本提出しました．句読点がこれになってるのは，それです． 実験も何もしていない状態で申し込むことになってスケジュール的にかなりしんどかったです．その結果単位がいくつか犠牲になりました．
就活
サマーインターンに何社か申し込んで3社受かりました．そのうち2社(1社はAtCoderJobs経由)に参加してきます． いくつか選考を受けた印象としては，
意外と書類で落ちた
学歴で行けるでしょと思ってへらへらしてたら思いのほか書類で落とされてびっくりしました．ESは人に見てもらって真面目に書いた方が良かったなと反省してます．
意外と競プロが評価された
2年前にサマーインターンに申し込んだときは競プロの話をしても興味を示してもらえないことが多い印象でしたが，今回面接を受けたところはほとんど好意的な反応が返ってきて，競プロが社会に浸透してきていることの表れなのかなと思いました．
あと，これは予想通りではありましたが実務経験が重要視されているのを感じました．2年前のインターンも現在アルバイトしているところもAtCoderJobs経由だったので，AtCoderがなければ僕は今頃ニートだったと思います．
その他
買ってよかったもの
オンライン授業やZoomミーティングで長時間イヤホンを付けることが多いので買いました．骨伝導だと耳が蒸れないのと疲れにくくて良いです．運動中にも使ってます．
4Kモニターが欲しくなったので買いました．画面に表示される情報量が増えて良かったです．
値段の割に高機能で良いと思います．寝落ちすることが多いので，いつからいつまで寝てたのか後から分かるのが助かります．
TA
学部3年生向けの講義「アルゴリズム」のTAをしました．来年のTAを熱烈募集しています．
アニメ
- 86
- 東京リベンジャーズ
- 不滅のあなたへ が面白かったです．Vivyは途中まで見ました．そのうち続き見ます．
Among Us
研究が燃えていたのでしばらく封印していましたが再開しようと思います．一緒にやる人を常に募集しています．
筋トレ
去年の9月から大学内のトレーニングルームでマシンだけ触っていましたが，最近フリーウェイトを始めました． 僕はどちらかというとやせ型なので体重を増やしたくて食事管理アプリ「あすけん」を入れたところ毎日3000kcal食べなさいと言われて絶望しました．
リアルフォースにコーヒー牛乳をこぼした
分解清掃したら一命をとりとめました．
オリンピック
TOEIC対策でやったこと
3年前にTOEICを受けたときの記事で「対策法を書きたい」とか言って放置していたら2年前から待っているという方のコメントを頂いたので、当時勉強したことをなんとか思い出して書きたいと思います。
前提
英語は大学受験の時点でそこそこ得意でTOEICのための勉強量自体はそこまで多くなかったと思います。具体的には、
前提
英語は大学受験の時点でそこそこ得意でTOEICのための勉強量自体はそこまで多くなかったと思います。具体的には、
- 英検準一級
- センター194/200
- 東大二次90/120
くらいからのスタートでした。入学してから1年経っていたとはいえ、単語や文
法はギリギリ頭に残っていたような気がします。
スコアの推移は、試験1ヶ月前に模試を解いて大体800~850くらい？(よく覚えてないのでかなり不正確です)で本番965でした。
やったこと
法はギリギリ頭に残っていたような気がします。
スコアの推移は、試験1ヶ月前に模試を解いて大体800~850くらい？(よく覚えてないのでかなり不正確です)で本番965でした。
やったこと
- 本番形式の問題集を解く
- 知らなかった単語を拾う(リーディング)
- 間違えた問題の音声トラックをスマホに入れて暇なときに聴く(リスニング)
の繰り返しでした。TOEIC用の単語帳やパート別の問題集はやりませんでした。
本番形式の問題集はたぶん公式問題集が一番良いと思いますが、当時はお金がなかったのでBOOK-OFFで旧形式の模試問題集を適当に3~4冊くらい買ってやりました。
2.について補足すると、問題を解くときに分からない単語を水色の蛍光ペンでマークしておいて、解き終わったら採点ついでにスマホの単語帳に追加する、という方法を取っていました。
「シンプル単語帳」ってアプリです。まだスマホにデータが残っていたので貼っておきます。(ちなみにこれを大学の友人に見せたら「お前それでよく東大受かったな(笑)」と言われました。)
大学3~4年でほとんど英語を使う機会がなく(最後の最後に卒論を英語で書いたくらい)、相当退化してしまっているので、そのうち勉強しなおしてまた受けようかなと思ってます。
本番形式の問題集はたぶん公式問題集が一番良いと思いますが、当時はお金がなかったのでBOOK-OFFで旧形式の模試問題集を適当に3~4冊くらい買ってやりました。
2.について補足すると、問題を解くときに分からない単語を水色の蛍光ペンでマークしておいて、解き終わったら採点ついでにスマホの単語帳に追加する、という方法を取っていました。
「シンプル単語帳」ってアプリです。まだスマホにデータが残っていたので貼っておきます。(ちなみにこれを大学の友人に見せたら「お前それでよく東大受かったな(笑)」と言われました。)
大学3~4年でほとんど英語を使う機会がなく(最後の最後に卒論を英語で書いたくらい)、相当退化してしまっているので、そのうち勉強しなおしてまた受けようかなと思ってます。
ICPC2020国内予選 参加記
こんにちは，モジャンボです．
sim(simkaren)，モジャンボ(Mojumbo)，じゅっぴー(juppy)の3人でチームSiMoJappyとしてICPCの国内予選に参加しました．去年結成したチームで，ICPCへの参加は2回目になります．
模擬国内がうまくいって12位だったので，あわよくばアジア地区大会(´イωク｀)ε-(/･ω･)/三┏( ^o^)┛٩(・ω・)วlet's go!という意気込みだったのですが，結果は38位で予選通過ならずでした．残念…
コンテスト前
開始30分前にZoomに集合．コミュニケーションはZoomとSlackで行った．
ここしばらくは
A:じゅっぴー
B:sim
C:モジャンボ
の分担で固定していたが，前日の通話で2人が構文解析に自信なしということが分かったため，もしDかEに構文解析が出たらCはじゅっぴーに押し付けて自分が構文解析をやることにしようと提案した(そしてほんとにDで出た)．
コンテスト
コンテストページにつながらない．そのうちアナウンスがあるでしょと思ってダラダラしゃべってたらヌルっと始まる．
D問題が構文解析なので打ち合わせ通りこの問題に取り掛かることに．Dの構文解析なんて実装するだけだろうと高をくくっていたが，普通に構文解析以外のパートが難しくない…？
苦しんでいる間にじゅっぴーとsimがABを通してC問題を相談しているのを何となく聞きながらDを考える．でも本当に何も分からない．(20分)
じゅっぴーが約数を全列挙して約数のペアを全探索でどうかというのが聞こえてきた．怪しいけどICPC的にはよさそう．
simが3つの約数のうち1番小さいもの(O(N^(1/3)))を全探索でどうかというのが聞こえてきて，それなら実装軽そうだし俺書きます！と言ってDから逃げる．
1番小さい約数は全探索するとして，残り2つは…？うーん，全探索！ｗをしたら実行があまりにも遅い(当然)ので適当に枝刈りを入れたら今度は1分くらいで実行できた．これがICPCなんですね．(40分)
Cを提出して帰宅すると，simがDよりもEの方が希望があると言うので相談しながら解法を生やす．
sim「奇数行と偶数行は独立に考えられて～」
モジャンボ「ｽﾞｻﾞｻﾞｧｧｯ≡______(┐「ε:)_それな」
sim「偶数行だけを抜き出すと，対角に並んだマスを同時に取れないから二部グラフの独立集合の数え上げみたいな」
モジャンボ「☜╮(´ิ∀´ิ☜╮)ﾔﾙﾈ-」
なんやかんやでbitDPができる制約まで落とせることが分かったので，実装する．スルスル考察が進んで気持ちよかった．参加記もこの部分だけ書きたかった．
とりあえず雑に2^15通りの状態から2^15通りへの状態への遷移を書いてDPすると実行が終わらないので，遷移先をDFSで列挙する(これで4^15から3^15に落ちたような気がする)と無事AC．(2:00)
帰宅すると，Dはやっぱり分からなくてFはできるかもみたいな状況らしいので，2人にはFをやってもらって自分はDを考え直すことに．
自分は1時間椅子を温めて，Fもバグが取れない？っぽくて4完で終了．さよなら…
感想
反省すべき点は多分立ち回りにはなくて，単純に個人としての力不足を痛感した．
特に構文解析は自分の担当なのに大量に通されているDが通せなかったのは猛反省．
来年の国内予選までにはAtcoder橙になっておきたい．
sim(simkaren)，モジャンボ(Mojumbo)，じゅっぴー(juppy)の3人でチームSiMoJappyとしてICPCの国内予選に参加しました．去年結成したチームで，ICPCへの参加は2回目になります．
模擬国内がうまくいって12位だったので，あわよくばアジア地区大会(´イωク｀)ε-(/･ω･)/三┏( ^o^)┛٩(・ω・)วlet's go!という意気込みだったのですが，結果は38位で予選通過ならずでした．残念…
コンテスト前
開始30分前にZoomに集合．コミュニケーションはZoomとSlackで行った．
ここしばらくは
A:じゅっぴー
B:sim
C:モジャンボ
の分担で固定していたが，前日の通話で2人が構文解析に自信なしということが分かったため，もしDかEに構文解析が出たらCはじゅっぴーに押し付けて自分が構文解析をやることにしようと提案した(そしてほんとにDで出た)．
コンテスト
コンテストページにつながらない．そのうちアナウンスがあるでしょと思ってダラダラしゃべってたらヌルっと始まる．
D問題が構文解析なので打ち合わせ通りこの問題に取り掛かることに．Dの構文解析なんて実装するだけだろうと高をくくっていたが，普通に構文解析以外のパートが難しくない…？
苦しんでいる間にじゅっぴーとsimがABを通してC問題を相談しているのを何となく聞きながらDを考える．でも本当に何も分からない．(20分)
じゅっぴーが約数を全列挙して約数のペアを全探索でどうかというのが聞こえてきた．怪しいけどICPC的にはよさそう．
simが3つの約数のうち1番小さいもの(O(N^(1/3)))を全探索でどうかというのが聞こえてきて，それなら実装軽そうだし俺書きます！と言ってDから逃げる．
1番小さい約数は全探索するとして，残り2つは…？うーん，全探索！ｗをしたら実行があまりにも遅い(当然)ので適当に枝刈りを入れたら今度は1分くらいで実行できた．これがICPCなんですね．(40分)
Cを提出して帰宅すると，simがDよりもEの方が希望があると言うので相談しながら解法を生やす．
sim「奇数行と偶数行は独立に考えられて～」
モジャンボ「ｽﾞｻﾞｻﾞｧｧｯ≡______(┐「ε:)_それな」
sim「偶数行だけを抜き出すと，対角に並んだマスを同時に取れないから二部グラフの独立集合の数え上げみたいな」
モジャンボ「☜╮(´ิ∀´ิ☜╮)ﾔﾙﾈ-」
なんやかんやでbitDPができる制約まで落とせることが分かったので，実装する．スルスル考察が進んで気持ちよかった．参加記もこの部分だけ書きたかった．
とりあえず雑に2^15通りの状態から2^15通りへの状態への遷移を書いてDPすると実行が終わらないので，遷移先をDFSで列挙する(これで4^15から3^15に落ちたような気がする)と無事AC．(2:00)
帰宅すると，Dはやっぱり分からなくてFはできるかもみたいな状況らしいので，2人にはFをやってもらって自分はDを考え直すことに．
自分は1時間椅子を温めて，Fもバグが取れない？っぽくて4完で終了．さよなら…
感想
反省すべき点は多分立ち回りにはなくて，単純に個人としての力不足を痛感した．
特に構文解析は自分の担当なのに大量に通されているDが通せなかったのは猛反省．
来年の国内予選までにはAtcoder橙になっておきたい．
第二回 アルゴリズム実技検定(PAST) 感想
第二回 アルゴリズム実技検定(PAST) をバーチャル参加で解きました。267分(+7ペナ)でなんとか全部解けました。
感想をTwitterに流そうかと思ったのですが量が多いのとまだ解いてない人のネタバレになってしまうのが怖いのでブログに書きます。
A - エレベーター
B→-1をかける
F→1を引く
みたいにパースしました
B - 多数決
a,b,cという変数を用意して出現回数を数えました
C - 山崩し
AOJ-ICPCにありそう
D - パターンマッチ
正規表現でかっこよく書きたい
E - 順列
言われたとおりにシミュレーションする
F - タスクの消化
その日に実行できるタスクの中で一番ポイントが大きいものを貪欲に選ぶ
priority_queueを使いました
G - ストリング・クエリ
言われたとおりに文字列Sを持つと大変なので {文字、個数} をdequeに入れた
H - 1-9 Grid
いつものダイクストラ
安心感が凄かった
I - トーナメント
N回戦までで終わるからシミュレーションして間に合う
J - 文字列解析
一番やらかしたし一番時間溶かした
パッと見区間dpにしか見えなくて
dp0[l][r]=[l,r)が正しい括弧列になるときの最小コスト
dp1[l][r]=[l,r)で'('が1個余るときの～
dp2[l][r]=[l,r)で')'が1個余るときの～
dp3[l][r]=[l,r)で')('が余るときの～
をやろうとしたら実装が重すぎて1時間溶かしたあともっと簡単なやり方に気づいた(これでもできるよね？)
M - 食堂
やることが分かっても実装がかなり辛いやつ
こういう問題練習すれば強くなるんだろうな～とは思うけどコンテスト以外で解くのはしんどい…
N - ビルの建設
これABCに出してほしい
クエリソートすると一次元セグ木でOK
O - 可変全域木
これも好き(でも既出なのかな)
とりあえず適当に最小全域木を作った後で辺(u,v)を使うことを考える。
u-vパスと辺(u,v)でループができるから、u-vパスの中で一番重みが大きい辺と辺(u,v)をswapすればいい
パスの中で一番重みが大きい辺を探すのはHL分解＋セグ木でできる(この問題HL分解のverifyに使えそう)
感想をTwitterに流そうかと思ったのですが量が多いのとまだ解いてない人のネタバレになってしまうのが怖いのでブログに書きます。
A - エレベーター
B→-1をかける
F→1を引く
みたいにパースしました
B - 多数決
a,b,cという変数を用意して出現回数を数えました
C - 山崩し
AOJ-ICPCにありそう
D - パターンマッチ
正規表現でかっこよく書きたい
E - 順列
言われたとおりにシミュレーションする
F - タスクの消化
その日に実行できるタスクの中で一番ポイントが大きいものを貪欲に選ぶ
priority_queueを使いました
G - ストリング・クエリ
言われたとおりに文字列Sを持つと大変なので {文字、個数} をdequeに入れた
H - 1-9 Grid
いつものダイクストラ
安心感が凄かった
I - トーナメント
N回戦までで終わるからシミュレーションして間に合う
J - 文字列解析
一番やらかしたし一番時間溶かした
パッと見区間dpにしか見えなくて
dp0[l][r]=[l,r)が正しい括弧列になるときの最小コスト
dp1[l][r]=[l,r)で'('が1個余るときの～
dp2[l][r]=[l,r)で')'が1個余るときの～
dp3[l][r]=[l,r)で')('が余るときの～
をやろうとしたら実装が重すぎて1時間溶かしたあともっと簡単なやり方に気づいた(これでもできるよね？)
M - 食堂
やることが分かっても実装がかなり辛いやつ
こういう問題練習すれば強くなるんだろうな～とは思うけどコンテスト以外で解くのはしんどい…
N - ビルの建設
これABCに出してほしい
クエリソートすると一次元セグ木でOK
O - 可変全域木
これも好き(でも既出なのかな)
とりあえず適当に最小全域木を作った後で辺(u,v)を使うことを考える。
u-vパスと辺(u,v)でループができるから、u-vパスの中で一番重みが大きい辺と辺(u,v)をswapすればいい
パスの中で一番重みが大きい辺を探すのはHL分解＋セグ木でできる(この問題HL分解のverifyに使えそう)
Google Hash Code 2020に参加しました
こんにちは、モジャンボです。
sim(simkaren)、モジャンボ(Mojumbo)、じゅっぴー(juppy)、ぴーよ(holeguma)の4人でチーム名SiMoJapPiyoとしてGoogle Hash Codeに初参戦しました。とても楽しく、貴重な体験ができたので参加記を残しておきます。
コンテスト前
19:30から22:30まで仮眠をとって、0:00ちょうどくらいに大学に行くとsimとjuppyが待っていました。ぴーよはその一時間後くらいに来ました。その日simはバイト、ぴーよはインターンがあったらしいです。お疲れ様です…
こんなに夜遅くに大学に集まるのはさすがに初めてだったのでテンションが上がりました。研究室に配属されると珍しくなくなるんですかね
集合が早く、コンテストが始まる2:30までかなり時間を持て余しました。僕はじゅっぴーが持ってきてくれたRealforceをしばいて、simはまちカドまぞくを観て、juppyはASMRを聴いて などして時間をつぶしていました。ぴーよが来た後はコンテスト開始後の流れや4人の役割分担を相談しました。
コンテスト
2:30コンテスト開始だと思っていましたが、2:45まで謎の待機時間がありました。
問題が公開されました。まずは全員で問題文を読んで、誤読を防ぐために問題内容を共有しました。
問題の概要はこんな感じです
\(B\)種類の本(それぞれ価値\(S_{i}\))と\(L\)個の図書館があり、期間は全体で\(D\)日間です。
各図書館\(j\)には、蔵書の集合(冊数\(N_j\)と本のIDの列)と、サインアップにかかる日数(\(D_j\))と、その図書館の本を1日に最大何冊までスキャンできるか(\(M_j\))のパラメータが定められています。
図書館は一度サインアップされた後、毎日\(M_j\)冊まで本を選んでスキャンします。(スキャンは並列に行えるがサインアップできる図書館は常に1つまで)。
サインアップする図書館とその順番、またスキャンする本をうまく選んで、スキャンされた本の価値の総和を最大化してください(ただし同じIDの本を複数回スキャンしても一度しかカウントされない)。
まずはぴーよとじゅっぴーがデータセットの中身を詳しく調べてくれました。
この問題は図書館をサインアップする順番を決めるパートとスキャンする本を選ぶパートに分かれるので、本を選ぶパートはsimにお願いして、僕は選ぶ図書館とその順番を焼きなますことにしました。
コンテスト中のコードの共有などはslackで行いました。
図書館の焼きなましは2点swapとdelete/insertを近傍として交互に行いました。
本を選ぶsimパートは、ゲインの小さい図書館から順に、価値が高い本を選ぶ貪欲をやってるっぽかったです(よさそう)(違ったらごめん)。
BDはそれぞれぴーよとjuppyが最適解を求められると言っていて両方かなり高いスコアが出ていてすごかったです。
バグらせながらもなんとか実装ができたのですが、凍結前の順位は1600万点くらいで順位は4000位くらいとかなり悪かったです。
終了10分前にsimがC問題の貪欲解を提出したら144万→564万に伸びて何事！？と思いつつその解をもらって初期解にしたら終了2分前にEFもめっちゃ伸びて大騒ぎになりました。
最終的なスコアが合計26711218で、全体598/10724位、国内15/43位になりました。
コンテスト後
Twitterを見ながら感想戦をしました。
反省点としては、コード片以外にも各自の進捗や情報をslackで共有すべきだったかなと思いました。
自分の場合は近傍の取り方や初期解(これが悪くてスコアが伸び悩んでいたことが後でわかった)をどう作ったかなどを共有したほうが良かったですね。とはいえコンテスト時間が短いのでなかなか難しいですが…
来年もまた出たいです。お疲れさまでした。
sim(simkaren)、モジャンボ(Mojumbo)、じゅっぴー(juppy)、ぴーよ(holeguma)の4人でチーム名SiMoJapPiyoとしてGoogle Hash Codeに初参戦しました。とても楽しく、貴重な体験ができたので参加記を残しておきます。
コンテスト前
19:30から22:30まで仮眠をとって、0:00ちょうどくらいに大学に行くとsimとjuppyが待っていました。ぴーよはその一時間後くらいに来ました。その日simはバイト、ぴーよはインターンがあったらしいです。お疲れ様です…
こんなに夜遅くに大学に集まるのはさすがに初めてだったのでテンションが上がりました。研究室に配属されると珍しくなくなるんですかね
集合が早く、コンテストが始まる2:30までかなり時間を持て余しました。僕はじゅっぴーが持ってきてくれたRealforceをしばいて、simはまちカドまぞくを観て、juppyはASMRを聴いて などして時間をつぶしていました。ぴーよが来た後はコンテスト開始後の流れや4人の役割分担を相談しました。
キーボード3台で同時コーディングするのがSiMoJappyの基本スタイルですモジャンボ@Jumbo_kpr
Hash Code 準備完了！ https://t.co/oXQsgwkOqa
2020/02/21 00:26:47
コンテスト
2:30コンテスト開始だと思っていましたが、2:45まで謎の待機時間がありました。
問題が公開されました。まずは全員で問題文を読んで、誤読を防ぐために問題内容を共有しました。
問題の概要はこんな感じです
\(B\)種類の本(それぞれ価値\(S_{i}\))と\(L\)個の図書館があり、期間は全体で\(D\)日間です。
各図書館\(j\)には、蔵書の集合(冊数\(N_j\)と本のIDの列)と、サインアップにかかる日数(\(D_j\))と、その図書館の本を1日に最大何冊までスキャンできるか(\(M_j\))のパラメータが定められています。
図書館は一度サインアップされた後、毎日\(M_j\)冊まで本を選んでスキャンします。(スキャンは並列に行えるがサインアップできる図書館は常に1つまで)。
サインアップする図書館とその順番、またスキャンする本をうまく選んで、スキャンされた本の価値の総和を最大化してください(ただし同じIDの本を複数回スキャンしても一度しかカウントされない)。
まずはぴーよとじゅっぴーがデータセットの中身を詳しく調べてくれました。
この問題は図書館をサインアップする順番を決めるパートとスキャンする本を選ぶパートに分かれるので、本を選ぶパートはsimにお願いして、僕は選ぶ図書館とその順番を焼きなますことにしました。
コンテスト中のコードの共有などはslackで行いました。
図書館の焼きなましは2点swapとdelete/insertを近傍として交互に行いました。
本を選ぶsimパートは、ゲインの小さい図書館から順に、価値が高い本を選ぶ貪欲をやってるっぽかったです(よさそう)(違ったらごめん)。
BDはそれぞれぴーよとjuppyが最適解を求められると言っていて両方かなり高いスコアが出ていてすごかったです。
バグらせながらもなんとか実装ができたのですが、凍結前の順位は1600万点くらいで順位は4000位くらいとかなり悪かったです。
終了10分前にsimがC問題の貪欲解を提出したら144万→564万に伸びて何事！？と思いつつその解をもらって初期解にしたら終了2分前にEFもめっちゃ伸びて大騒ぎになりました。
最終的なスコアが合計26711218で、全体598/10724位、国内15/43位になりました。
コンテスト後
Twitterを見ながら感想戦をしました。
反省点としては、コード片以外にも各自の進捗や情報をslackで共有すべきだったかなと思いました。
自分の場合は近傍の取り方や初期解(これが悪くてスコアが伸び悩んでいたことが後でわかった)をどう作ったかなどを共有したほうが良かったですね。とはいえコンテスト時間が短いのでなかなか難しいですが…
来年もまた出たいです。お疲れさまでした。
ぴーよ@ywmt_kpr
今からインターン、、、
2020/02/21 07:05:51
