2位でした。とっても嬉しいです。おかげで懇親会では普段のN倍口数が増えて、参加記も文章が増えます。
開始前
紙ぺーぱーさん、とこはるさん、すぎむさんとお昼にカツを食べた。願掛けは意識してない。
会場の入り口前でchokudaiさんに遭遇した。
案内板らしいものはなかったのでchokudaiさんが居なかったら少し困ったかもしれない？
会場入り。受付してQUOカード10000円(ギリギリ首都圏外判定)とTシャツを手に入れる。
レッドブルを配っていたがおなかの調子があまり良くないのでスルー。
席について接続テスト。最初は繋がらなかったが数分で回復した。
始まるまで適当に机を整理してtweetdeckを眺める。
本戦中
考察と実装と感想をある程度分けてるので若干時系列が前後します。
開始直後、本戦問題を開くリンクを押してもリンク先が間違っていて何も起きない。URLを推測したら1発で当たった。
問題が長い。適当に読み飛ばしながら読む。
正の点数を得るにもそこそこステップが必要そう。仕事を受注して、仕事に社員を割り当てれば良いらしい。
仕事の納期に間に合わないと罰金があるので、仕事はこなせる分だけ受注しないと死にそう。
仕事の種類によって、得意な社員が異なるので、仕事に対して処理能力が高い社員を順に割り当てていき、期限ギリギリで終わるように人数を調整するという方針になった。
とりあえず色々な情報が手に入るgetinfoを叩いて情報をクラスにホイするプログラムを書いて、そこから点数を取れるようにしていく。実装がクソ重い。
第一世代プログラム
- 仕事がなく、かつ待機している社員が15人以上いれば仕事を1つ取る。
- 受注した仕事に対して、待機している社員から、その種類の仕事の能力が高い順に割り当てる。期限内に終わるようになるまで人数を増やす。
15人以上の待機を確保したのは、ある程度待機させた方が、来た仕事に対して高い適正のある社員が残っている可能性が高そうだから。
最初のプログラムを動かし始めた時点で既に一時間くらい経過していた。この時得られるポイントは最終的には8分の1になる。
大事な所だけを文章にすると短いけど実際問題を読んだり考察したりコード増やしたりを行ったり来たりしている。
最初のプログラムの効率が結構良かったらしく、前の順位表を見るといつの間にかランクインしていた。案外みんな大したことないのかとか、上位陣は潜伏して他のこと考えてるんじゃないかとか思った。
点数が得られるようになったので、仕事のデータなどをログに吐かせて考察する。
効率を上げるにはどんな指標が必要か考える。社員が50人と決まっていることを考えると、社員一人あたりの時間あたりの稼ぎ、つまり
(仕事の報酬) / (仕事にかかる時間) / (仕事に割り当てる人数)
が高いほど良さそう。
この値は仕事と、現在待機している社員のパラメータによって決まる。社員の割当方法は変更なし。今後この値を仕事の「指標」などと言うことにする。
指標は仕事が完了できない場合にはとりあえず-(罰金)としておいた。
ログを見るとこの指標は仕事によって大きく差があり、低いものは0.1未満、高いものだと0.7とかを超えた。
すると、仕事をせずに罰金を食らってでも、効率のいい仕事だけ取れば良いのではとなり、仕事を外注するというシステムがあるのでこれを利用したくなる。
仕事を取ってきて効率が悪そうなら外注にする。
また、効率のいい仕事を外注で見つけたらそれを割り当てる。
この方法で細かい試行錯誤をして次のようになった。
第二世代プログラム
- 外注されている仕事を見て、指標の最大値が0.6以上だったら即座にその仕事に社員を割り当てる。
- 外注している仕事が5つ以下かつ、待機している社員が15人以上いれば仕事を1つ取る。
- 受注した仕事の指標が0.2未満ならば外注する。0.2以上ならば社員を割り当てる。
これを実行してみると外注の仕事ばかり取ってきた。外注は宝の山だった。
ほとんど考察していなかった経験値や社員の挿げ替えについてはもう手遅れという感じだったので、方針はこれ以上変えられないという感じになり、このプログラムで最後まで走ることになった。
順位がみるみる上がっていくのを観測できた、そのうち2位になって、さらに1位になった。やったぜ。
ここからはパラメータ調整職人になった。主に外注されている仕事を取ってくるしきい値が大事っぽい。
しきい値を上げると社員の割り当てがあまり起きなくなり、暇な社員が増える。15人以上になった時は受注で暇な社員を減らしていたが、やはり受注は指標があまり良くなかった。
時間あたりの金の効率 >= しきい値 * 仕事している人数
みたいなことが言えるので、働いている人数との兼ね合いを考えてしきい値を調整していた。
ものすごい勢いで追い抜かれて2位になった。パラメータ調整職人しても追いつけそうにない。
どこで差がついたのだろう。やはり挿げ替えや経験値を序盤に見なかったのが痛かったか。それとも割り当てのアルゴリズムが悪かったか。
終了30分前くらいから、市場に出回る仕事の指標が高くなる傾向があった。
外注に手を出す人が増えたのでいい仕事を見つける可能性が上がったのか、ヤケクソで好条件で外注してる人でも居るのだろうか。
外注の仕事をもらうしきい値0.6は最後には1.5になっていた。
コンテスト終了。100850点で2位。
1位,3位とはそれぞれ1万点以上差がついた。終盤は順位は変わらないなあと思っていた。
表彰
こういうコンテストで壇上に上がるのは初めてでとても嬉しかった。あと緊張した。
最初にポイントを稼いだコツを聞かれるの、感想が言いづらくて厳しい。
これ顔出し配信じゃんって思ったけど、そもそも上位に居た時点でかなり映っていたらしい。
10万円の使い道は検討します。
その他コンテストについて
人によって応答が帰ってくるまで異常に時間がかかることがあったらしい。幸運にも自分は全くそのようなことがなかった。
難しいだろうけど出来るだけ不公平がないように運営がんばってほしい・・・
問題は面白かったです。なんか利益を最大化するために部下の使い方など手段を問わないブラック会社が生えた。
ただ問題の要素はもう少し少ない方がとっつきやすい気がする。
前準備してた話
表彰の時にも話した前準備のことです。
ゲーム終了直後の記念SSがこれです。ザ・Swingという感じ。
ぼくのかんがえたさいきょうのCODE RUNNER環境(クソ図でごめんなさい)
を実現しようと準備してました。
去年の本戦でプログラムを複数作って、手動で止めたり走らせたりしたという話を聞いてそれ良さそうだなあと思ったので、じゃあwindowsのタスクマネージャー的な物を用意してプログラムを一部だけ止めて差し替えたりとか色々できそうだなあと思ったのですが、そういうことに向いていそうなスクリプト言語の知識がありませんでした😇
実現したこととしてはプログラムやサーバーが止まったときに備えてデータをセーブロードしやすいように支度したり、グラフにプロットできるようにしたり、ログを出力したり、クエリを効率よく投げられるようにしました。
結果として本戦で便利だったのはログ出力・グラフプロット・クエリライブラリの3つでした。
ログは標準出力垂れ流しと大差ない気はしますが、Eclipseのウィンドウから独立してるのは良いです。
グラフプロットは分析やパラメータ調整職人の時に役立ちました。
クエリは種類ごとに時間を管理したり、自動リトライとか、エラー処理を入れてかなり快適な感じにしました。
並行プログラミングやGUIが役に立ったのでプログラミング第三(講義)に感謝🙏
コンテスト後
懇親会。2位なので調子に乗れる。
大体お昼食べたメンバーやキーキさんと固まる。
uwiさんと周りの人が話してたが、僕は顔を知らなかったのでチームラボの人だとしか分からなかった。
去った後に周りに聞いてみたらuwiさんだった。話しに行かないと。(使命感)
懇親会の半分以上の時間はuwiさんと話してた。
Java競技プログラマーの超強い人と話すのは初めてだったので、ライブラリのことについて聞いて色々知見が得られた。
ボクシングを出来るだけ減らすと速いらしいです。データ構造全部自前不可避。
No.310 2文字しりとり - yukicoderの素晴らしさを力説されるなと、Javaに関係あったりなかったりする話題で盛り上がったと思う。
紙ぺーぱーさん、すぎむさん、キーキさんとCOCOSで夜ご飯。懇親会でサンドイッチ3切れしか食べていなかったので助かった。
COCOSは初だったが普通のファミレスだ。立地の関係か人は多かった。
作問の話になった。
ぐるぐるツアーはクソ。(ハマったから過剰にdisります)
www.hackerrank.com
CODE FESTIVALの時からデータ構造を布教されているので次は平衡二分探索木を書かないといけない気がする。
新幹線でおうちへ。参加記を書く宣言をしていたので書く。クッソ時間かかった。
関係ないけど
yukicoderで12/25まで毎日問題が追加されるAdvent Calender Contestが今アツイです。
順位表→順位表- yukicoder
Adventar
www.adventar.org
僕の問題が16日,水曜日に公開されるので是非解いてください。
