/ 最近 .rdf 追記 編集 設定 本棚

脳log[20230812]



2023年08月12日 (土) [AtCoder] 今日は ABC314 があった。コンテスト成績証自分のすべての提出。配点を見たら 100-200-300-400-475-475-575-625 だったから E と F は易しめなのかなと思っていたら全然そんなことはなかった。E も F も解けず ABCDG の5完。E は解きたかった。ABCDEG ならこれまででベスト3の順位だった。まだ解けないんだから実のない願望ではある。以下 ABCDG のふりかえり。■A 問題「3.14」。切り捨てを四捨五入だと誤読した。小数点以下 N 桁までしか知らされていないのに四捨五入して小数点以下 N 桁を出力するためにどうしようか考えてしまった。0を補おうか? いま再読すると「小数第 N+1 位で切り捨て」と書かれているのがミスリーディングだと思う(やつあたり)。切り捨てであってもないもの(N+1 桁目)を操作することはできないじゃない。考えちゃうよ。提出 #44490051 (AC / 142 Byte / 43 ms)。■B 問題「Roulette」。制約は小さいしやるだけではある。でもあまりやりたくない気分になる。見通しよく素直に実装すると3パスの操作になる。すぱっときれいに片付ける方法はないものか。考えた結果ソートなんてしてしまう人間(私です)は計算量についてイチからやり直そうな。提出 #44494576 (AC / 235 Byte / 44 ms)。■C 問題「Rotate Colored Subsequence」。色ごとに文字を積んでローテートして取り出すだけではある。でもケチなことを考えた。総要素数が N 個になる M 個の配列を作りたくないなと。要素数 M 個の文字配列だけで済ませたいなと。それで TLE を出しているのはただの間抜け。4-7 行目が良くなかった。提出 #44500699 (AC / 220 Byte / 158 ms)。TLE の解消方法がまだいまいち。reverse_each をやめても前から順に常に上書きするなら同じ結果が得られる。■D 問題「LOWER」。クエリ2と3があると文字列の大文字小文字がすべて決まってしまうのだから、文字列を直接書き換える他に、クエリ2と3の後のクエリ1についてだけ記録を残して上書きすればいい。例によって toupper やら tolower やら locase やらを試してとうとうリファレンスを調べた。upcase の反対は downcase らしいです。提出 #44506770 (AC / 266 Byte / 666 ms)。クエリ先読みが有力だったっぽい。■G 問題「Amulets」。問題の構図は比較的理解しやすく、データ構造の知識が問われる問題だった。持ち込むアミュレットの種類は後出しで選ぶ。どのように選ぶか。n 体目のモンスターまでで総ダメージが sa になるとする。モンスターのタイプ別でも総ダメージを記録しておく。タイプ別総ダメージが大きい方から k 個を選んでアミュレットでダメージを無効化するのが最善。その結果総ダメージが H 未満になるならいいが、H 以上になるなら n 体目のモンスターは倒せなかった。アミュレットの個数と倒せるモンスターの数は比例関係にあるので、アミュレットの数とモンスターの数を増やしながら答えを記録していく。たぶんだけどアミュレットは増加していく単一の集合ではないと思う。つまり、k=2 で選ぶアミュレットは k=1 で選ぶアミュレット+1ではないと思う。だから BIT で都度都度最適な k 個を選ぶようにした。top k の総和を効率良く求めることがこの問題の中心だった。BIT にたどり着く前にはプライオリティキューを貼り付けたりしていた(でも行き止まり)。BIT で個数と総和を管理するのはついこの前 ABC312-F Cans and Openers でやったばかり>提出 #44067838。その問題にその解法は log が余分に付くうまくない解答だったのだけど、それが今日の解答のプロトタイプになったのだから怪我の功名。提出 #44529976 (AC / 1412 Byte / 1731 ms)。べつに今回が2回目ってわけでもない。ABC287-G Balance Update Query への提出 #38427641 でもやってる。