注意 このブログは、競技プログラミングの問題を解いたログを残しているもので、間違っていたり、証明しているとは限らないものが記載されている可能性があります。記述された情報を利用して発生した問題については、一切責任を負えませんので、自己責任でお…

概要 RECRUIT 日本橋ハーフマラソン 2022夏(AHC013)の参加記です。 atcoder.jp 結果は、16位とよかったですが、結構迷走してました。 問題 サーバルームがグリッドで与えられる。 各マスはサーバか空きマスで、サーバはK種類がそれぞれ100台ずつ存在する。 …

問題 1から10^9まで番号がふられた10^9人が参加する大会があり、この大会では2回コンテストが行われる。 コンテストでは1からNまで番号がついたN問の問題が準備されており、問題iが出題された場合は、L_iからR_iまでの番号の人が正解し、それ以外の人は不正…

問題 1からNまで番号のついたN頂点からなる有向グラフが与えられる。 以下の操作をグラフが空になるまで繰り返すとき、操作回数の期待値を求めよ。 まだ削除されていない頂点を一様ランダムに1つ選び、その頂点および、その頂点から到達可能な頂点をすべて削…

問題 数字列v_iと文字列w_iがNペア与えられる。 数字列v_iの各数字(1文字)は、1からKまでの数字で、それに3文字以下の文字列が割り当てられている。 w_iは、v_iの各数字を割り当てられた文字列にして順番に連結したものになっている。v_iとw_iから、元の数字…

問題 正整数N, Kが与えられる。 以下の条件を全て満たす有理数の多重集合は何種類存在するか、mod 998244353で求めよ。 多重集合の要素数はNで、要素の総和はK 多重集合の要素はすべて、1,1/2,1/4,1/8, ... すわなち、1/2^iのいずれか 制約 1 解法 最初にN個…

問題 非負整数からなる長さNの数列a_iとb_iが与えられる。 今、0 「a'_i = a_{(i+k) mod N} xor x」 のように定める。a'がbと等しくなるような(k, x)のペアを全て求めよ。 制約 1 0 解法 まず、条件をできるだけ数式で考える。 a'はaをkだけローテートしたも…

問題 長さNの整数列A_iと、整数Kが与えられる。 1 (Σ_{L=1}^{N-1} Σ_{R=L+1}^{N} (A_L + A_R)^X ) mod 998244353 を求めよ。 制約 2 1 1 解法 Σ_{L=1}^{N-1} Σ_{R=L+1}^{N}という形は、行列で考えるところの、対角を除く上三角部分の部分に相当する。 これは…

問題 下の階から1～2Nの番号がついた2N階の建物がある。 1階から2N階まで1度だけ動いて、その際、N人の人が乗り降りをした情報と、各階で乗り降りした人は1人のみであることがわかっている。 人iはA_iで乗りB_iで降りたことが記録されており、以下のような条…

問題 N個のセルが並んでおり、1～Nの番号がついていて、すべてのセルが白になっている。 M個のボタンがあり、i番目のボタンを押すと、L_i～R_iのセルの白黒が入れ替わる。 任意の順番で任意の回数ボタンを押すことができるとき、範囲A～Bの部分が黒になって…

問題 整数A, Bが与えられ、Aに対して「正の約数を1つ選び、Aに足す」という操作を120回まで繰り返して、AとBが等しくなるようにしたい。 テストケースがT個与えられる。 各A, Bに対して、加える約数を列挙せよ。 制約 1 1 解法 A,Bが大きいのでまともに約数…

概要 縦H+1マス、横Wマスのマス目がある。 最初、一番上のいずれかのマスからスタートし、右または下に1マスずつ移動していくことを繰り返す。 ただし、上から1以上H以下の縦iマスの左からA_i～B_iマスについては、下に移動することができない。上からi (i=1…

問題 長さNの文字列Sがあり、すべての文字は「1」になっている。 Q回、整数L, Rと数字Dが与えられるのでいかに答えよ。 L番目からR番目の文字をすべてDに書き換え、文字列Sを10進数で書いた整数とみなした値を998,224,353で割ったあまりで表示せよ 制約 1 1 …

問題 整数列A_iと整数Kが与えられる。 以下の条件を満たす数列Bの長さとして考えられる最大値を答えよ。 BはAの(連続とは限らない)部分列 どのBの隣り合う要素の差の絶対値もK以下 制約 1 解法 セグメント木に「その値が最後になる部分列の最長の長さ」をも…

問題 整数Sが与えられる。 すべての項が3以上の整数で総和がSである数列がいくつあるか求めよ。 答えは10^9+7で割ったあまりで求めよ。 制約 1 解法1 dp[i] := 総和がiであるような数列の個数 を考える。i-1以下がわかっていると考えると、dp[i]は、それらの…

問題 N頂点からなる木が与えられる。頂点iには整数a_iが書かれている。すべての頂点について、頂点1から各頂点までの最短経路に出現する整数の列での最長増加部分列(LIS)の長さを求めよ。 制約 2 1 解法 数列における最長増加部分列(LIS)はdp+lower_boundで…

問題 H * Wのグリッドがあり、各マスには、非負整数A_ijが書かれている。 今、2個の整数(r,c)がQ個与えられるので、それぞれについて、その行rと列cを除いた部分の非負整数の積をmod 10^9+7で求めよ。 制約 2 4 0 1 1 1 解法 A_ijが0もあり得ることに注意。0…

問題 T個のテストケースについて、 Pが素数か判定し、素数でなければ-1、素数ならば、A^(P!) mod Pを求めよ。 制約 1 1 1 解法 Pが素数かどうかは、素数テーブルを最初に作っておけばO(1)で求められるのでよい。A^(P!) mod Pは、P! mod PがPが入っているので…

問題 数直線上に、スライムがN匹いて、i番目のスライムは、時刻0で、座標x_i、速さv_i(正の方向)でいる。この数直線上で、同じ座標になる場合は、「衝突」し、以下のようになる。 番号が小さいスライムがその他のスライムをすべて吸収し、吸収されたスライム…

問題 石の山がN個あり、i番目の山にはA_i個の石がある。 2人で「交互に、石の山を一つ選び、そこから1個以上の石を取り除く。先に取り除くことができなか唸ったほうが負け」というゲームを行う。このゲームは、2人が最適に考動する場合、ゲーム開始時にどち…

問題 N頂点N-1辺からなる木が与えられる。 頂点には1からNまで番号がつけられている。整数1 Sを番号がL以上R以下の頂点からなる集合とする 頂点集合Sと両端がSに属する辺からなる部分グラフにおける連結成分の個数をf(L, R)とする このとき、Σ_{L=1}^N Σ_{R=…

問題 N人の社員をいくつかの部門に分ける。 社員iと社員jの間には、信頼度w_ijがあり、部門に分けたときのスコアを「(部門の数)*K - 異なる部門に属する2人の間の信頼度の合計」とする。スコアが最大になるように部門分けをした場合のスコアを返せ。 制約 1 …

問題 現在、各飛行機が(X_i, Y_i)を飛行しており、x,y座標を正か負の方向に進んでいる。 すべての飛行機は秒速0.1で進んでおり、同時刻に同じ座標に来てしまうと衝突してしまう。飛行機の中で、一番早く衝突してしまう飛行機が衝突までの何秒かを求めよ。 衝…

問題 グリッド上に、N個の都市があり、i番目の都市は、(X_i, Y_i)に位置する。また、都市の人工はP_iで与えられる。今、x=0とy=0に鉄道が走っており、x軸またはy軸に平行なK本の鉄道を追加で建設できる。 各都市の人々は、一番近い鉄道まで、グリッドに沿っ…

問題 N日間の株価の1株あたりの金額A_i円がわかっている。 最初、1000円の所持金から、毎日株の売買(所持金や持っている株数までで)が可能な時、最終日の所持金を最大化せよ。 制約 2 100 解法1 No.664 超能力者Aと株価予測 - yukicoder を思い出した。。。…

問題 N個の整数A_iが与えられる。 この中からK個の要素を選び、それらの積が最大になるものを答えよ。 ただし、積は10^9+7で割ったあまりで答えよ。 制約 1 | A_i | 解法 まず、負、0、正に分類し、パターンに分けて考える。「負」の数＋「正」の数がKに足り…

問題 N本の縦棒を横に並べ、上から順にM個の横棒を同じ高さに2本以上入らないようにしてあみだくじを作成する。 i個目の横棒は、a_iとa_i + 1の縦棒を線で結んでいる。さらに、このあみだくじを縦にD段積んだものを考える。 最終的にi番目から入った場合、何…

問題 N人の幼児が一列に並んでいる。左からi番目の幼児の活発度はA_iである。幼児たちを1回だけ任意の順番に並び替えることができ、並び替える前にx番目にいた幼児が並び替え後にy番目になった場合、その幼児のうれしさはA_i * |x-y|になる。うれしさの合計…

問題 文字列Sが与えられる。次の操作をK回繰り返してできる文字列は何通りあるか？ 好きな英小文字1文字を好きな位置に挿入 10^9+7で割ったあまりで答えよ。 制約 1 1 解法 最終的な文字列は、 「? ? ? S[0] ? ? ? S[1] ? ? ? ... S[|S|-1] ? ? ?」 のような…

問題 a～zまでの文字を使って整数Nを表現する。 N=1のときa、N=26のときz、N=27のときaa、N=702のときzzのように、Nを1増やすたびに一番最後の文字が zでない場合はインクリメント zの場合は、一つ前の文字をインクリメントしてaに戻す ようなことを繰り返し…