問題 atcoder.jp 解説 生成できる最小値と最大値を計算すれば、間の組み合わせ数は、おのずと割り出せる。 実装 参考 youtu.be

問題 atcoder.jp 解法 区間DPで解く。 区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。 𝑑𝑝[𝑙][𝑟] := 区間 [ l, r ) について、最適な状況下での何かしらの値 dp[0][0]から、幅0でdp[0][0], dp[1][1], dp[2][2] ....と計算していく。 先攻後攻…

問題 atcoder.jp 解法 コンテスト参加中 「DFS(深さ優先検索)だろ！こりゃACもらった！」 と思ったら、TLEで解けなくてガッカリだったー。 ので復習。 この問題、DFSで木を上方向に戻る処理まで再帰関数で実装してしまったんだが、1に戻って終わるのが前提の…

AtCoderの問題の答え表示で、横一列表示が出て、 「あれ？どうすんの？」 と思い、調べたのでメモ >>> A = [1, 2, 3, 4, 5] >>> print(*A) 1 2 3 4 5

問題 atcoder.jp 解法 1 <= N <= 4000 なのでO(N3)だと、43 * 109 でTLEのはず。 なので、R, Gの二つの要素を固定。 すると O(16 * 106) くらい？ あとは、計算でBの要素から何個採用できるかを出す。 この方針でTLEは出ないはず。 R, Gのある場所のインデッ…

問題 atcoder.jp 解法その1 numpy + njitを使ったO(N3)解法 なんと、何も考えずに問題通り、総当たりコードを書くとACしてしまうという解法。 マジですか。 AtCoderのPythonではnumpyが使用できるが、njitを使って関数の実行速度を高速化。 実行すると、1731…

問題 atcoder.jp 数学問題。 解法 水の体積が、水筒の半分以下か以上かで処理が異なる。 水の体積が水筒の半分以下のとき 半分以下の時、水は三角柱の形でこぼれる。 水の体積が半分以下 θの角度が求める答え。 水の面積 x / a 水の底辺yの値を求める。三角…

問題 atcoder.jp 解法 K個の石の山に対して、 dp[k] := k個の石からなる山で先手が勝ち状態か(=1なら勝ち状態） というdpを設計。 数が小さい方から、Kまでの石の山をシミュレーションしてdpの数値を埋めていく。 まずはk = 0と非常に単純な状態から調べてい…

問題 atcoder.jp 解法 問題を一見すると 「どの商品に何枚半額割引券を使えばよいか？」 という問題に見える。 だが半額割引券を1枚ずつ使っても結果は変わらない。 なので、 「一番値段が高い商品に1枚ずつ割引券を使う」 という貪欲法で解ける。 あとは、…

問題 atcoder.jp 解法 最小値を計算量低く取り出すデータ管理構造、優先度付きキュー（priority queue）を使うことがポイント。 Pythonではheapqとして提供されている。 全体に対する玉の数の上下はoffset変数を作って管理。 玉を追加する時は、offset値を引…

問題 atcoder.jp 解法 数列A、数列Bが2 x 105なので、A,Bの全要素に対して総当たりだと、2 x 105の2乗なので108越えでTLE確実。 なにか最適化する必要がある。 おそらく二分探索だろうと、検索したところ、そういえばbisectという便利ライブラリがPythonには…