katsu_y practice 019
記録: hadrori
問題セット
Regionals 2014 :: Asia - Taichung
2015/08/23 14:10 - 19:10 (5h)
久しぶりに記録を残します.
solved | time | A | B | C | D | E | F | G | H | I | J | K | L |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 809 | 8 | 19 | 51 | 82 | 179 | - | 126(+2) | - | 137 | 147(+1) | - | - |
5位相当.7完ではペナルティ的にはぶっちぎってる.
練習前
鍵忘れたので西8に入ることすらできない
— 7 (@hadrori) August 23, 2015
katsu_yさんが8Fの鍵をあけてくれた.流石
練習
s「なんとなく順番に問題読んでるけど本番ではどうしようかね」
s「Aやるだけ」
8分 A WA(AC)
WAとでたけどそれからしばらくデバッグとかするもどう見ても間違ってるように見えないのでACしたことにしました…
難易度に対してAC率が異様に低かったのでジャッジ側になにかあるとしか思えない.
p「Bやるだけ」
19分 B AC
h「Cはぽにょなら一瞬で書いてくれそうなので任せた.クイーンにナイトの動きを追加した感じのやつで最大何個置けるかとそのときの置き方の場合の数」
p「まじかよ.めんどうなやつだ」
h「Eは点と多角形の内外判定するだけ」
p「ライブラリあったっけ」
h「うーん,なかった気がする…」
s「Dは木DPっぽい.考えてます」
51分 C AC
h「Fは行列内の矩形に含まれる値の平均の最大.ただしk個以上の値が含まれること」
h「Gはよくわかんない」
p「読んでみるわ」
h「(H問題文長え…とばそ…)」
82分 D AC
p「711ってどれくらい」
s「2*109くらい」
p「枝刈り入れるしいけるかな」
h「Iは幾何要素ない.フローでどうやるんだったっけなあって考えてる」
s「どうやるんだっけ」
p「蟻本のやつ?行と列で2部マッチング」
h「それで何がもとまるんだっけ」
p「答え」
h「マジか.なんでそうなるんだっけ…全然自明じゃないぞ…」
p「蟻本に書いてあるし…」
110分ぐらい G TLE
p「あとはもっと枝刈りを頑張るか……」
120分ぐらい G WA
p「初期化…」
126分 G AC
137分 I AC
s「Jがいけそうなので書きます」
140分ぐらい J WA
147分 J AC
s「そのままE書きます」
ライブラリとかなしに全部書いていてプロだった.
179分 E AC
h「standingsみよう」
残ってる問題の最終AC数
F : 3,H : 2,L : 2,K : 0
本番で筑波がFを解いている.Fなのかなあという感じでみんなで考える.
残念ながら眠くなったり全然関係ないこと話し出したりして終了って感じだったので終了.
まとめ
- A: あみだくじやるだけ
- B: 最小全域木とかごにょごにょらしい
- C: 探索するだけ
- D: 木DP
- E: 点と多角形の内外判定書くだけ
- F: いったいどうやるんだ…割と典型らしいのでFCCPCはこの解法を求めています
- G: 探索(?) よく知らない
- H: やるだけかと思ったら制約でかくてやばかった
- I: 二部マッチング
- J: よく聞いてなかったのでどうやるのかわかってない
- K: ループみたいなのがやばそう
- L: 例が見辛すぎる.全くわからない