2020-11-29から1日間の記事一覧
まさにナップサック問題!!! 問題へのリンク 問題概要 個の饅頭がある。それぞれ 円で売り出そうとしている (全部売るとは限らない)。 饅頭を得るための箱をいくつか購入することにした。箱は 種類あって、 番目の箱は 饅頭を 個まで詰められる 仕入れるの…
ちょっと実装大変だった。差分のみ更新していく系の問題。 問題へのリンク editorial 問題概要 のグリッドがあって、各マスには "J"、"O"、"I" が書かれている。 またこれとは別に、2 × 2 の "J", "O", "I" のパターンが与えられる ( 通りありうる)。 今、与…
すごい面白い!! 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…
こどふぉ特有の、ややギャグ要素ありの楽しい問題。結構好き。 問題へのリンク 問題概要 長さ の正の整数からなる広義単調増加な数列 が与えられる。以下の操作を何度か行うことで、広義単調増加ではない状態にしたい。 数列の隣接する 2 つの要素を選んで、…
個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …
DP でやったけど、もっと楽にできたみたい 問題へのリンク 問題概要 長さ の文字列 と、正の整数 が与えられる。 人がジャンケンのトーナメント戦を行う。 は "R", "P", "S" のみからなる文字列で、"R" はグー、"P" はパー、"S" はチョキを表す。 (0-indexed…
二分探索でやればよさそう。本当は でもできるのかも。 問題へのリンク 問題概要 正の整数 が与えられる。 整数 のうち、いくつか選んだものが以下の条件を満たすようにしたい。そのような選び方のうち、選ぶ個数の最小値を求めよ。 選んだ整数はいくつかの…
Dijkstra 法をしたけど、同じ殴りなら Warshall--Floyd 法にすればよかった。 問題へのリンク 問題概要 100 階建ての 2 つの建物 A, B がある。 A, B 内では 1 フロア上下するのに 秒を要する A の 階と B の 階とが廊下でつながっていて、移動に 秒を要する…