競技プログラミング

ABC401-F: Add One Edge 3

競技プログラミング

問題概要

  • 2 つの木が与えられる
  • 各木から頂点を 1 つずつ選んで辺を追加すると新しい木が得られる
  • 全ペアについて新しい木の直径の総和を求めよ

【バックパックバトル】パイロマンサー 剣進行

競技プログラミング
基本 木の剣 炎の剣 灼炎フレイムウィップ 灼炎 序盤 1 ターン目 以下のアイテムを買う。 セール品 (石がある場合) 石入り袋 砥石 石 フレイム 2 ターン目 セール品 3 ターン目 ユニークによって方針を変える ダブルレインボー イッツ・スライムタイム！ 太陽鎧ヒートを稼ぐということはスライムが起動するということなので悪くはない 庇護 氷ビルドにして雑に 氷盾 + 氷鎧*2 と置くだけでも割と強い 炎剣進行で拾った剣は灼炎にするとヒートの供給源になるため悪くない 大抵の炎構成では太陽の鎧を 1 個だけ配置することが多いので合わない印象 メモ 以前はハヤブサも検討していたが、グローブがレアな点と 7 ラウンド目前後でノコ刃の剣が出て砥石がある 黒曜カタナ 5 ターン目に鞭 灼炎フレイムウィップ

逆元を知らない人でも確率dp mod 998244353を通せるようにするための「おまじない」(茶~緑向け)

競技プログラミング

せっかくブログを立てたので競プロの記事を書きます。

dp などの問題で確率 mod P (P は大きい素数)を求めることがしばしばあります。
初見だと「は？確率の mod？何いってんだこいつ」となりがちなので、この記事では

単純なナップサック dp のような D 問題相当の dp なら解けるけど、確率 mod P とか言われると「は？何いってんだこいつ」となる人向けに

  1. Python ユーザーが ACL の modint に相当するライブラリ等を使わずに
  2. 答えが小数になることを許容してそのまま実装し
  3. 実装した確率 dp を機械的に mod P に対応させる

というステップで解く方法について整理しました。