mayoko’s diary

プロコンとかいろいろ。

ACM-ICPC 2017 アジア予選に参加しました

参加しました。しばらく競プロはお別れな気がする。

前日まで

前回のDCCCでなんか言っていたが特に達成していない(9/25 AC)

せっかくなので JAXA エクスカーションに行った


なんかあるのかと思ったけど普通の見学だったのでうん, まぁという感じ
せっかくなので風船飛行機を買った(324 円)
たまに飛行機を飛ばして害悪行為をしておりましたすみません

割とグダグダしながら会場入り

会場も割とグダグダだったけどホイホイしながら練習
まぁここらへんは逆に企業間イベントが頑張ってるんだよなぁとか思った
ddccとかこどふぇすとかのスタッフさんすごい

  • 英字キーボードヤバすぎて vim を使う気を起させなかった
  • gedit で行こうかなぁとか思ったけど最後何気なく使った eclipse が案外優秀だったので eclipse で行くことに

ごはんを目の前にひたすら待たされる作業
早く食べたかったよー

ホテル
OpenGL の勉強しようかと思ったけどそういえば環境は my PC にはなかったのでスプラをやる
丁度ガチアサリをやっていたのでやったけどなかなか難しいね


C帯で 29 キルするな

本番

8:00 頃に起床 AC
風船飛行機をしぼませるストローをなくして邪魔だったのでストローを買った

本番の動き
僕がログインしてる間にどりきゃすに A 問題, 住建に B 問題を読んでもらった
A は dp らしいので書き書き
B は全探索らしいので書き書き
C はどりきゃすが式を生成していたので書き書き
I は住建が解いてくれたので一部書き書き
G はなんか知らんけど解かれてた
ここまでで 2 時間半で, ここからの 2 時間半は,

  • 僕とどりきゃすが E 問題で適当な貪欲をして意味不明をする
  • 住建が F 問題を解こうとしてなんかダメ

で終了。コンテスト時間 3 時間で良かったよ

11 位でした。10 位からなんかいい感じだったので惜しい

解説
ただでさえわからない競プロ解説を英語でやるとどうなるか…

閉会式

一位114514知ってた
sigmaさんが負けたの辛いみたいなツイートしてたけどそれでも続けてるのすごいなぁとか思った

懇親会

思ったより就活イベントっぽかった
たまに就活イベントとか行ってるんですけど、そこであった人が割りといてビックリ
いい生活とレトリバから景品もらえたのでハッピー
バランスボールはとりあえず家に一週間くらいおいて使ってみたいです
あとは知り合いも新しい知り合いも含めて色んな人と話せたので良かったです

mayoko と競プロ お別れの時

実際のところ, 国内予選で終わりかなぁと思っていたんですが, なぜかアジア予選に通ってしまったのでここまで伸びてしまいました。
競プロは楽しいんですけど, 解けないと面白くないのでちゃんと練習したいんですが, 最近は別の娯楽(switch とかね)をやってるし研究室とか別のことが忙しいので, 全然解けなくて面白くないを錬成しているのでまた時間が取れたら戻ってきます。

戻って来れるのかは分かりませんが・・・・・・・・・・・

まとめ

SHIROBAKO はいいぞ

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

後から考えると

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

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