けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2020-11-29から1日間の記事一覧

JOI 本選 2014 B - IOI饅頭 (AOJ 0599, 難易度 6)

まさにナップサック問題!!! 問題へのリンク 問題概要 個の饅頭がある。それぞれ 円で売り出そうとしている (全部売るとは限らない)。 饅頭を得るための箱をいくつか購入することにした。箱は 種類あって、 番目の箱は 饅頭を 個まで詰められる 仕入れるの…

JOI 本選 2014 A - JOI紋章 (AOJ 0598, 難易度 6)

ちょっと実装大変だった。差分のみ更新していく系の問題。 問題へのリンク editorial 問題概要 のグリッドがあって、各マスには "J"、"O"、"I" が書かれている。 またこれとは別に、2 × 2 の "J", "O", "I" のパターンが与えられる ( 通りありうる)。 今、与…

Codeforces Round #687 (Div. 1) C. New Game Plus! (R2200)

すごい面白い!! 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…

Codeforces Round #687 (Div. 1) B. XOR-gun (R2000)

こどふぉ特有の、ややギャグ要素ありの楽しい問題。結構好き。 問題へのリンク 問題概要 長さ の正の整数からなる広義単調増加な数列 が与えられる。以下の操作を何度か行うことで、広義単調増加ではない状態にしたい。 数列の隣接する 2 つの要素を選んで、…

Codeforces Round #687 (Div. 1) A. Bouncing Ball (R1400)

個置きに累積和をとるの、3 ヶ月前の僕だったら思いつかなかったかもしれない。 問題へのリンク 問題概要 整数 が与えられる。また、長さ の 0 と 1 のみからなる文字列 が与えられる。文字列 に対して以下の操作を行うことができる。 文字列 中の文字 "0" …

AtCoder ARC 109 C - Large RPS Tournament (緑色, 500 点)

DP でやったけど、もっと楽にできたみたい 問題へのリンク 問題概要 長さ の文字列 と、正の整数 が与えられる。 人がジャンケンのトーナメント戦を行う。 は "R", "P", "S" のみからなる文字列で、"R" はグー、"P" はパー、"S" はチョキを表す。 (0-indexed…

AtCoder ARC 109 B - log (茶色, 400 点)

二分探索でやればよさそう。本当は でもできるのかも。 問題へのリンク 問題概要 正の整数 が与えられる。 整数 のうち、いくつか選んだものが以下の条件を満たすようにしたい。そのような選び方のうち、選ぶ個数の最小値を求めよ。 選んだ整数はいくつかの…

AtCoder ARC 109 A - Hands (灰色, 300 点)

Dijkstra 法をしたけど、同じ殴りなら Warshall--Floyd 法にすればよかった。 問題へのリンク 問題概要 100 階建ての 2 つの建物 A, B がある。 A, B 内では 1 フロア上下するのに 秒を要する A の 階と B の 階とが廊下でつながっていて、移動に 秒を要する…