競プロ日記

差分: +175

5完
申し訳程度に初5完。
申し訳程度に初水色パフォーマンス。
申し訳程度に緑になった。
Eで終了5分前にTLE3回出して終了17秒前に提出したのがAC。
ジャッジ中に終了通知が来て焦った。
EはACしたものの、いわゆる嘘解法ってやつな上にその嘘解法も未完成。
未完成なのは提出段階から分かっていたが、その部分直すのは時間間に合わ無さそうだったので、出さないよりも出した方がワンチャン！と思ったら通ってしまった。
後で(嘘解法を落とすのとは別の)ダメそうなテストケース考えてチェックしたら普通に間違ってる。

A問題

かんたん。
でも最後の中括弧間違えて消して提出しちゃってCE。
焦って再提出したのは次解くぞと開いていたB問題用のファイル。
つまりテンプレートをそのまま提出してしまった。
CEはジャッジに時間かかるし、テンプレートも入力形式も合ってなくてジャッジに時間かかるし、無駄に時間潰した+WA。
かなり凹んだ。

B問題

かんたん。

C問題

焦ったからなのかちょっと理解できなかったけど10分くらいでAC。
サンプルケース使って解くのはもはやただのパズル。
最初は以下のように考えていた。
町iから町jへの行き方はN-1通り。
それらは全て同じ確率のはずだから、iを固定してjをN-1回ループし、それぞれの距離の合計をN-1で割ったものをsumに足す。
町iをN回ループした後のsumが答え。
でも答えが合わない。
N-1で割るんじゃなくてNで割るようにしたらサンプル全部と合ってAC。

D問題

方針はすぐ立ったのに解き方がアホ。
解説PDFと同じように、n+2m=X, 2n+m=Yの連立方程式を立てた。
なんなら変数名まで同じだった。
そこからnを全探索した(?)。
どう考えても不定形の連立方程式じゃないので、解は一意に定まるはずである。
でも答えが何通りでMOD取るってことは、不定形のパラメータ付きの解になるんじゃないかと思い込み、nを1からXまで全探索した。
もちろんオーダーは計算して全探索にしたのだが、連立方程式を立てた意味が皆無である。
しかもひどいことに、係数2がかかる部分を勘違いして実装していて、全然気づかずに方針が間違っているのかと15分以上溶かした。
連立方程式活用してたらこんなことには・・・。
これ解いた時点で45分+1WA。

E問題

本番ACコード - スーパー嘘解法
スーパー嘘解法修正版(正しい嘘解法)

問題の嘘解法。
特に工夫するところも見つからず単純だけど難しいなぁという印象。
またお得意の問題理解ミスなのだが、「T-0.5分後以降に注文できない」を、「T+0.5分後までなら注文できる」と思い込んでいた。
もはや無茶苦茶である。
それに気付いたのが終了15分くらい前で、実装が大きく変化することはなかったものの、細かい部分はおかしかったり無理矢理だったりする。
無駄なソートをしていたり謎にdp[T]の値を使っていたり。
TLEしてるんだからせめてソート部分は消すべきだった・・・。
まずちょっとミスがあった状態でTLE(残り5分)。
ミス直して(時間に関わる部分は直していないので当然だが)TLE。
setをunorderd_setに直して、ソートされていないことに関わる部分も直してTLE。
unorderd_setの代入部分を参照変数に直してAC(残り17秒)。

以下色々書いて修正したけどそもそも方針が間違いだったというお話。
この嘘解法がTwitterでも報告されていたが、自分はその嘘解法すら未完成だった・・・。
未完成のスーパー嘘解法を嘘解法に昇華させる謎の考察だが、せっかく書いたので残しておく。
一番最初に考えたのは、「最後に注文する料理を決めてそれぞれに最大値求めたい！」というお手本のような方針だったのになぜこうなったのか・・・。

方針としてはDP。
dp[i分まで] = pair{おいしさの最大値, 今まで食べた料理の種類}
おいしさの種類がsetからunorderd_setに変えた部分。
iを0~T-1まで計算した後、全てのiに対して、dp[i]のおいしさの最大値+まだ食べていない料理の最大値を調べ、それの最大値が答え。
全体的には間違っていない(と思う)のだが、同じおいしさの時の処理をしていないのがダメ。
(2分, おいしさ2), (2分, おいしさ2), (4分, おいしさ4)という3つの料理があった場合、4分でおいしさ4を得る方法は、0,1番目を選ぶ方法と2番目のみを選ぶ方法があるが、最後に1つ好きなものを足せることを考えた場合、前者は+4できて後者は+2しかできないので、前者を選ぶべきである。
同じ美味しさだと処理しない実装なので、先に2番目が選ばれてていると間違えてしまう。
例えば、嘘解法のコードに[3 5 2 2 2 2 4 4]を入力すると誤った答えが出力される。(正:8, 誤:6)
これを解決するには、まだ選んでいない料理のおいしさの最大値を持てば良い。
が、それを確認するにはO(N)かかって辛いので、選んだ料理のおいしさの最大値を持つと良さそう。
選んだ料理のおいしさの最大値が小さい方が最後においしさが大きい料理を取れる。

あるいは、dpの情報を増やす代わりに、おいしさの小さい順にソートするのも良さそう。
こちらはあまり自信がないが、おいしさが小さい方から見るようにすれば、おいしさの合計値が同じ時に更新しなかった場合、おいしさが小さい料理が積極的に使われているはずである。
例えばおいしさ1,2,2,3,4,7からおいしさ7を作りたい場合、遷移をdp[i]=max(dp[i], dp[i-料理jの時間]+料理jのおいしさ)とする。
2を作る場合は、2のみ。
3を作る場合は1+2のみ。
4を作る場合は3+1が優先されるが、3には1が使われているので2+2。
5を作る場合は4+1が優先されて4+1。
6を作る場合は5+1が優先されるが、5には1が使われているので4+2を見るが、4には2が両方とも使われているので、3+4。
7を作る場合は、6+1が優先されるが、6には1が使われているので5+2を見るが、5には2が両方とも使われているので、4+3。
・・・とここまで書いて、使われているかどうかで優先されても選ばれないかもしれない可能性がありそうなので、うまく行かなさそうな感じがする。
ちょっとその辺の証明できるほどの実力はまだない。
素直に最大値持つことにする。
と言っても嘘解法でACしてしまっているので本当に正しいか分からない。
※正しくないです

F問題

ちょっと見たけど問題文の理解するよりE考えたほうが良さそうと思った。


初めて嘘解法って奴を通してしまった。
初の5完が嘘解法はちょっと嫌だなぁ。
実質4完である。
うまく行かないだろうなと気付いたものの、時間的に厳しそうでそのまま突っ走ってしまった。
Dの勘違いのタイムロスがなければ、最大値を持った正しい嘘解法はできてそう。

新ABC制覇してかなりコツ掴んできた感あったんだけどうまくいかないなぁ。
目下の目標は全体的な速度アップと間違った思い込みをなくすことだ。
今回嘘解法で不本意に緑になったが、その緑すら落とすようなことはないようにしたい。