AtCoder Beginner Contest 102 参加ログ
ABC102に参加しました
AtCoder Beginner Contest 102 - AtCoder Beginner Contest 102 | AtCoder
実力：緑色（最高R: 1007, 現R: 915）
今回は約30分おくれて参加（20:30~のところ、21:00~）。
これからは毎週参加して、レポートをこんな感じで書くようにしたい
A, B問題
この二つの難度はいつも通りで、標準入出力さえできて焦りさえしなければ、解ける問題
C問題 Linear Approximation
僕のレベルだと、C問題を解くのに30分以上はかかる。今回もそんな感じ（約34分）だった。
今回の僕の思考を整理すると、
- 問題文よく読む
- 平均値の周りを調べればいいんじゃね？ｺｰﾄﾞｶﾞﾘｶﾞﾘ- => WA
- 平均じゃダメなのか、、、何がおかしいの、、、？
- なんか極端なテストケース突っ込んでみるか
- BruteForceで調べると、確かに答え違うな、、、
- おk、平均、お前はダメだ。medianこそ正しい => AC
問題
WA一回で済んだのは僥倖だったものの、この思考プロセスには問題がある。
コンテストは時計を見ながらやっているので、各プロセスにかかった時間はだいたい把握している。以下の通り。
1: 5 min,
2: 12 min,
3: 3 min,
4: 7 min,
5: 5 min,
6: 2 min
3~6までに17 minもかかっていて、結局はじめから解き直しているのと同じになっている。
これは、2. で問題が正しく解けることの証明をしていないからだ。
反省点
次からはもう少し踏み込んで考え、証明に到るようにする。
D問題 Equal Cut
Dは解けるか解けないか2:8くらいの割合なのだが、今回は8の方だった。
今回の僕の思考を整理すると、
- 問題文を読む
- 全部調べようとすると組合せ爆発するから、何かしらうまい方法を考えなきゃいけないな
- 総和/4の値を超えるかどうかで数字を分けたらどうかな、、、
- quantileを超えたり超えなかったりで数字を分けられないかな、、、
- 時間切れ
こんな感じ。
解説を読んで自分なりに解説してみる
PQRSの切り口をleft, center, rightとする。
centerを固定すれば、
PとQを同じ大きさにするようにしてleftが決まり、
RとSを同じ大きさにするようにしてrightが決まる。
これで組み合わせはN通りしか無くなるので、全ての値を計算して最小値を出せば良い。
もしleft, rightの決定がO(1)で済むなら、全体の計算量はO(N)で済む。
あとは個々の計算量をうまく減らせるかどうかの問題になる。
"total(L, R) # left~right区間の値の和を返す" のような関数を用意しておいて、この関数はただすでに計算済みの値を返すようにする。
こうすれば、leftとrightの決定にも使えるため、O(N)を担保できる。
反省点
結局、「組合せ爆発をどうやって回避するのか」が最も重要なところだったようだ。
僕の思考プロセスのうち３も４も、与えられた数字をどうやって分けるかしか考えられていなかった。
よって今回の反省点は、
- もっと大局観を持って設問に臨むこと（今考えていることがダメそうかどうかを常に評価すること）
- 計算量にシビアになること
結果
R915 => R964 (49 up !!)
時間通りに参加してたらもっと上がってたかも、、、
