結果
ABCD4完(74:55 + 4ペナ)
- Performance: 1175
- Rate: 1293 -> 1280 (-13)
しょうもないWAが多く冴えない回だった
コード
各問題の振り返り
A
特定のパターンの文字列の文字目を取り出す問題
文字列を実際につくらなくても,割り算して何種類目の文字か数えればいい.
いきなり1WA.原因は大文字を出力しなければいけないのに小文字にしてしまったこと
6:42 (+ 1WA)
B
コマの動きをシミュレーションして最終配置を求める問題
コマが追い越さないことを利用して問題を読み変えると少し楽になる.
ここで3WAも出してしまう.原因は,の値だけ制約が少し大きいのを見逃して,メモリの確保が足りていなかったこと. 原因に気づくのに時間がかかりかなりロスしてしまった.
22:24 (+ 3WA)
C
単純なしきい値を用いた判定器の正解率を最大化する問題
一番簡単なのはしきい値で全探索することだが,候補が[tex: 109]程度あるので無理. 実際にはしきい値は与えられた体重のどれか(または体重の最大値より大きい値)だけ考えれば十分なので,これで候補数をに減らせる. ただし,各しきい値に対して正解数の計算は安直にやるとかかるのでまだ少し工夫がいる. 大人,子供それぞれの体重をソートしておいて,各しきい値の候補に対して正しく判定される大人と子供の人数をそれぞれソート済みの配列に対する2分探索で計算することによってで解いた.
16:16
D
任意のジャンプ台の間を移動できるようにするための条件を求める問題
- 訓練の回数を増やすと,飛び移れるジャンプ台の数が増えることはあっても減ることはない
- 訓練回数を固定すれば,条件を満たすかどうかは比較的簡単に判断できる
という点を考慮すると,訓練の回数について2分探索するのが良さそうである. 実際条件を満たすかの判定については,ジャンプ台からジャンプ台に飛び移れるときにの辺を張ったようなグラフを考えて,すべての始点からDFSなりBFSなりして到達可能性を調べることでできる([tex: O(N3)]).
デバッグのためにいれた出力自体が間違っているというしょうもない理由で手間取り,ここでも時間ロスした.
30:33
E
与えられた予算で最大の数字をつくる問題
はじめ,残っている予算に対してその時点でつくれる数字の最大値をDPで求めていけばよさそうと考えた. 一見するとで良さそうなのだが,整数の桁あふれが問題になる. 多倍長整数を使えばできそうに見えるが,整数の桁がになるので,整数の計算やコピーにかかることになり実は全体で[tex: O(N2)]になってしまう.
解決策が思い浮かばず時間切れ.
終了後解説を見て通した. 桁数に注目するという考察ができていなかった. 以前もD - At Most 3 (Contestant ver.)で失敗したが,10進の桁に注目する考察が苦手なのかもしれない.