脳log[20231216]

2023年12月16日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）があった。自分のすべての提出。ABCDE の中では C 問題が一番難しかった、というか、N 進数を使ったきれいな解き方がありそうで、でも見つけられなくて、芸のない全列挙をするまでに時間をかけてしまった。E まで簡単。F も解けて然るべき難易度だと思ったけど解けなかった。ではふりかえり。■A 問題「Three Threes」。JavaScript だと文字列に乗算が定義されていないので暗黙的に数値化されるところだけど、Ruby の文字列は乗算が繰り返しになる。■B 問題「Pentagon」。線分の長さは２種類。だけど意外に隣接頂点を見つけるのが難しかった。なんでだろうね。■C 問題「Repunit Trio」。E までで一番時間を使った。制約が小さいから答えが見つかるまで全列挙すればいい。でもしたくなかった。結局列挙したんだけど。敗北。■D 問題「Erase Leaves」。最初は頂点１が葉なら１が答えで、そうでないなら頂点１から生える部分木のうち最もサイズが小さいもの＋１が答えだと思った。これはサンプルの３が合わない。そりゃあそうだ。１から生える１つの枝をすべて取り除いてもまだ１から複数の枝が生えているなら１を取り除くことはできない。１から生える最大サイズの枝１本分だけ削除操作が省けるというのが正解。これだと場合分けもいらない。■E 問題「Takahashi Quest」。E 問題にしてはあまりに簡単素直な解法が見えたから、どんな罠を見落としているのか考えてしまったよね。罠などなかった。逆から見てモンスターがいるということを知ってからポーションを拾えばいい。所持数 K を最小化するためにトリッキーな拾い方をする余地があるかと考えてみたけど、そんなものはなかった。結局のところモンスターの直前で対応するポーションを拾うよりましな拾い方はない。■F 問題「Bomb Game 2」。自分が先頭にいて後ろに○人いるときの確率というのを、後ろに０人から順番に求める DP をするのだと思った。元の状態に戻ってくるループがあるなと思った。サンプル１すら合わせられなかった。■■■@2023-12-21 F 問題。Rational でサンプル１を試したらね、1/3 になるべきところが 4/3 になってることがわかってね、計算式に欠けてる項にすぐ気がついてね、そうしたらサンプルの１も２も合うようになりましたね。一度は TLE (#48681588) を出したけど、コンビネーションの計算式を分解してループのあいだ変化しない定数項を外に出したら AC になりましたよ。提出 #48681702 (AC / 574 Byte / 619 ms)。詰めは甘かったけど問題の考え方は間違ってなくて良かった。■ちなみに mod 998244353 の世界において 1/3 は 332748118 で、4/3 は 332748119 なのです。１差。mod の数字を見てもデバッグはできない。