2022-04-01から1ヶ月間の記事一覧
DPの問題.前日の情報をどうするか,そこがカギとなります. atcoder.jp 問題の説明 温度条件が度の下で日服を選んだ場合の派手さの差の絶対値の合計の最大値を求めよ. 条件 考えた事 派手さの差の絶対値の合計を考える.つまり前の情報を遷移させる必然性を伺わ…
DPの問題.ナップサック問題+α.スクリーンショットの重要度ってなんやねん. atcoder.jp 問題の説明 枚数が枚,幅がに収まる条件の下で画像を選ぶときの重要度の合計の最大値を求めよ. 条件 考えた事 枚数制限がない場合,これは典型的なナップサック問題と呼ば…
いよいよDP.最初は優しめの問題から. atcoder.jp 問題の説明 高橋君が回または段のジャンプを行います.回のジャンプの後ににいる可能性があるか答えなさい. 条件 入力は全て整数. 考えた事 まず,DPとは何をする手法なのか.端的に言えば値を記憶する配列を作…
Greedyの問題.どうマッチングさせると仲良しさんが作られるか. atcoder.jp 問題の説明 赤い点の外側にある青い点を結ぶことで作る事の出来るペアの個数の最大値を求めよ. ただしでかつのとき,はの外側にあるという. 条件 赤い点と青い点の座標,座標は全て相…
Greedyはブログにまとめてなかったなと思ったので.ゴミ屋敷の住人必見!? atcoder.jp 問題の説明 高橋君が個の箱を積み上げる時に出来る箱の山の最小個数を求めなさい.箱にはその重さ以下の箱を重ねる事ができる. 条件 考えた事 Greedyの基本は「その場での…
0-1BFSの問題.障害は多い方が燃えるよね. 問題のリンク 問題の説明 高橋君はの迷路を移動する.高橋君は2回まで障害物を乗り越えられるものとして,ゴールに辿り着けるかを判定せよ. 条件 考えた事 迷路の基本的な実装は, garakutagoya.hatenablog.com BFSにつ…