問題はこちら atcoder.jp 回じゃんけんを行う。買った場合、以下のように点が与えられる。 グーで勝った時、 点 チョキで勝った時、 点 パーで勝った時、 点 ただし、ちょうど 回前に出した手と同じ手は出せない。 相手の出す手が事前に全て文字列 で与えら…

問題はこちら atcoder.jp 長さ の正整数列 に対して、その部分集合 を考える。その部分集合に含まれる部分集合 の和が になるようなものの個数を求めよ。 考え方 集合単位でDPをしていくことを考える。部分集合に含まれる部分集合という考えが少し難しいが、…

問題はこちら leetcode.com 二つの配列 nums1 と nums2 が与えられる。同じ長さの空でない部分列を nums1, nums2 から順序を変えずに選んだ時の内積の最大値を求めよ。 考え方 DPの典型問題（解けませんでしたが... ） LCSと関わりが深いので、こちらの記事…

問題はこちら atcoder.jp マス に二つの数 が書かれている．一回の移動で または に移動する．マス から に移動しながら，数の片方を選び に．もう片方を に追加する．移動する経路を とする時，以下の値を偏りと呼ぶ． 数を自由に選びながら移動した時の，…

問題はこちら atcoder.jp 個の点がある。その点に対して、以下のように回の操作を行い、辺を追加する。 となる頂点と頂点 の間にコストの辺を追加する。 最終的な頂点からまでの最短距離を求めよ。 以降は0-indexとして話を進める。 解法1 - seg木でdp が与…

問題はこちら 考え方 解答 別解 問題はこちら atcoder.jp までの箱がある。 個目の鍵のコストは であり、 種類の箱を開けることができる。全ての箱を開けるために必要な費用の最小値を答えよ。不可能な場合は を出力せよ。 考え方 まず、これは割と複雑な遷…

Common Subsequence 問題はこちら atcoder.jp この問題はLCS(Longest common subsequence)と関わりが深いのでまずはそれから書いてみる。 LCS 最長の共通部分列の長さを求めてくださいというのが典型的な問題。次のような例を考えてみる。 s: abcd t: acfed …

Beautiful Array 問題はこちら codeforces.com 自分が気づいたところ まず最初に，xが負の時は最小区間和を選んできてそれをx倍する．xが正の時は最大区間和を選んできてそれをx倍する．とすれば最大値が求まると考えた．ここでセグ木とかをググり始める... …

Static Sushi 問題はこちら atcoder.jp 自分が気づいたところ 最大でも反対方向に向きを変える動きは一回だけなので，反転する場所を一つ決めてそこから反転した後の最大値を求めることを考えた． これだと，計算量は反転する場所が ，反転後の最大値探索が…