模擬地区予選に参加しました
shuriken チーム(僕, 住建, どりきゃす)で参加しました。
jag2017autumn.contest.atcoder.jp
国内予選が初手で僕が早解きする流れだったのでその流れを踏襲
コンテスト
A 問題を見たんだけど, イマイチサンプルの意味がわからず
他の二人が B, C あたりを相談してて話しかけづらい雰囲気だったんだけどわからないのはマズイので聞いてみる->解決
かなりデオクレティアヌス帝だけどまぁなんとか AC
B 問題を住建が読んでたので任せる(エディタ慣れてないのも合わせてかなり時間食ってしまったので僕に実装投げてくれたほうが良かったかも)
その間にどりきゃすと C 問題を見る
ふーん…とか思って 5 分 10 分考えたらわかったので次に行く
E, H が問題文短くてすぐ読めたけど解法はわからず~とか言ってる
その後 F を見て, どうせ全部通れるやろwとか思いながら解法を考えたらなんか浮かぶ
実装めんどくせーとか言いながらもまぁなんとなく実装方針は立つ
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 に参加しました
参加しました。久しぶりに競技プログラミング系イベントに出た感じがしますが楽しかったです。
前日
明後日の夜にDDCC参加者でご飯でも食べに行きませんか
— やざてん (@Yazaten) 2017年10月31日
興味あればふぁぼください
やざてんさんに誘われて飲み会に行ってきました。
自己紹介で好きなアルゴリズム言ったりとかするのは競プロ飲み会独特って感じで面白かった
— マヨ子@紅ダァーーーーーーーーーッ! (@mayoko_) 2017年11月2日
コンテスト前
10:00 くらいに行けばよかったので 30 分くらい前に着けば良いかなぁと思っていたら 8:30 とか 9:00 とかに会場入りしてる人がいてビビった
え、まだ家ですが
— マヨ子@紅ダァーーーーーーーーーッ! (@mayoko_) 2017年11月2日
人々着くの早すぎない?
— マヨ子@紅ダァーーーーーーーーーッ! (@mayoko_) 2017年11月3日
後最近僕がファンになっているチノちゃん競プロなりきり bot の中の人に会えました。チノちゃんかわいい。
他にも昔なじみの知り合いとか Indeed ツアーで知り合った人とか前日の飲み会で知り合った人とか次々と会いました。
コンテスト中
A, B の 2 完でした。
20 分程度で 2 問解いたので残り 1 時間 40 分座っているだけでした。
山本一成さん, 西尾さん, chokudai さん対談
面白い話が聞けました。
印象に残ったことを書いていく(575)
DISCO 紹介, 見学
就活性だし聞いておくべきだったのではとか思ったけどあんまり聞いてない
ていうかどこも調子の良いことしか言わないからか, 話を聞く任意の企業が優良企業に見える
懇親会
btk さんとかヘクトさんとかとしゃべる
btk さんに 114514 回競プロやってと言われた
- のでちょっと自分にしては珍しいことをやった(今いいねしても遅いですよ)
ちょっとやる気出たので#いいねされた数だけACする
— マヨ子@紅ダァーーーーーーーーーッ! (@mayoko_) 2017年11月3日
- 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 でやるときはデコレーションで「ここにアクセスしたときはこういう操作すれば良いよ」というのを書けば良いってのもここで知りました
- 世の中の人いろいろ考えるなぁっていう
話を聞いていると今回は GET /icons/* を高速化するのが大事っぽかったんですが, しょラーさんの提案していた解法が僕にはよくわからなかった(なんか nginx 使って何かするらしい)
その後僕が見てたのは mysql 周り(見てただけ)
- まだ見てないメッセージ数を求めるやつは, 各チャンネルごとに合計のメッセージ数を覚えておき, 各ユーザーが各チャンネルのメッセージをいくつ読んだか覚えておけば(メッセージを消すことが出来ないので)求まるよねという話をした
- GET /fetch のところで, プログラムが sql クエリを何回も呼び出すやつやってて頭悪いな~と思ってたら しょラーさんが解決してた
- 世の中には 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 位!
そのまま終わって終了
終了後
4 位でマジビビった
— マヨ子@紅ダァーーーーーーーーーッ! (@mayoko_) 2017年7月14日
みんなお祝いしてくれてとてもうれしい
レッドコーダーがいなくても、全員競プロを大学から始めても東大で予選通過できることを示してしまったな
— 住建 (@smiken_61) 2017年7月14日
チームメートのこのツイートなんか心に来る
CODE FESTIVAL 2016 に参加しました
タイトル通りです。思ったことをつらつら書いていきます。
1 日目
家から追い出されたのでちょっと早めに家を出ると案の定早く着きすぎた。
来ちゃった♥ pic.twitter.com/r5pIBd4dUS
— マヨ子@大天使クサハエル (@mayoko_) 2016年11月26日
暇だったのでちょっと周りをブラブラしましたが面白いものは電通しかありませんでした。
会場に着いて暇だったので雪の宿を yazaten さんと btk さんにあげたりクソなぞなぞコンテストを作ったりしていました。12/11 に行う予定です。よろしくお願いします。
https://t.co/czhBapNrSv
— マヨ子@大天使クサハエル (@mayoko_) 2016年11月26日
12/11 21:00 から 1 時間の予定です
メインメニューのコンテスト。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
個人的にはとても楽しかったのですが, 上位の人によるとあまり工夫のしどころがなかったようです。
とりあえず自分のやったことを書いていきたいと思います。
貪欲パート
この後「ちょっと待てばレーザーでたくさん消せるならちょっと待つ」というのを入れましたが, これはうまくいきませんでした。
これについて考察すると, 例えば残り 3 個の小惑星があり, 1 つは非常に遠くにあって残りの 2 つはすぐ近くにあるとします。今打つと遠くにある一つのみを消すことになるのですが, ちょっと待ってから打つと近くにある小惑星が 2 つ消せるとしましょう。
そうすると, 元の方法では「遠くを消してからちょっと移動して 2 つ消える」だったのに対し, もう一つの方法では「2 つ同時にレーザー打ってから遠くにある小惑星に近づいてまたレーザーを打つ」となるので, 明らかに損をします。
- 近づく小惑星に関して, 端っこに近いやつほど近づきやすくする, で 68199
- レーザーも端っこ消しやすくすれば良くなるのでは, を勘違いして真ん中にあるほど消しやすくしたところ改善, で 67686
これについて考察すると, 今回の自分のアルゴリズムではなにかの小惑星に向かう動きしか考慮していないので, 宇宙船自体はずっと端っこにいたほうが有利っぽいことを考えるとレーザーは真ん中をたくさん消すほうが良さげだったということですかね。
探索パート
- 行先であり得そうなものを 2 通り拾ってくるようにする, で 62469
- ここでマグカップを確信しました。
- レーザーについてもあり得そうなものを 2 通り拾ってくる, で 61632
- 枝刈りを入れることでたくさん探索して 60117
- 枝刈りは, (今のターン) + (まだかかりそうなターン数) > (今までの最短ターン) だったら消す感じです。
- 時間で粘るようにする, で 59761
後は気合の高速化で探索範囲を広げました。ここまではめっちゃ楽しかったんですがこっからはあんまり楽しくなかったです。
最終的には 59136 ターンで finish しました。最後に確認したときは 4 位僅差で 3 位だったと思いますがどうなることやら。
上位陣の話を聞いたところ,
だったそうです。確かにこれだと高速化ゲーで楽しくなさそうですが, ビームサーチは「ターンでゲームを進めると評価関数つくりにくいなぁ」と思ってた自分にとっては「小惑星の壊れた数」でサーチを進めるのは頭の良さを感じました。なるほど。
できれば 3 位に入っててほしいです…
Codeforces Round #365 (Div. 2) C. Chris and Road
問題
n 頂点の凸多角形が x 軸方向の負の方向に単位時間 v で移動する。この凸多角形の内部に入らないように, y 軸を y = w まで移動したい。
y 軸の移動速度が最大で u の時, 最短で何秒で y = w まで移動できるか。
解法
凸多角形の左側を歩くときと右側を歩くときで場合分けします。右側を歩くのは必ず成功するので, これでちゃんと答えが求められます。
左側を歩く場合, x 軸が最小になる点から y 軸が最大になる点(時計の 9 時方向から 12 時方向ってイメージ)で凸多角形に衝突しなければ良いです。
右側を歩く場合, y 軸が最小になる点から x 軸が最大になる点(時計の 6 時方向から 3 時方向)で凸多角形の内部に入らないようにすれば良いです。
const int MAXN = 100100; pii P[MAXN]; int N, W, V, U; typedef double Real; int prv(int i) { return (i+N-1)%N; } int nxt(int i) { return (i+1)%N; } int main() { cin >> N >> W >> V >> U; for (int i = 0; i < N; i++) cin >> P[i].first >> P[i].second; int imin = min_element(P, P+N) - P; int imax = max_element(P, P+N) - P; Real ans = 1e18; // 多角形の左側を通る場合 { int i = imin; bool ng = false; for (int j = 0; j < N; j++) { Real t = (Real)P[i].second / U; Real x = P[i].first - V*t; if (x < 0) { ng = true; break; } int ni = prv(i); if (P[ni].second <= P[i].second) break; i = ni; } if (!ng) ans = min(ans, (Real)W/U); } // 多角形の右側を通る場合 { while (1) { int ni = prv(imax); if (P[ni].second >= P[imax].second) break; imax = ni; } Real tmp = 0; int y = 0; int i = imax; for (int j = 0; j < N; j++) { // 普通に歩いてかかる時間 Real need = (Real)(P[i].second - y) / U; if ((Real)P[i].first - V*(tmp+need) <= 0) tmp += need; else tmp = (Real)P[i].first / V; y = P[i].second; int ni = nxt(i); if (P[ni].first <= P[i].first) break; i = ni; } tmp += (Real)(W-y)/U; ans = min(ans, tmp); } printf("%.10lf\n", ans); return 0; }