mayoko’s diary

プロコンとかいろいろ。

ISUCON 7 final に参加しました

ISUCON 7 final になぞなぞチームで参加しました。
意外に座るだけじゃなかったので良かったです。

チームリーダー(?) が詳しいことを書いている
brookbach.com

競技前



やったこと
  • 二人が構成を頑張っている間に app.py とか game.py とか見て遅そうなところを見つける
    • 僕は完全にのんびり読んでたんですけど, 二人はプロファイル作るのに苦戦していた模様
  • 1 秒先までの未来を見るみたいのが calc_status にあったけど遅いやろって思ってたら実際に遅いらしいので適当に実装
    • test_game.py と言うのがあったので非常にありがたかった
    • test_game.py のテストは通るけどベンチは通らないみたいな感じだったので相談しながら実装して点数上げる(イエーイ)
  • なんかこれが一番やった感あるやつで, あとはいろいろ試したけどベンチ通らなくて悲しいというやつだった
    • 点数上がりそうだなーと思っていたのは, calc_state まわりで前のデータから更新された新しいところだけとってくるってことだけど無理でした
      • 今更ながら, これと Redis に乗り換えるの同時進行でやるのは難しかったのではとか思った
      • データベースは実質グローバル変数だからちょっと変えようと思うだけでもめっちゃコードいじらないといけなくて難しい
へーとか思ったこと

python は型がなくてクソと思ってたけど一応 total_milli_isu : int = 0とかで宣言出来たりするらしい(関数の引数の定義でも似たようなことが出来る)(少し見直した)

  • 3.6 からだった(自分の PC に入っていたのが 3.5 のため)
終わり
  • 去年の反省を生かさずまた大量に食べてしまう
    • おいしいから仕方ないね
    • ケーキ久しぶりに食べた




(解説：僕は web サービスとかサーバーとか全然知らないのに ISUCON に出ている)

模擬地区予選に参加しました

shuriken チーム(僕, 住建, どりきゃす)で参加しました。
jag2017autumn.contest.atcoder.jp

国内予選が初手で僕が早解きする流れだったのでその流れを踏襲

コンテスト

A 問題を見たんだけど, イマイチサンプルの意味がわからず
他の二人が B, C あたりを相談してて話しかけづらい雰囲気だったんだけどわからないのはマズイので聞いてみる->解決
かなりデオクレティアヌス帝だけどまぁなんとか AC

B 問題を住建が読んでたので任せる(エディタ慣れてないのも合わせてかなり時間食ってしまったので僕に実装投げてくれたほうが良かったかも)
その間にどりきゃすと C 問題を見る
ふーん…とか思って 5 分 10 分考えたらわかったので次に行く
E, H が問題文短くてすぐ読めたけど解法はわからず～とか言ってる
その後 F を見て, どうせ全部通れるやろｗとか思いながら解法を考えたらなんか浮かぶ
実装めんどくせーとか言いながらもまぁなんとなく実装方針は立つ

B で割と詰まってたのでコーディング変わって C, F を解きにかかる(なんか B はエディタが保存してなかったのが原因だったらしい)

C はまぁあっさりAC
F は途中まで書いたところで出力見たらバグってて, 住建が B 変わりたいとのことだったので印刷して交代
どりきゃすとコードにらめっこして間違い見つける
B 問題 AC

その後 1 WA のち F 問題 AC
僕が F 書いてる間に G 解けるやろと後ろで相談していたらしく, G 実装してあっさり AC

順位表見て, E と H がねらい目だよねという話をしつつもよくわからないので暇
適当にみんなでバラバラに考え始めるけど結局 E 問題を僕とどりきゃすで, H 問題を住建が考える形になった
最終的に解けたのは H なので住建すごい(解説聞いてえぇ…と思ってしまったけどそういうのも出るんですね)

E 問題は 3 回くらい印刷してどりきゃすとにらめっこしてたけど結局解けなくて悲しい
後で結果見たらスターグラフの場合で落ちているらしい

解説

tokoharu さんが全体的に難しい問題を解説してたんだけど, 知らんってのが多くてあんまりわからなかった(すみません)
今回は全体的に短い行数で書けるのが多かったらしい

解散後

計数の人々がめっちゃいたので, 住建と後 4 年メンバーでご飯を食べに行く
計数 3 年生が競プロ部作ってるとかいろいろあるらしくて計数が競プロ学部になってる感ある(頑張ってくれ)

感想

つくばでも頑張ります

DDCC 2017 に参加しました

参加しました。久しぶりに競技プログラミング系イベントに出た感じがしますが楽しかったです。

前日

やざてんさんに誘われて飲み会に行ってきました。


コンテスト前

10:00 くらいに行けばよかったので 30 分くらい前に着けば良いかなぁと思っていたら 8:30 とか 9:00 とかに会場入りしてる人がいてビビった


後最近僕がファンになっているチノちゃん競プロなりきり bot の中の人に会えました。チノちゃんかわいい。
他にも昔なじみの知り合いとか Indeed ツアーで知り合った人とか前日の飲み会で知り合った人とか次々と会いました。

コンテスト中

A, B の 2 完でした。
20 分程度で 2 問解いたので残り 1 時間 40 分座っているだけでした。

山本一成さん, 西尾さん, chokudai さん対談

面白い話が聞けました。
印象に残ったことを書いていく(575)

  • 競技プログラミング AI がいつ超えるのか？
    • 今も論文が出ているらしい
      • 入力, 出力の関係を見てそれに合致するアルゴリズムをひたすら提出するらしい
      • AtCoder レート 1000 程度は出るとか
    • 競技プログラミングはプログラミングの中ではある意味単純(入力, 出力がきれいにフォーマットされている)ので問題文解釈して論理的にそれに答える等価なコードを書いていけば案外早く超えられるのではと
    • そういうことでまだまだ若い人には競プロ以外のチャネルを試してほしい
  • 人間機械学習千田さん
    • (将棋盤面の)学習セットとテストセットを分けて学習セットの評価値を学習しながらテストセットの盤面の評価値を最小二乗法で最小化する(は？)
  • プログラマーは PC に論理を与えるのをやっている
    • プログラム自体は論理を理解していない

DISCO 紹介, 見学

就活性だし聞いておくべきだったのではとか思ったけどあんまり聞いてない
ていうかどこも調子の良いことしか言わないからか, 話を聞く任意の企業が優良企業に見える

懇親会

btk さんとかヘクトさんとかとしゃべる
btk さんに 114514 回競プロやってと言われた

  • のでちょっと自分にしては珍しいことをやった(今いいねしても遅いですよ)

  • kuuso さん初めてお会いした気がする(ありがとうございました)
  • 他にもいろいろな人に会った気がするけど忘れた(ごめん)

何も知らないのに ISUCON 2017 に参加した

チーム「座るだけのコンテストってな～んだ？」で OKeiGo さん, しょラーさんと一緒に ISUCON 2017 に参加しました。

僕がやったのは, チーム名を考えることと, それを実際に実行することだけです。

前日まで

Vagrant で ISUCON の環境を再現できるものがあり, それでホーンとか言ってた
github.com

これ使ってなんか勉強しようとネット資料とか見てたけどみんな難しい言葉使っていてわかりませんと言う感じ

サーバーの概念に多少詳しくなったけど肝心の実装は何もわからない

  • 冷静に考えてお前コード読むことしか能ないんだからもうちょっと app.py とか読んでおけばよかったのにと始まってから思った
  • というかしょラーさんと OKeiGo 君だったら僕いらないだろとチーム組んだ時から思ってた

当日

一番いろいろ勉強できた気がする
他の二人が頑張ってセットアップしてる間にへーとかホーとか言ってた

  • ていうか二人が詳しそうなのでなんか思いついても言いづらいなぁみたいな気持ちはあった
  • ssh でどう接続すれば良いのかもよくわからなかったし, web サービス自体どうやって閲覧するのかもよくわからなかった
    • 理解するのに 30 分くらいかかった

後ほかの二人が slack で話してるのを見てヘーとか言ってた

  • python でやってたんですけど, os.environment.get() ってやると環境変数が取れるらしい
    • それでヘーと思って echo $ISUBATA_DB_HOST とかやってみたけど特に何も起きなくて解せなかった

app.py を読んどけと言われたので読む

  • flask とか言うのが web アプリケーションのフレームワークになってることを初めて知った
  • おそらく ISUCON ではそんなに大事な部分ではなさそうですが, login とか logout ってこうやって実装するんだーみたいのも初めて知った
    • flask.render_template(filename) で filename を渡すとか(GET でよく使う)
    • POST の時には flask.request.form['hoge'] で hoge を受け取るとかしてるっぽいですね
    • flask.session がよくわかってない
      • 複数の人がいるのに flask.session.pop() とかで除外するみたいな感じで良いんだろうか

後まぁ flask でやるときはデコレーションで「ここにアクセスしたときはこういう操作すれば良いよ」というのを書けば良いってのもここで知りました

  • 世の中の人いろいろ考えるなぁっていう

話を聞いていると今回は GET /icons/* を高速化するのが大事っぽかったんですが, しょラーさんの提案していた解法が僕にはよくわからなかった(なんか nginx 使って何かするらしい)

その後僕が見てたのは mysql 周り(見てただけ)

  • まだ見てないメッセージ数を求めるやつは, 各チャンネルごとに合計のメッセージ数を覚えておき, 各ユーザーが各チャンネルのメッセージをいくつ読んだか覚えておけば(メッセージを消すことが出来ないので)求まるよねという話をした
  • GET /fetch のところで, プログラムが sql クエリを何回も呼び出すやつやってて頭悪いな～と思ってたら しょラーさんが解決してた
    • sql でもらった結果を配列として持っておいて, 配列で for 文を回せば OK
      • python 詳しくないので書き方がわからなかった
  • 世の中には slow query というボトルネッククエリを調べられる便利機能があるらしい
    • 使い方イマイチわかってない

その他気になったこと

  • password に salt つけてハッシュ化するってやつ, たまに見るけどそれ意味ある？と思っているのでやる必要性が気になる

感想

世の人々はこんな複雑な web 系プログラミングに詳しくてすごいなーと思いました。

ICPC 国内予選 2017 に参加しました

4 位でめでたい！

開始前

Sleep, 114514, lsplpl, catsatmat の次で 5 位くらい入ればワンチャンあるのでは？とかそれ無理でもドワンゴ賞と NTT 賞が美味しそうとかいう話をする
結構時間余裕を持って会場入りしたので暇
戦略としては僕が基本的にコーダーをやる感じに

本番

問題文は印刷してもらってその間に僕は A と B を解く
A ははい
B はめんどいけどなんとか
A と B 解いてる間に C と D 見てもらってて, C はなんか解けて D は難しいらしいので C は解いてもらって D の相談
「ユーて n*m 小さいし場合分けして行けない？」と聞いて最初えーって言ったけど行けるやんと気づいて C 問題 AC の直後書き始める -> AC
D 解いてる間に E の解法が大体出来ていて, 「書いて」と言われたので書く
バグバグ
バグバグしてる間に F わかったらしいので書いてもらう -> AC(天才か？)
E もなんかバグ取れて AC
予選通過ワンチャンあるんじゃね？という空気になり始める(たしか 4 位くらい)
G もなんか考えられていて, 「右手法っぽくやればいいんじゃない？」という話だったのでじゃあ実装するか〜ということに
バグバグ
実装の思いがこっちに伝わってなかったっぽいのでいろいろ言いながら実装完成させる->AC
G を AC するだいぶ前に catsatmat とかが 7 完してたっぽいので今更かな〜と思ったけど順位表見たら 4 位！
そのまま終わって終了

終了後


みんなお祝いしてくれてとてもうれしい
チームメートのこのツイートなんか心に来る

CODE FESTIVAL 2016 に参加しました

タイトル通りです。思ったことをつらつら書いていきます。

1 日目

家から追い出されたのでちょっと早めに家を出ると案の定早く着きすぎた。


暇だったのでちょっと周りをブラブラしましたが面白いものは電通しかありませんでした。

会場に着いて暇だったので雪の宿を yazaten さんと btk さんにあげたりクソなぞなぞコンテストを作ったりしていました。12/11 に行う予定です。よろしくお願いします。

メインメニューのコンテスト。1600 点でパーカーがもらえるらしいというのと配点からまずは ABCDe を解くことを目標にしました。

  • A 問題: はい。
  • B 問題: 最初 N 点「以上」だと思って超簡単な貪欲じゃんと思ったら WA して「は？」と言ったけど適当に二分探索して通した。
  • C 問題: 「多分連結っていうので良くね？」と思って提出したら AC して良かった。AtCoder の配点はよくわかりませんがいつもの 400 に比べると簡単だった。
  • D 問題: これはちょっと迷った。しばらく考えた後,
    • M で割ったあまりで考える
    • M で割ったあまりについて, 奇数個余っているようなものについて注意する
    • M で割ったあまりが i <-> M-i となるようなものをペアにしてごにょる
  • みたいな方針でできることに気づいて, 適当にやったらサンプルあったので提出したら AC した。これはバグらせるかと思ったのでラッキーだった(ここで詰まって終了した人もいたらしいけど, 辛そう)。
  • E 問題: 適当に dfs 枝刈りしたら部分点はとれた。満点をしばらく考えていたけどわからなかったので 次の問題を見る。
  • H 問題: 次の部分点なのでちょっと見たが難しそうだったのであまり真面目に取り組まなかった。
  • F 問題: 一瞬である程度の方針が立ったので簡単な気もする。最初に思いついた方針は少し間違えてたけどまぁ修正できる範囲で, 普通に AC。これはうれしかった。

後は E の満点, H の部分点を考えててた(特に E ばっかり考えてた)けどわからず終了。去年は面白い問題に取り組む前に終了してた感じだったけど今年はそこそこ楽しめたので良かったです。無事パーカーももらえたしハッピー。

後はごはん食べたりペアコーディング見たりエキシビジョンマッチみたりしました。

  • AC 画像について, ガーリッシュナンバーに変更したのは良くないという意見を受けました。
  • エキシビジョンはちょっと考えたけどわからず…海外勢が 0 完太陽だったのは面白いですね。

最後リレーでよろしくお願いしますするときに英語離せないの辛いなーってなりました。tozangezan さん普通に話せててすごいなぁと思いました。

2 日目

トーナメントは B 問題が簡単そうだったので 400/600 を狙ってたんですがバグって終了。0 完太陽でした。
A 問題の最小全域木作ってあらかじめ i から j への最大コストとか覚えておくののテクニックとかアルゴリズム的正当性がすごい頭良いなぁと思いました。

トーナメントは割と難しい問題だった気がするので 45 分 2 セットでも良かったような気がします。あんまり消化しきれてない感じが。

あと Round2 の A も 1 行でかけると聞いて考えてたんですがこれも面白かったですね。後で chokudai さんに賢い考え方を教えてもらいました。ところでいまだにいろはちゃんと chokudai さんの違いが分かってない。誰がやってるんだ。

その後のトークは kyuuri さんの LT とりんごさんのクイズが面白かったです。snuke さんがクソなぞなぞに言及してたのはなんとなくうれしかったです。

最後にリレーがありました。本選でまぁまぁいい順位だったせいで I 問題を割り当てられました。が, 普通に難しくてわからなかったので海外勢に教えてもらいました。すごい。ここでも英語できないの辛かったですね…

ところで I 問題は書くべきことを記憶するのが非常に面倒なロシアゲーだったのでメモを持っていくのを許可してほしい感じがありました。頭の中で解法を思い起こしながらコード書いてたら「ﾏﾀﾞｰ?」みたいなこと言われてすまぬ…となりました。

後から考えると

  • クソなぞなぞ談義したかった
  • ハル研プロコンの話もうちょっとしたかった
  • コンテンツ別のやつもうちょっと楽しみたかった

とかいろいろやればよかったと思うことありますが楽しかったです。運営の方々本当にありがとうございました。

ハル研プロコン2016に参加しました

ハル研プロコンに参加しました。
www.hallab.co.jp

個人的にはとても楽しかったのですが, 上位の人によるとあまり工夫のしどころがなかったようです。

とりあえず自分のやったことを書いていきたいと思います。

貪欲パート
  • 一番近くの小惑星に近づく, 最も小惑星が消える方向にレーザーを打つ, で 76240
  • レーザーで遠くにいる小惑星が消えてくれるほうが嬉しいのでそうする, で 71813

この後「ちょっと待てばレーザーでたくさん消せるならちょっと待つ」というのを入れましたが, これはうまくいきませんでした。
これについて考察すると, 例えば残り 3 個の小惑星があり, 1 つは非常に遠くにあって残りの 2 つはすぐ近くにあるとします。今打つと遠くにある一つのみを消すことになるのですが, ちょっと待ってから打つと近くにある小惑星が 2 つ消せるとしましょう。
そうすると, 元の方法では「遠くを消してからちょっと移動して 2 つ消える」だったのに対し, もう一つの方法では「2 つ同時にレーザー打ってから遠くにある小惑星に近づいてまたレーザーを打つ」となるので, 明らかに損をします。

  • 近づく小惑星に関して, 端っこに近いやつほど近づきやすくする, で 68199
  • レーザーも端っこ消しやすくすれば良くなるのでは, を勘違いして真ん中にあるほど消しやすくしたところ改善, で 67686

これについて考察すると, 今回の自分のアルゴリズムではなにかの小惑星に向かう動きしか考慮していないので, 宇宙船自体はずっと端っこにいたほうが有利っぽいことを考えるとレーザーは真ん中をたくさん消すほうが良さげだったということですかね。

探索パート
  • 行先であり得そうなものを 2 通り拾ってくるようにする, で 62469
    • ここでマグカップを確信しました。
  • レーザーについてもあり得そうなものを 2 通り拾ってくる, で 61632
  • 枝刈りを入れることでたくさん探索して 60117
    • 枝刈りは, (今のターン) + (まだかかりそうなターン数) > (今までの最短ターン) だったら消す感じです。
  • 時間で粘るようにする, で 59761

後は気合の高速化で探索範囲を広げました。ここまではめっちゃ楽しかったんですがこっからはあんまり楽しくなかったです。
最終的には 59136 ターンで finish しました。最後に確認したときは 4 位僅差で 3 位だったと思いますがどうなることやら。

上位陣の話を聞いたところ,

  • 方針はビームサーチ
  • 小惑星の壊れた数でサーチのターンを進めていき, 評価関数は経過ターンのみ
  • 遷移は基本的に 8 方向で, 40 ターン以内にぶつかって破壊できるときは小惑星に向かって近づく

だったそうです。確かにこれだと高速化ゲーで楽しくなさそうですが, ビームサーチは「ターンでゲームを進めると評価関数つくりにくいなぁ」と思ってた自分にとっては「小惑星の壊れた数」でサーチを進めるのは頭の良さを感じました。なるほど。

できれば 3 位に入っててほしいです…