Google hash code 2019 Final

Google hash code 2019に参加してきました

hash codeって?

google主催のコンテストで、GCJみたいなものです。一番の違いは形式で、2-4人チーム、パソコン無制限で短時間(予選:4時間, 本戦:5時間)というコンテストになっています。 予選は一発で、上位から、人数の総和が150人ぐらいになるまで進出らしいです。

ということからわかるように、GCJ Finalなどのtop25コンテストよりはるかに進出しやすいコンテストな気がします。

交通費

交通費、ホテル、食費のうちいくらか出すとサイトには書いてあります。 僕らがもらう予定の交通費は、全額ではないけど大半、ぐらいです。詳しく知りたい人は直接聞いてください。

環境

ファイルの共有はdropboxを使用しました。短時間なのでgitの旨味がほとんどないからです。

ディレクトリは

- common・
     - common.h
     - random.h
- yosupo/
     - main.cpp
- sigma/
     - A.cpp
- sugim/
     - A.cpp
- maroon/
     - A/
          - main.cpp

みたいな感じです。common.hには問題のファイルからの入力、出力、スコア計算などを書き並べ、全員importします。

戦略みたいなのはなくて、分担したり協力したりをぬるっとやりました。

結果

🌞

感想

5時間で4人4台チームコンテストすると、もうめちゃくちゃになります(チーム戦とは?)

事前に誰が何をやるかとか、もはや完全に分割して別のケースを解くとかするといい気がします。

あとpast gloryはしっかり優勝してて、さすがだなあって思いました。

余談1

Mac book pro(2018)を使っているんですが、最近いろんなキーがチャタリングを開始して、本戦がしんどかったです。 space, nあたりが酷い、対策されたって聞いたのに…

余談2

GWだったのでダブリン->イタリア->ドイツの大型旅行にして、今イタリアにいるんですが、パスポート失くしました。

DDCC 2019

コード部門

  • A: なんかバグった、素直にD言語のgroup関数を使うべきだったかも、遅かった
  • B: 平衡二分木使うか悩んだけどしばらく考えたら貪欲で普通に解けた、遅かった
  • D: もう典型、segtree.hとmatrix.hを貼って終わり、速かった
  • C: みんな解法は簡単というけどそんなことない気がする、実装の方は2ヶ月後にICPC WF行く人幾何担当がこれを解けないとチームをクビになる、でも遅かった(は?)
  • E: コンテスト開始からチマチマ考えていた、1080までは見えていて、残り時間との兼ね合いでそこで諦めることにした、見積もりを間違えてて1110が取れた、速かった

DISCOの人が順位表の凍結にこだわっていそうだったので、せっかくだからすっとぼけることにした。

昼食の時はCが大変なことになって終わった(終わったとは当然文字通り問題が終わった=ACという意味です)とか、Eも提出だけはした(提出した結果0点だったとは言っていない)とか言ってた

装置実装部門

予選: なぜか壮大なものを実装しようとしていたが、そもそも正の点数を取ることすら相当難しいと気づいて方針転換。これが幸いしてギリギリ滑り込めた

10位に入れていそうだったので、予選が終わった後の休憩時間ではすぐに本戦のためにプログラムを改善開始

本戦はesper力、観察力、実装力、盤外戦術力みたいなのが全部問われる不思議なコンテストだった

pre本戦:

  • 向こうの口ぶり的に最速で移動するとどうせ大変なことになる設定なんだろう
  • 最高速を減らすことのメリットが少なすぎる、いじるべきは加速減速時間のみでいいだろう
  • 普通に実装すると45度移動になるが、水をこぼさないように運ぶなら明らかに直線的に動くべきだろう
  • AとかBに移動するとき、真下まで行かずにちょっと前で止まると少しだけお得
  • pre本戦は自分の挙動を確認する以上に、他人の挙動を確認するのが大事だろう
  • submissionの点数を見ることで、n週ギリギリの調整が出来る

あたりには気づいていて、これらを踏まえて適当に良さそうなのを実装して、pre本戦は紙とペンを持って気づいたことをなんでもメモを取ることにした

また、pre本戦ではわざとダメなの送って気づいたことを秘匿しようかとも思ったけど、ぶっつけ本戦で挙動が終わるリスクを考えたら素直に送った方がいいと判断した

以下はpre本戦中の考察や、人を見て気づいたこと

  • E -> Aは水がないんだから最速で移動すればいい(また、A -> Bは水が少ないから少し早くてもいい)
  • AとかBに移動するとき、真下じゃなくてちょっと前で止まると少しだけお得だが、ここでギリギリを攻めると水がうまく給水できずに零れる
  • 4週しかない、5週は時間的にまず不可能だろうし、3週だと水が少なすぎる気がする
  • pre本戦でもっと情報を収集するべきだった(sugimは各週ごとに速度を変えて水のこぼれ具合を調べていた)

また、自分のコードはほとんど自分の予想通りに動いていることが確認できて嬉しかった、特に直線的に動けているかは不安だったので

これを踏まえて、その後の実装タイムでは

  • まずは、E -> Aの速度をmaxにし、A -> Bの加速度はB -> Eの2倍にすることにした(水量が半分だから)
  • 5週でまともな量は運べないだろうこと、3週だとどれだけ上手くやっても4週に勝てないだろうことを確認
  • 理論値480では勝てないだろうと予想して、理論値と加速度のバランスを雰囲気で調整していくことに
  • ↑pre本戦一位(自分)が水をかなりこぼしていたのに435であったことを加味すると、450 ~ 460程度は平気で出るだろうと予想した
  • また、ここらへんでA -> Bの加速度が2倍ではお話にならないことに気づく(ビーカーの形的に水量が半分でも水位は結構高くなる)、謎の仮定(めちゃくちゃでした)を置いた計算の結果1.43(1 / 0.7)倍にすることにした
  • 理論値528で挑むことにした、理由は特になくて、注ぐ時間を100ms刻みで選ぶと480, 504, 528, 552になるんだけど、504だと流石にしんどいだろう & 552は欲張りすぎだろうみたいな判断から)

結果は予想より全然水がこぼれず500.5になった、preよりこぼした量が減ったというのは驚きで、多分もっと理想の理論値は上だったっぽい(下手したら552まで行くかも)

AGC 029

A

隣り合う要素をswapして数列をsortする最小回数は転倒数と呼ばれています

B

  • 2で割れる回数でグループ分けして←いらない
  • 大きい順にマッチしていく

という解法で解いた、1個目いらない

証明

xとマッチできる値たちのうち、x以下のものは1種類しかない、というのが本質

最大の値xとマッチできるyが存在しなかったらx消していい

存在したらx - yでマッチ作っていい(x - yを使わないマッチングがあったとしても、x - yを使うマッチングに変換できる、なぜならx - yを使わないならxはぼっちで、yはx以外の何かとマッチしている、よってy - 何かをばらしてx - yを足せばいい)

C

そもそもどういう文字列をつくっていけばいいか考える

二分探索をする

シミュレーション

D

E

実装を詰めなかったため、破滅

F

twitter

CODE FESTIVAL 2018

本選

対策

特になし

結果

ふつう

原因

Hの得意度は参加者の中でトップクラスだった自信があるため,Iを速やかに解ければ勝っていたと思うが,Iに90分掛けたためどうしようもないね

対策

転生?

りんごの挑戦状

対策

  • ペイントで様々な色を作って眺める
  • トップページを暗記する,日時を重点的に

結果

どうしてこんなことに

原因

R:G:Bの比だけを注意していて,明るさという概念を忘れていた。|R-r| + |G - g| + |B - b|ならR:G:Bの比は本質じゃないんだよな

対策

そもそも地理系に弱いので詰んでいませんか?詰んでいますね(チーム戦にしませんか?)

リレー

対策

例年はふわっとやってふわっと終わるみたいな戦略だったけど,今年は真面目に

最初の5問に2人 * 5で取り掛かって後の5問は臨機応変にみたいな(いややっぱりふわっとしていない?)

結果

2位

原因

戦略が上手く行った,とかではなく他のチームの話を聞くとそもそもチームメンバーが優秀だったっぽい(完)

対策

文句なし

minimize しんどさ s.t. 早起き

背景

突然寒くなって二度寝不可避 →出来る限りしんどくなく早起きしたい

目的関数

minimize しんどさ s.t. 早起き, 現実的な予算

10時起き安定を目標にする

環境

照明

空き巣対策に決まった時間に勝手に電気がつく機能があるのでオンタイマーとして使用,30分ぐらい前につくようになってればいい?

温度

エアコンのオンタイマーを使用,指定方が絶対時間じゃなくて相対時間なのでめんどい。寝起きは体が冷えているのでちょっと温度高めがいいかもしれない。

寝起き直後の行動

布団でスマホを開くと9割がた二度寝なので対策を行う必要がある。 布団から遠くにスマホをおいておく,アプリで目覚ましを止めたあとしばらくはスマホにロックをかける?

食事

飲み物

朝起きるといえばコーヒーだが,そこまで好きではない。 紅茶(ティーバッグ)が最善だろうか

食べ物

食パンはポロポロこぼれるので苦手,レーズンロールを夜のうちに準備しておくとかだろうか,深夜に食べてしまわない強靭な精神力が必要

起きたあとの目的

これがあるかないかで起床成功確率は大きく違う

授業/ゼミ

そもそも午前に無い

研究

最もだが,寝起きでやってなにか進むものではない

散歩

寒い

ばちゃ

一番ありかも,そもそも起床の目的とも合致している

気づき

着替え

C++ライブラリのテストを切り出している

C++ライブラリのストレステストを切り出しているという話

背景

プログラミングコンテストのライブラリには色々と要求されるが,一番重要なのはバグを少なくすることだと思う。 バグが無いだろうと信頼できればバグったときでもライブラリ以外の部分だけ疑えば良くなり,逆にライブラリを疑いだしたらもう実装を簡略化, 高速化するという目的に対し本末転倒ではないかと思う。

もちろんバグがないことを保証するのは不可能であるが,適切にテストを行えばバグが潜む可能性を十分下げることは可能だと思う。

テストの書き方

大きく分けて オンラインジャッジを活用する / リポジトリにテスト用のコードも書く の2種があると思う,両方一長一短

僕は後者のリポジトリにテスト用のコードも書く,のほうが好みで,自分のC++ライブラリ(https://github.com/yosupo06/Algorithm)にもある程度ストレステストを書いたりしていたのだが,ライブラリの長さが制限されているコンテスト用にライブラリをカスタマイズする必要が出てきた(個人的にこのルールに思うところはあるが)。

当然テストは流用できるのだが,どうせなら切り出して両方のライブラリから共通で使えるようにしてしまおうと思い,切り出している。

切り出したもの

https://github.com/yosupo06/algorithm-test

swap(v, v)は危ない?という話

-D_GLIBCXX_DEBUGを付けて以下のコードを実行するとアサートにひっかかります(https://stackoverflow.com/questions/13129031/on-implementing-stdswap-in-terms-of-move-assignment-and-move-constructor)。

struct S {
    vector<int> a;
}
S s;
swap(s, s);

どうやらswap内部でs = std::move(s)が発生し、これがヤバイっぽい(UBを引き起す?)です。 競技プログラミングにおいては、ランダムな並び換え(これはshuffle使えばいいけど)や、ガウスの掃き出し法などでswap(s, s)を使うことが多いと思います。

対策1

swap(s, s)をしないようにする。

対策2

UBと言ってもどうせ動くのでアサート自体を無効化する(https://stackoverflow.com/questions/22915325/avoiding-self-assignment-in-stdshuffle)

#include <debug/macros.h>
#undef __glibcxx_check_self_move_assign
#define __glibcxx_check_self_move_assign(x)

struct S {
    vector<int> a;
}
S s;
swap(s, s);