問題原文 atcoder.jp 問題要旨 の 個の数字が与えられる。 この中から 個以上の数を選ぶ時、その和としてありうるものの個数を求めよ。 解法 不要なものを頑張って引こうとすると地獄をみるよ！ こう言うのはちゃんと特殊な条件（今回だと 10^{100} とかいう…
問題原文 https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf 問題要旨 × のグリッドが与えられる。各グリッドの値は 0, 1, 2 のいずれかである。 このグリッドから面積４マス以上の四角形領域を抜き出した時、４つの角にあたるグリッドの値…
問題原文 https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day4.pdf 問題要旨 人の選手からなる競プロの大会を考える。 大会では0点から100点までの点を取得できる問題が 問あり、 問が終了した時点での各選手の得点は 点である。 また金メダルを取…
問題原文 atcoder.jp 問題要旨 J, O, I からなる長さ の文字列 が与えられる。 の連続する部分列であって、その中に含まれる J の数、 O の数、 I の数 が等しいようなもののうち、その最大の長さを求めよ。 解法 なら累積和 + 始点終点全探索で終わり。。。…
問題原文 atcoder.jp 問題要旨 長さ の整数列 の中から、隣り合う部分を選ばないように 個選ぶ。 選んだ要素の総和を最大化せよ。 解法 番目までみて 個選んでいる場合の最大値 がぱっと思い浮かぶが、これは になので間に合わない。 少し考えると、「８番目…
問題原文 atcoder.jp 問題要旨 １以上 以下の整数からなる長さ の数列 を考える。 考えうる数列 通り全てについて、 を計算し、その総和を求めよ。 解法 まともには到底計算できないので、 「gcdが になるようなものは何通りあるか？」 を考える。 まずgcdが…
問題原文 atcoder.jp 問題要旨 R, G, B のみからなる長さ の文字列 が与えられる。 であって、 , , が全て異なり、 であるようなものの通り数を求めよ。 解法 全体からカウントしてはいけないものを取り除く 方針を取る。 まず答え全体は明らかに、 (Rの数) …
問題原文 atcoder.jp 問題要旨 個のオレンジが横１列に並んでいる。 番目のオレンジの大きさは である。 このオレンジの列をいくつかの区間に分割し、箱詰めすることを考える。箱には最大で 個のオレンジがあり、１つにつき のコストがかかる。また、ある箱…
問題原文 atcoder.jp 問題要旨 長さ の正整数列 がある。また、 個の１より大きい整数 が与えられる。 にした場合の以下の問題の答えを求めよ。 始め整数 がある。 の順番に、 を で置き換える。 途中で となる場合はそうなる最小の を、ならない場合は最終…
問題原文 atcoder.jp 問題要旨 分された丸いケーキがある。時計回りに 番目のピースの大きさは である。 以下の操作を繰り返すことで、JOIくんとIOIちゃんでケーキを分け合う。 最初に、JOIくんが好きな位置のピースを１つ取る。 IOIちゃんが両端のピースの…
問題原文 atcoder.jp 問題要旨 正整数 が与えられる。２以上 以下の整数 を決めて、 となるまで以下の操作を繰り返す。 なら、 で置き換える。そうでないなら、 で置き換える。 最終的に が１になるような はいくつあるか？ 解法 本番は実験の結果通してしま…
問題原文 atcoder.jp 問題要旨 匹のスライムが横１列に並んでいる。 番目のスライムの大きさは である。 スライムが１匹になるまで以下の操作を繰り返す。 隣り合うスライムをくっつけて１匹のスライムにする。このとき、くっつける前のスライムの大きさをそ…
問題原文 atcoder.jp 問題要旨 明日から 日間のうち、 日間を選んで働く。 ただし、 x がつけられた日と、最後に働いてから 日間は働けない。 日働くために必ず働かなければいけない日を全て求めよ。 解法 まず問題を簡単にして、「できるだけ多く働くには？…
問題原文 atcoder.jp 問題要旨 10進表記において、隣り合う各桁の差の絶対値が１以下であるようなものを「ルンルン数」と呼ぶことにする。 番目のルンルン数を求めよ。 解法 sample3が、 のときに3234566667だと言ってるので、最大でも10桁だということがわ…
問題原文 https://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day1_20.pdf 問題要旨 段の階段があり、 段目の高さは mmである。 また、段差の和が mm 以下であれば１歩で登ることができる。 段の階段を上りきる通り数を求めよ。また、用いた段が同じ時…
問題原文 https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day2_21.pdf 問題要旨 日間、毎日 個の商品の中から１つを選んで購入する。 各商品の値段は毎日変動する。また、同じ商品を２日連続で買うと１割引で買え、３日以上連続で買うと３割引…
問題原文 https://www.ioi-jp.org/joi/2011/2012-ho-prob_and_sol/2012-ho.pdf#page=7 問題要旨 祭りは時刻０から時刻 まで行われる祭りにおいて、 つの夜店からいくつかを選んで、順番通りに遊ぶことを考える。 夜店 の楽しさは で、遊ぶのに かかる。出来…
問題原文 https://imoz.jp/data/joi/2013-sp-d1-joi_poster.pdf 問題要旨 縦 , 横 のポスター上に 個の点が並んでいる。 これらのうち異なるものを４つ選び、それぞれa, b, c, d とするとき、以下の条件を満たすようなものはいくつあるか？ a を中心とし、b…
問題原文 https://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day3_23.pdf 問題要旨 文字列 が与えられる。 の全てのアナグラムのうち、 は辞書順で何番目か？ ただし、 も のアナグラムとする。 解法 全通り並べることはできないので、うまく数える必…
問題原文 atcoder.jp 問題要旨 個の赤いリンゴ、 個の緑のリンゴ、 個の無色のリンゴがある。 それぞれの美味しさは、 , , である。 また、 個の赤いリンゴ、 個の緑のリンゴを食べることを考える。 食べるリンゴの美味しさの合計を最大化せよ。ただし、無色…
問題原文 atcoder.jp 問題要旨 頂点の直線状のグラフがあり、 辺 は頂点 と 頂点 をつないでいる。 またバイパスが張られていて、 頂点 と頂点 をつないでいる。 について 最短距離が となるような の通り数を求めよ。 解法 各 の組み合わせを全探索すること…
問題原文 atcoder.jp 問題要旨 縦 マス、横 マスのチョコレートがある。 各マスは 0 か 1 で、 0は普通のチョコだが、 1 はホワイトチョコである。 マスの境界に沿った直線によってグリッド全体の端から端までチョコレートを割る時、各ブロックに含まれるホ…
問題原文 atcoder.jp 問題要旨 種類のネクタイと、 人の社員がいる。 各ネクタイの長さは であり、 各社員が最初につけているネクタイの長さは である。 について、以下の問に答えよ。 番目のネクタイを除いた 種類のネクタイを、各社員に１人１本ずつ割り当…
問題原文 D - Banned K 問題要旨 ボールが 個あり、 番目のボールには が書かれている。 について、以下の問題を解け。 番目のボールを除いた 個のボールから、書かれている整数が同じような異なる２つのボールを選ぶ方法はいくつか？ただし、選ぶ順番は考慮…
問題原文 atcoder.jp 問題要旨 日本列島は横長い島であり、地点 の高さは である。 また海面の高さは０であり、海面より高い部分を陸地、陸地が１つ以上連続している区間を島と呼ぶ。 海面が徐々に高くなっていくと、島の数が増減し、最終的には０になる（日…
問題原文 atcoder.jp 問題要旨 海から陸に向かって風が吹く。海から家までには 個地点があり、その標高は である。（ただし海も１つの地点として、 = 0 として与えられる） 温度0から始め、高度の変化に応じて温度が変化する。 のとき: 標高が１上がるごとに…
問題原文 atcoder.jp 問題要旨 長さ の J, O, I からなる文字列 が与えられる。 文字列のある１箇所に J, O, I の文字を差し込むことで、変化後の文字列 に含まれる JOI という部分文字列のとりかたの通り数を最大化せよ。 解法 基本はdp。 文字目までみたと…
問題原文 atcoder.jp 問題要旨 一直線上に伸びる数直線上に、 人の人がいる。 番目の人の位置は である。 人は始め右か左を向いており、１秒にあたり距離１だけ移動する。ただし他の人と出会った場合にはその場で停止する。 秒後の、 番目、 番目という形で…
問題原文 atcoder.jp 問題要旨 価値がそれぞれ であるような饅頭が、 個と、饅頭を入れるための箱が 個ある。 番目の箱は、饅頭を [C_j] 個入れられるが、コストが かかる。 箱に詰めた饅頭の価値の総和 - 箱のコストを最大化せよ。 解法 饅頭は明らかに価値…
問題原文 atcoder.jp 問題要旨 J, O, I で構成される 縦 マス、横 マスの大グリッドに、2×2の同じく J, O, I で構成される小グリッドを重ねることを考える。 大グリッドの１マスを好きな文字に変更してよいとき（変えなくてもよい）、大グリッドの全ての2×2…
