最大スコア
面白かった！ 問題へのリンク editorials 問題概要 3 つの文字 B, Y, K からなる長さ の文字列 が与えられる。 この文字列をいくつかの区間に分割する。各区間について、 ランレングス圧縮すると、B -> Y -> K の順になるもの：区間の長さだけスコアを獲得 …
いろんな解法がある。ここでは、ソートで解いてみよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 各数列から要素 を選んだときの差 の最小値を求めよ。 制約 考えたこと 本当にいろいろな解き方がある。その中でも易しいのは、…
にょぐた君と一緒に考察した。面白かった。公式解説は多面体で考えているけど、ここでは LP 双対で解いてみる。 問題へのリンク commentary 問題概要 種類の水溶液がある。水溶液 は、 として、 水溶液全体の重さが g 1 g あたりの溶質の重さが g 以上 g 以…
初歩的な Greedy の問題と言える。 問題へのリンク 問題概要 以上 以下の整数からなる数列 であって、 は で割り切れる という条件を満たすものを考える。そのような数列の長さの最大値を求めよ。 制約 考えたこと 基本的には、なるべく小さい値でスタートし…
ビット全探索の練習問題。少し問題内容を理解するのに手こずるかもしれない。 問題へのリンク 問題概要 すでに 個の店が出店している商店街で、新たに店を開こうとしている。 どの店についても 10 個の時間帯があり、それぞれについて open・close を選ぶこ…
ずっと、「2 個分開いているかっこについて、1 個閉じてから、また 1 個開く」というパターンを見落として、WA 12 個がとれなかった！！ 問題へのリンク 問題概要 1 - 20 - 13 + 14 - 5 のような、 個の正の整数を「+」「-」で連結した計算式が与えられる。…
面白かった！ 問題へのリンク 問題概要 英小文字および文字 '?' からなる文字列 が与えられる。 の各 '?' を英小文字に置き換えてできる文字列のうち、次の条件を満たす辞書順最小のものを求めよ。 (条件) 文字列 を連続する部分文字列として含む 制約 考え…
Greedy の本当に初歩の問題といえる。 問題へのリンク 問題概要 整数 1 がある。この整数に対して、以下のいずれかの操作を 回行う。 操作 A：整数値を 2 倍する 操作 B：整数値に を足す 操作後の整数値の最小値を求めよ。 制約 考えたこと 基本的に、「も…
日頃から「まずは全探索！」という意識があれば、この手の問題は全探索でできると気づけるはず！ 問題へのリンク 問題概要 ビーカーに対して、次の 4 種類の操作を好きな順序で好きな回数だけ実行する。 ビーカーに g の水を入れる ビーカーに g の水を入れ…
長さが大きい順に処理していこう！ 問題へのリンク 問題概要 長さが の棒がある。 これらの棒を 4 個選んで長方形を作りたい。作れる長方形の面積の最大値を求めよ。長方形を作れない場合は 0 と答えよ。 制約 考えたこと できるだけ大きい長さの棒を使いた…
ソートの練習！ 問題へのリンク 問題概要 個の整数 から 選んで総和をとる。 総和を取った値の最大値を求めよ。 制約 考えたこと 個の整数 を大きい順に並べておいて、大きい順に 個とって足せばよい。 C++ では、大きい順にソートするのは sort(l.begin(), …
面白い問題。最近はこういうの、あまり見ないかもしれない。 問題へのリンク 問題概要 個の正の整数 が与えられる。 これらからいくつか選んで総和をとる。ただし、その値が 10 の倍数である場合には、その値は 0 になってしまう。 この値の最大値を求めよ。…
ランレングス圧縮！ 問題へのリンク 問題概要 文字 'O', 'X' からなる長さ の文字列 が与えられる。 「'O' のみからなる連続 個の文字をすべて 'X' に書き換える」という操作を最大で何回行えるか？ 制約 考えたこと ランレングス圧縮が有効な問題。ランレン…
意外と整理するのが大変だと思う。map を使って整理しようとするのも自然だが、もうちょっと簡単に解くことを考えよう。 問題へのリンク 問題概要 文字列を投稿すると得点が与えられるコンテストに、 個の文字列 がこの順に投稿され、それぞれ 点が与えられ…
ちょっとした考察が必要になる問題。 問題へのリンク 問題概要 整数からなる数列 が与えられる。数列の各要素に対して「何もしない」「1 を足す」「1 を引く」をしていく。 操作後に、整数値 を選ぶ。 となる の個数の最大値を求めよ。 制約 考えたこと 問題…
区間を伸ばしたり縮めたりしながら、それに伴う「挿入」や「削除」に対処するデータ構造を考える系の問題！ 問題へのリンク 問題概要 数列 について、連続する 個の要素の種類数の最大値を答えよ。 制約 考えたこと 数列の幅 の区間をすべて調べるには、次の…
この問題は、for 文でも解けるし、map でも解ける。ここでは map で解いてみよう。 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 これに対して文字列を考えて、その文字列に対するスコアは ( に含まれている分の個数) - ( に含まれて…
辞書順最小と言われたら......！！ 問題へのリンク 問題概要 文字 'd', 'p' からなる長さ の文字列 が与えられる。 この文字列のある区間をとって、その区間を 180 度回転させる（reverse した上で、'd' と 'p' を入れ替える）。 こうしてできる文字列のうち…
すごく数学的な問題 問題へのリンク 問題概要 縦、横、高さの総和が であるような直方体の体積の最大値を求めよ。 制約 考えたこと 縦、横、高さの長さを としよう。このとき、次の問題になる。 のとき、 の最大値を求めよ この手の問題では、 のとき最大に…
面白い。各値に対する答えを予め整理して求めておく手法は頻出！ 問題へのリンク 問題概要 個の品物がある。品物 は、重さが であり、価値が である。 いくつかの品物を、総和が 以下となるように選ぶとき、選んだ品物の価値の総和の最大値を求めよ。 制約 …
集計処理の応用問題 問題へのリンク 問題概要 一般に、文字列 からいくつかの文字を抜き出して、それを並び替えることによって文字列 を作れるとき、 から を作れるという。 英小文字からなる 個の文字列 が与えられる。 のいずれからも作れる文字列 のうち…
bit 全探索が意外と思い浮かびづらいかもしれない。 問題へのリンク 問題概要 個の正の整数 が与えられる。これらの整数を A, B の 2 グループに分ける。 の最大値を求めよ。 制約 考えたこと bit 全探索を使うと、 個のものに対して「0」「1」の値を割り当…
計算量改善のことを本当に知らないと、TLE に悩むかもしれない。 問題へのリンク 問題概要 長さ の 2 つの数列 、 が与えられる。 1 以上 以下の整数 を選んで、 の最大値を求めよ。 制約 考えたこと 最も素直に考えると、次のように二重 for 文を用いて解き…
一次元 DP で「配る DP」が書きやすい問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 マス目に と記された マスの双六がある。1 からスタートして へ進みたい。 マス からマス () に進むことができて：100pt 獲得 マス からマス () に進むこ…
区間の左端と右端を添字にもちつつ、左端を除去したり右端を除去したりする DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 ブロック がこの順に一列に並んでいて、「左端のブロックまたは右端のブロックを除去する」という操作を 回行って…
LCS を求める DP の練習。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 2 つの文字列 が与えられる。 の部分列でも の部分列でもあるような文字列の長さの最大値を求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; int main() { string S, </bits/stdc++.h>…
ナップサック問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 宝箱には 個の品物が入っている。品物 の重さは 、価値は である。 太郎君は、いくつかの品物を選んで持ち帰りたいと考えている。しかし、彼のナップザックには容量制限があるの…
この時代多く見られた「グルーピング」の問題！ 問題へのリンク 問題概要 S 型ピース 1 個と c 型ピース 2 個を使って、下図のように Scc を 1 個作ることができる。 また、c 型ピース 2 個を使って S 型ピース 1 個を作ることもできる。 今、S 型ピースが …
きちんとした手続きを経て求めたいところ 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。この数列に次の操作を繰り返して、数列の項がすべて相異なるようにしたい。できあがる数列の項数の最大値を求めよ。 【操作】 数列から 3 個の整数を選…
制約が なのがびっくり。素直に連続部分列をすべて調べると TLE してしまう。そのような問題は B 問題で登場するイメージがないので、現代なら などとしそうだ。 問題へのリンク 問題概要 文字列 の連続する部分文字列であって、先頭が 'A' で末尾が 'Z' で…
