naoya_t@hatenablog

いわゆるチラシノウラであります

Mujin Programming Challenge 2018

8/4(土) 21:00-23:00
おなか痛い2時間コンテスト
Mujin Programming Challenge 2018 - AtCoder

ooooo--- 5完で119位
Tシャツには手が届かず。惜しい。
f:id:n4_t:20180804233024p:plain

成績上位200位までの方をMUJINオフィスツアーにご招待いたします!

とあるけど…(「MUJIN オフィスツアーに興味がある」にチェック入れてない)

(※この後2am〜5amに開催されたFacebook HackerCup Round2は欠席しました)

参加登録フォーム埋め (0)

トイレ行ってて出遅れた (21:01)
参加登録フォーム埋めるとか聞いてない
埋めた
→AC 1'xx

A - コンテスト名 (100)

pythonでちょちょい (startswith)
→AC 3'33
https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2942362

B - セキュリティ (200)

シミュレーション
A=0始まりの場合のYes、サンプルケースが親切で良かった…(記録が始まる前後も含めて、と問題文にある)
→AC 6'38
https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2942817

C - 右折 (400)

行方向と列方向それぞれに累積和を取っておいて、
すべての交差点について上下左右いくつ行けるか見て (up, down, left, right とする)、
up*left, left*down, down*right, right*up を足していったもの
これなら O(N^2 logN) で行けるのでは
→AC 32'14
https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2943901

D - うほょじご (400)

999x999愚直にやると数十秒かかるんだけど…なにか法則でもある?
いろいろ試してみて分からず
パス!

E - 迷路 (500)

ダイクストラ的な何かなんだけど、信号待ちがあるみたいなやつ
R,U,L,D それぞれの方向に進める時刻を方向毎の配列に入れておけば、ある時刻にある方向に行ける次のタイミングを O(logN) で求まる(行けないこともある)
そんな感じでダイクストラっぽく
→AC 88'01
https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2945125

F - チーム分け (600)

読んだ;スターリング数っぽい問題
Dに戻る

D (再訪)


あるペアからの遷移というのはO(1)で求まって→全部でO(NM)
それが織りなすグラフを考えたときに、(0,y) とか (x,0) にたどり着かないペアの数が答え
逆方向にdagを張って、(0,y)(x,0)から攻めて、たどり着けたペアはマークして
1≦x≦N, 1≦y≦M の範囲でマークのないペアの数が答え、か
(思いついたけどお腹痛くて先にトイレ…)
→AC 112'47
https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2945618
間に合った

G - 移動 (800)

読んでない

H - タイル張り (1000)

読んでない