ABC 118 & ABC-D 53-56
3回目のコンテスト参加。
33分 3完で 833th。
パフォーマンス 1121
rating 815 → 872 (+57)
無念。
やはり全完できないとABCではパフォーマンスは全然出ない。
D問題は方針は立っていたのだがどうしてもWAになってしまうケースが残ってしまった。20分かけても原因を特定できずにタイムアップ。
C問題は解説を読むと最大公約数でユークリッドの互除法使う問題だったらしい。
自分はといえば、Aiの最小値で他全てのmodを計算 -> 0になったものを除いて再び残りの最小値でmodを計算 …としてAの要素数が1になったところでその値をprintというコードを書いた。最大公約数であることに気付ければ本来一瞬で解ける問題だった。
D問題は9, 8, … 1の順で、使用可能でかつ最終的な桁数が変わらないような数字をdfsで入れていくという方針で書いた。3が使えるとき2を使う理由がないとかそういうのをいれて高速化するとTLEしない。
ただ、どうしても4つWAが取れないで終わってしまった。
コンテスト中20分かけても原因がわからなかった。
想定解はDPだったようだ。
WAの原因は桁数を固定してしまったところ。
最適桁数の値がそもそも存在しない可能性が取り入れられていなかった。
以下のように、dfsの実行を桁数の値を徐々に減らしながら行えばよかった -> AC
while(!flagout){
dfs(0);
maxdig--;
}
コンテスト中はただコードを眺めて原因を特定しようとしてしまった。
やはりD問題が解けるかどうかはdp力が左右するようだ。
以下、今日やったABC-D解答メモ。
ABC53
カードを食うな。
3枚以上あるカードは確定で操作。
n -> n-2になる。
結果、全てのカードが2枚以下になるまで続けることができる。
11 22 3 4 55のようになったら、
112 -> 1 2 3 4 55
1 55 -> 2 3 4 5
にできる。
2枚以上のカードの組の数は一回の操作でm-> m-2になる。mが0以下になるまで繰り返せばok
よってやるべきは、カードの枚数を数えることと、3枚以上を処理したあとの2枚の組の数の偶奇の判定。
15分ぐらいでAC。
ABC54
N=40なあたり半分全列挙で解けそう。
たとえば、N/2とN-N/2で組み合わせを列挙して、Aの重量/Bの重量でソートしておく。
前半組の各々に対してパートナーをlog(2^{N/2})で見つけられればOK。
前半組の重量比が Ma/Mbより大きい場合、それと組み合わせられるのは後半でMa/Mbより小さいもの。
ただ、重量比では二分探索ができない。
前半をa, b, 後半をc, dとしたとき
(a/b - Ma/Mb) + (c/d - Ma/Mb) = 0が条件。
-> a/Ma - b/Mbでソートする。
これなら二分探索で探せる。
-> subtask05以降が全滅(WA)
原因がわからん。
-> 想定解はDPで、O(N^2 A B)の解法。
dp[i][ca][cb] := i 番目までの薬品の組み合わせで、物質 A が ca グラム、物質 B が cb グラムとなる溶液の最小コスト
半分全列挙による解があることも触れられているが詳細は書いてない。
dpの方が解きやすかったはず。制約に引っ張られすぎた。
この人は半分全列挙で解いている。mapを使うのが良いっぽい。
mapで書き直してAC。おそらく探索部分に問題があった。
-(a/Ma - b/Mb)を探すというコードだと、doubleの差の誤差で思うような動作をしないというのが原因か。
a *Mb - b*Maなら良いのかというと、今度はうまくソートできなくなる。
前半、後半をあわせた総重量を j としたときに、ある与えられた後半組のパートナーが
(Ma * j - after.A, Mb *j - after.B)になるということを使うことで、mapで探せる。
自分の解答はパートナーの決め方についての考察が甘かった。
半分全列挙のパートナーを探すときは、単調性などに依存せず該当する値をダイレクトに探せるmapの方が向いている。
ABC-Dで半分全列挙が要求される問題はそうそうでないだろうという気付きも必要だったかもしれない。
教訓: 半分全列挙にはmap。慣れてない手法を使う前に他の選択肢を検討する。可能な限り浮動小数点計算は回避する。
ABC55
s[i] = ‘o’の場合、t[i-1]とt[i+1]は等しい。
s[i] = ‘x’の場合、t[i-1]とt[i+1]は異なる。
WとSにt[i]を分類すれば良い問題。
Union findみたいな感じで解けそう。
予めunionを２つ用意しておけばいい。W, Sを割り当てておいてok
iの小さい方から見ていくとき、i+1を見た時点でi-1のunionは決定している。一周回って矛盾がなければok
無矛盾に調べていくのが意外と面倒。
0, 1を決め打ちして調べる？
途中まで狼と羊でx, oの振る舞いが違うことに気づいてなかった。
解けたけど時間かかりすぎ。
どうせ0, 1を決め打ちして調べるならunionfindなんぞ持ち出す必要もなく、矛盾しないか確かめるだけで良かった。
ABC56
カード i を含むある部分集合の総和をXとしたときに、
X > K ならば X - ai > K
が成立するなら i は必要。
aiが非常に大きいとき、明らかに条件は満たされない。
aiは小さくなければならない。どのくらい？
X > K ならば X - ai > K
とはつまり、Xにはaiをのぞけるだけの余裕があるということ。
K = 1のとき、条件を満たすものは存在しない。
K = 2のとき、ai = 1が一つだけある時それが条件をみたす。
K = 3の時、ai = 1, 2 が一つで他全て 3以上ならok
もしくは、ai = 1が２つでほか全て3以上ならok
ここから、条件をみたせるのは
-
K未満の数字
-
他のK未満の数字との組み合わせが全てK未満
-
K以上の数字が少なくとも１つ存在
が全て満たされるとき？
もっと複雑。例えば
K = 9
{1, 5, 5}
で1は条件を満たす。
K以上の数字は一つにまとめてしまって良い。
与えられた数列は
{a1, a2, .., an, K以上}
という形。ここでa1, …, anはK未満で昇順とする。
※「aiを除くことで条件が満たされなくなるのは、
部分集合の総和がK -ai以上 K 未満のものが存在する時。」
K = 2のとき、a1 = 1, a2 = 1でアウト。
K = 3のとき、a1 = 1, a2 = 2でアウト。
a1 = 1, a2 = 1は、K-a1 = 2なので問題ない。
というわけで、※でok。このときaiは必要。
i を含まない部分集合の和であって、K未満のものの最大値をリストアップしたい。
部分和を処理する方法がわからない。
dp[i][K]としたときに更新できるか? -> 無理。
除くカードについて独立にやればいい。
あるカードを除いたあとの状態について、
dp[i][j] : i枚目まで使ったときjにできるか
とする。これでO(N^2 K)になる。
あとは単調性を使って高速化。
-> REする。
二分探索を行わないO(N^2K)のコードでもRE, WAしている。
N =1のケア & K以上の数値の処理。
->なんとか部分点までは終了。あとはこれを二分探索に。
二分探索のやり方で混乱した。
不必要と必要の境界が欲しいので、おおまかには
middleが必要ならright = middle
middleが不要ならleft = middle
だが、最初に必要になる箇所をもとめるには？lower_boundのようなことをする。
オチとしては
middleが必要なとき right = middle
middleが不要なとき left = middle +1
とするのが正しい。
教訓: ある値を作れるか否かの管理にはDPがよい。
どうやったら自力で解けていたか。
問題が※の形で言えること、dpっぽいというところまではできていた。
除く数字について独立に解くという方針は、O(N^2 K)になりそうという時点で考察を切ってしまっていた。
やはり、aiの値について、不要、必要に単調性があるという点に気づけていなかったのが問題。
D問題だと現状では半分ぐらいしか解けない。時間内だと1/3ぐらいか。
