問題原文 atcoder.jp 問題要旨 か？ 解法 絵に書いたような地獄絵図を生んだ問題。反省のために書く。 基本的にはやるだけだけど、テストケースがほぼ完璧に誤差を潰してくる。 なので、式変形して根号の部分をつぶしていく。 まず、入力が必ず正の整数なの…

問題原文 atcoder.jp 問題要旨 頂点の木がある。以下の条件を満たすよう、各頂点に１から までの数を当てはめよ。 距離が３である頂点のペアに書かれている数の和もしくは積が３の倍数 解法 超絶怒涛の神良問（解けなかったけど） 。 3, 6, 9などはどれとで…

問題原文 atcoder.jp 問題要旨 長さ の文字列 がある。 以下の種類がある 個のクエリを処理せよ。 文字目を に変える 番目から 番目まで（両端含む）に、何種類文字があるかを答える は英子文字からなる 解法 こういうのは、ある場所までに文字がどのぐらい…

問題原文 atcoder.jp 問題要旨 あまりにもめんどうなので書きません（） 解法 くそくそくそくそくそくそめんどくさ実装！！！！！w 方針を間違えると大事故を起こしそう。 方針としては、 1 の6方向について、(6 - 1の数)分外周に必要とする ここから、外か…

問題原文 https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/2011-ho.pdf#page=4 問題要旨 冊の本のうち、 冊を売ることを考える。 番目の本の買取価格は である。 また、本には10種類のジャンルがあって、同じジャンルの本をまとめて 冊売ると、１冊あた…

問題原文 https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf#page=7 問題要旨 本のつららが横一列に並んでいる。 番目のつららの長さは である。 つららは、両隣のつららよりも自身が長い時 に、毎秒１cmずつ伸び、 cmになると折れる。（折…

問題原文 atcoder.jp 問題要旨 英子文字からなる があり、これに対しての操作クエリが 個与えられる。 クエリには２種類ある。 反転クエリ: 現状の を反転する 文字追加クエリ: の (先頭: / 末尾: ) に 英子文字 を追加する 個のクエリを処理したあとに出来…

問題原文 atcoder.jp 問題要旨 縦 マス、横 マスのグリッドがある。 左上からスタートして、右か下への移動を繰り返して一番右下のマスを目指す。 曲がった直後に曲がることはできない という制約があるとき、一番右下のマスへたどりつく通り数はいくつある…

問題原文 https://www.ioi-jp.org/joi/2008/2009-ho-prob_and_sol/2009-ho.pdf#page=4 問題要旨 長さ の円環上に 個の店舗がある。（入力で与えられるのは 個で、店舗０は座標０にある） また注文が 個きており、円環状の宅配場所が与えられる。 各注文につ…

問題原文 atcoder.jp 問題要旨 個のぷよが縦に並んでいる。ぷよは同色が４つ以上連なると消える。 あるぷよの塊が消えると、その上にいたぷよたちは下に移動し、そのあとも消える条件を満たすのであれば連鎖的に消える。 あるぷよの１つの色を変更することで…

問題原文 atcoder.jp 問題要旨 SNSの友達関係・ブロック関係が無向グラフの形で与えられる。（友達関係の数は 個、ブロック関係の数は 個である） ある人 について、友達関係のみを辿ってたどり着ける かつ その人とはブロック関係にない、という時、その人…

問題原文 atcoder.jp 問題要旨 を超えないように 個の整数 の中から重複を許して ０個以上４個以下選ぶ時、その和とし取りうる最大値は何か？ 解法 整数を２つ選んだ場合の和のリストをあらかじめ計算しておく。（これを とする。） すると、 ある について…

問題原文 atcoder.jp 問題要旨 × のグリッドがあり、各セルは １ か ０ かである。 ある行を好きなだけ選び、その行の１と０を反転 → ある列を好きなだけ選び、その列の１と０を反転 という操作を１回行う。 操作後のグリッド上の ０と書かれたセルの数を最…

問題原文 https://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day1_20.pdf 問題要旨 × のグリッドで表現される広い土地がある。 各土地の値段は であり、その１セルの土地の価格を表す。ただし、−１であれば人が住んでいることを表す。 この土地のうち…

問題原文 atcoder.jp 問題要旨 個の整数がある。 これらの整数のペアは、 通り考えられるが、それぞれのペアについて積を求め、小さい順に並び替えた時 番目にくる数は何か？ 解法 atcoder.jp こいつの上位互換問題。。。どう考えても令和ABC-Dの難易度じゃ…

問題原文 atcoder.jp 問題要旨 区別可能な 個の部屋があり、最初各部屋には人が１人いる。 この最初の状態から、「ある人が今いる部屋から別の部屋に移動する」という操作が 回行われた時、各部屋にいる人数の組み合わせとしてありうるものは何通りあるか？ …

問題原文 atcoder.jp 問題要旨 本の区別可能な花から、１つ以上を選んで花束をつくる。 ただし、 , あるいは と一致する本数を選ぶことはできない。 作りうる花束の種類数を求めよ。ただしそのような物が無い場合には 0 とせよ。 解法 逆元コンビネーション…

問題原文 atcoder.jp 問題要旨 縦 、横 マスのグリッドが与えられる。各マスには二つの数字、 と、 が設定されている。 一番左上のマスから、「右に移動」「下に移動」を繰り返して、一番右下のマスを目指す。 あるマスを通った時、そこに書かれている数字の…

問題原文 atcoder.jp 問題要旨 のグリッドがある。このグリッドに区別のつかない 個のコマを、各マスにつき最大１つ配置する。 また 個のコマの、ある配置の仕方についてのコストを、 と定める。 全ての配置の仕方についてのコストの総和を求めよ。ただし配…

問題原文 atcoder.jp 問題要旨 数直線と見なすことのできる道路がある。 この道路で 回工事が行われる。工事 は、時刻 [S_i - 0.5] から 時刻 [T_i - 0.5] まで座標 を通行不能にする。 また 人の人がいる。人 は時刻 に座標0から数直線を出発し、時速1で右…

問題原文 atcoder.jp 問題要旨 長さ の整数列 がある。「ある数に +１し、ある数に-１する」という操作を 回以下行ってできる の全ての数を割り切るような数のうち 、最大のものは何か？ただし操作の途中で要素の値が負になってもよい。 解法 答えの候補を絞…

問題原文 atcoder.jp 問題要旨 人のゲストがいる。 番目のゲストの幸せパワーは である。 これらのゲストからある人の右手とある人の左手を選んで握手させるという操作を 回行う 。ゲスト とゲスト が握手した時、全体の幸せ度は 増える。（最初、全体の幸せ…

問題原文 atcoder.jp 問題要旨 1以上 以下の整数であって、10進法で表した時に、0でない数字がちょうど 個あるようなものの個数を求めよ。 解法１：がんばる が高々３通りしか無い and 制約が小さい ので、頑張ればできます。 実装を見た方がいいと思うので…

問題原文 atcoder.jp 問題要旨 人の選手が以下のルールで総当たりで試合を行う。 １日に最大１試合を行う。 各選手について、試合を行う順番が[tex: A{i1}, A{i2}...] のような形で決められており、この順番でしか試合を行えない。 ルールに基づいた上で、最…

問題原文 atcoder.jp 問題要旨 非負整数からなる組 であって、以下の条件を満たすものの通り数を求めよ。 == 解法 ここから出てくる1111~とかは全部２進数です。 制約が桁dpをしろと言っている。。。 こういう場合には、「以下であることがまだ未確定にdpテ…

問題原文 atcoder.jp 問題要旨 文字列 と文字列 が与えられる。 を 回繰り返した文字列において、何文字目までを使えば部分文字列として と同じものをとりうるか？ どう頑張っても取り得ない場合は -1 を出力せよ。 は英子文字からなる。 解法 まず、 にあっ…

問題原文 atcoder.jp 問題要旨 長さ の文字列 が与えられる。 の連続する部分文字列であって、２回以上出現しているもの（ただしそれらの区間は重なりあってはいけない）ものの、最大の長さを求めよ。 解法１：Z-algorithmで殴る Z-algorithm を使って、 の…

問題原文 atcoder.jp 問題要旨 サイコロが 個ある。サイコロ の出目は、１から まであり、それぞれの目が等確率で出る。 隣接する 個のサイコロを選んで独立に振ったとき、出る目の合計の期待値の最大値を求めよ。 解法 それぞれのサイコロの出目は独立に決…

問題原文 atcoder.jp 問題要旨 頂点１から頂点 まで移動できることが保証される、 頂点 辺の有向グラフが与えられる。 このグラフ上で、頂点１から頂点 まで移動するゲームを考える。 プレイヤーは１秒につき一回移動でき、各辺を通るごとに何度でも 点を得…

問題原文 atcoder.jp 問題要旨 長さ の整数列を塗り分けることを考える。 同じ色で塗られたものからなる数列が狭義単調増加数列になっているようにするためには、最低何色で塗る必要があるか？ 解法 例えば、すでに２種類の色を使っていて、それぞれの現状の…