月報 (2023 年 8 月)

ユーフォの新作映画、よかったぜ・・・

観に行ったり飲んだりしてた、いい休日でした pic.twitter.com/VOe11d99Gh

— homu (@homuhomucomp) 2023年8月20日

競技プログラミング

CodeQUEEN 2023 の Writer をした

お疲れ様でした〜
A, B, C, E の Writer でした #CodeQUEEN2023 #CodeQUEEN

— tsutaj (@tsutaj) 2023年8月6日

参加いただいた方々ありがとうございました！4 問 Writer をしました。

問題についてのコメント（ネタバレ注意）

• B 問題
  • 3 乗の方針が若干ちらつくような問題設定にしたくてこうなりました。二乗でも通るはずですが、想定は線形時間です。
  • データセットを作るのがそこそこ大変でした。適当に埋めていって盤面が良い状態になることはほぼないので、焼きなましでなんとかしました。
• C 問題
  • 緑〜水 diff くらいの難易度のものを作ろうとしました。いろいろな解法が存在すると思います。
• E 問題
  • 最初はセグ木を使うのが想定解でしたが、もっと楽にできる方法を後で見つけました。解く時間が早かった方の解法はだいたい楽な方針で、みんな方針選びすごいなぁとなってました。

AHC022 に出た

参加して 180 位でした。

S が大きい場合：温度を 0 か 1000 にする。計測の仕様上、温度が 0 か 1000 のときは真の値が返ってくる確率が S によらず 1/2 あるので、10 回くらい聞いてどちら側なのかを調べることを繰り返して、あり得る候補を減らしていく。うまくいけば S=900 でも全問正解できるときがあった。 pic.twitter.com/OgV9a6kAGn

— tsutaj (@tsutaj) 2023年8月20日

基本的な方針は上の通りなんですが、色々と解法を見てると反省点がいくつかあり・・・

• 0 か 1000 の 2 値で特定する方針は改善の余地あり
  • 0 側か 1000 側かの分類を一度間違えてしまうと、その箇所についてはもう正解できなくなるので、リカバリーが効かず良くなかったです。
  • 計測回数削減のため、すでに確定させた箇所は候補に入れないようにしていましたが、これが原因で芋づる式に間違えていくことがしばしばありました。ワームホール が出口セル につながっている確率を持ってあげるべきでした。
• 1 点だけ高温にする解法の存在に気づかなかった
  • 1 点だけ高温にして相対位置で当てにいく解法がありましたが、気づいていませんでした。（というか正確には、それが現実的な計測回数で回ると思ってませんでした）

ABC に出た

ABC313 と ABC315 に出ました。

アルゴの方は、たまに ABC に出て勘を取り戻す程度になってきてますが、続けられたらいいなあ。マラソンは黄色に上がりたくて、頑張りたい！