Google Hash Code の過去問を流し見る
モチベーション
chokudai さんが 「Hash Code が一番興味ある」みたいに言ってて僕も気になった。
2020年の開催は
予選が日本時間2020年2月21日（金）午前2:30〜午前6:30
Hash Code - Google’s Coding Competitions
普通に参加すると生活が崩壊してしまう。
それはそれとしてどんな問題が出るかくらいは見ておきたいので、過去問を翻訳しつつざっくり眺める
2019年 予選問題
問題の概要だけかいつまんで書くと
Photo slideshow
写真が
枚と各写真
に関連付けられたタグが
個与えられます。 それを使ってできるだけ「面白い」スライドショーを作ってください。
各写真には向きがあり、縦向きか横向きです。 横向きの写真を1枚か縦向きの写真を2枚で1枚のスライドになります。 スライドショー全体では各写真は最大1回しか使用できません。
面白さのスコアは以下のルールで決まります
- スライドのタグはそのスライドが含む写真のタグの和集合になる
- スライドショーのスコアは「連続したスライドのペアのスコア」の和になる
- 連続したスライド
と
のペアのスコアは以下の3つの数値の最小値になる
制約
ぱっと見はしりとりを構築する問題に近いのかな？と思った。 （全く違うかもしれない）
2018年 予選問題
概要
Self-driving rides
2次元グリッド上で自動運転自動車を使いあらかじめ知れる乗車予約をこなす。 自動運転車の操作は「この予約をやる。次にあの予約をやる。次に・・・」形式。 基本的にgreedyにグリッド状を動く。 予約時間ちょうどに予約の乗車位置にたどり着けたらボーナスがもらえる。
なるほど。 王道で面白い。 最近AtCoderでよく見かけるスケジューリング系マラソンもこれくらいシンプルな問題設定だとハードルが下がって楽しそうだ。
2017年 予選問題
概要
Streaming videos
データセンターとキャッシュサーバーとユーザーがあって、ユーザーとデータセンター、ユーザーとキャッシュサーバーのレイテンシが与えられる。 各ビデオデータが何回リクエストされるかも与えられる。 キャッシュサーバーに保存できるビデオデータの容量は決まっている。
キャッシュサーバーにビデオデータを適切に配置して、データセンター直のときからの応答レイテンシーの改善量の平均をよくする。
（問題要約が無茶苦茶だけどまあ良い）
ほとんどナップザック問題だと思うけどどうだろう？
