リアタイした回もブログに残さないと「あの解法で解いた回どれだっけ」に対応できないことに今更気付きました。
さすがにunrated合わせて40回前後遡って書くのは(結果的に復習とかでやるかもしれないけど)無理なので、これから頑張ります。
- やった回: ABC318
- 成績: ABC3完 / 2ペナ(+未AC2ペナ)/ 86:31(ペナ込み)
- パフォーマンス: 576
D問題はやったことない解法だったので単純に勉強不足でしゃーないですが、しょうもない勘違いでC問題に時間食ったのが悔しかったです。
A問題: ABC318-A Full Moon
n < m でn日以内に最初の満月が来ない場合は0で返してしまって話を簡単にしておく。
あとはp日おきに満月が来るので、n - m した日数をpで割って、最初の満月のぶんで1足せばOK。
B問題: ABC318-B Overlapping sheets
なんか速度に不安があったのでいもす法でやったんだけど、指定された範囲に都度フラグを立てていく解法でも出来たらしい。 二次元いもす、どこを足してどこを引くのかまだ都度図を見ないと思い出せない… ので、二次元いもすのシミュレーションが出来るサイトがあるので思い出していきたいという未来の自分への手紙を残しておく。これすごい分かりやすい。
C問題: ABC318-C Blue Spring
運賃を高い順にソートして、高い方からD日分ずつ周遊パスに置き換えていって最小値を求める感じ。
方針は概ね合っていたんだけど、損益分岐点近辺の処理を間違えていて、周遊パスにすると損になる日を完全に分けて計算してしまい2WA。
例えば12日の旅程で周遊パス1単位が5日分で、高い方から7日ぶんまでは周遊パスの方が安いっていうケースで5日ぶんと周遊パスの比較、2日分と周遊パスの比較、っていう感じで計算しちゃってておかしくなってた。後で気付いて日ごとの単価だと却って高くつく残りの5日分から3日分引っ張ってきて、得になる下位2日分＋損になる上位3日分 と周遊パスの比較をするように修正したら何とかAC。
一度D問題を見に行って頭を切り替えられたのは良かったけど、もっと早いタイミングで解きたかったなー
たぶん提出コードよりもっとお洒落なコードで書けるはず。
D問題: ABC318-D General Weighted Max Matching
(upsolveコード) atcoder.jp
メモしつつのDFSで書いて2TLEして、多分解法違うんだろうなぁとは思いつつ、コンテスト中はお手上げ。N<=16の制約で何かしらのビット管理の香りは感じたんだけど、未体験のbitDPだったのでこれはもう仕方ない。
管理しないといけない状態が多い場合にそれをフラグの羅列としてビットで表現できるなら次元減らせて管理楽になるよね、というのがbitDPの気持ちという理解を現時点ではしている。
とりあえず立っているビットが奇数個の場合は無視して、立っているビットのうち2つを直近で選んだパス、残りのビットを既に選んだパスとして、立っているビットのcombination(2)を全探索していくイメージ。
今週も対ありでしたー
