毎日格上の問題を倒すやつの39日目です。
これはこどふぉバチャになるので、必ずしも「格上の問題を倒す」ではない気がしますが。
コンテストリンク
結果
AB2完・Score1236・Perf1890相当
A...00:13
B...01:14(+1)
D...(-4)
うーん
— はるく@競プロ (@halc_kyopro) 2023年10月29日
[バーチャル参加]
hirayuu_cfさんのCodeforces Round 857 (Div. 1)での結果は585位でした！
パフォーマンス：1890相当
レーティング：1804→1829 (+25)#CodeforcesAnytimehttps://t.co/5sZhR9jpnS
解法
A. The Very Beautiful Blanket
サンプルを見ると、規則性が見えます。右に2動くと数字が4増えていて、下に2動くと数字が512増えています。
適切に数字を決めたとき、この戦略は有効です。
結論から言うと、左上に
0 1 2 3
を置いてから先ほどの規則を適用すればいいのです。
XORの条件はね。
ここで、数字をかぶらせない方がいいことを思い出します。このままでは、下に2動いたものと右に256動いたものの数字がかぶってしまいます。
まあこれの対処法は簡単です。下に動くとき、4000以上数字を増やせばよいのです。
これは2の冪乗であることが大事です。4096が最小ですが、念のため私は8192増やしました。
B. Buying gifts
1人目にあげる価値の最大値を固定すると、2人目への最適なあげ方を固定できます。
言葉ではこれで終わりですが、ヒープなどを駆使した注意深い実装が必要です。
PyPyでは余裕でTLEすることにも注意です。おとなしくC++を使いましょう(1ペナ)
UpSolve:D. The way home
あぁ、ショーの回数を最小化してその中でお金を最大化するダイクストラね、と思ったら嘘で4ペナ。
実際は持たせる情報が違って、蟻本にも載ってた「報酬後払い」の思考をするのが正解でした。
つまり、「これまで通った中で最大の報酬が得られる頂点」をもって頂点数を2乗する必要がありました。
こうすれば自然にDPぽくダイクストラできますね。
反省として、極端に小さい制約が出たら2~3乗を疑え、というのはまっとうなのですが、私の嘘もそれをフル活用してたので気づきにくかったです。
あとは、いつもの「より確実な方法を検討する」を考えてなかったのが敗因かもしれません。
提出コード
A
B
D
コンテスト中(WA)
コンテスト後
感想
うーん、昨日の0完よりはましだけどそれでも結果が芳しくない…
やっぱARC系はニガテっぽいので克服しないとレート上がりませんね…
空いた日にやってたこと
38日目*1
【今日の精進】
— はるく@競プロ (@halc_kyopro) 2023年10月28日
Codeforces Round 887 (Div. 1)
0完☀️(笑)
A...流石に解けるべきだった問題。
確かに最小の数字をシミュレーションすることが可能。これは盲点だった。
明日ちゃんとリベンジしないとね
*1:0完なのに精進したって言い張るんですか?
