問題 頂点数がnで全てのi=1,2,...,nについて頂点iと最も遠い頂点の距離がa[i]となるような木が作れるか判定 解法 ↓木が作れる場合の作り方 まずk = max(a,a+n)とし、直径kの一直線な木を作る(写真の青色部分) それで余った頂点iは、最も遠い頂点との距離がa[…

今年大学があまりにも辛くて全然やれてない もう青になってから半年近く経ってるんですが・・ 他人にとって参考になる情報が少なそうだから書く気なかったけど一応残しておく結論から言うと、 ○AtCoder/CF/CSAのratedコンテストにほぼ全て出る ○↑で解けなか…

問題 n頂点m辺の重み付き無向グラフと整数xが与えられる このグラフの各辺を白or黒で塗る方法で、以下の条件を満たすものの個数を求める 条件: 白く塗られた辺と黒く塗られた辺をともに含む全域木が存在し、そのような全域木のうち最も重みが小さいものの重…

問題 長さnの数列aが与えられる この数列の全ての連続する部分列の中央値を並べ、新しい数列mを作る 数列mの中央値を求める1 1 解法 (思考) 各要素が中央値になるような区間が何個あるかわかると嬉しい →値aが中央値になるような区間っていうのは、(区間に含…

問題 長さnの数列が与えられる これを以下の操作を繰り返して単調増加に並べたい 操作1) 連続する2要素を選び反転する 操作2) 連続する3要素を選び反転する 後者は何度でもしていいとき、前者を最小で何回行う必要があるか求める1 解法 まず操作2だけでソー…

問題 n頂点の木が与えられる この木の直径をk以下にするために削除する必要のある頂点数の最小値を求める2 解法 木の直径をDとすると、 Dが偶数のとき) ある頂点vが存在し、vから他の頂点への距離がD/2以下となる Dが奇数のとき) ある辺eが存在し、eから他の…

問題 "ABC?" の4文字のみからなる文字列sが与えられる この文字列が '?' をq個含むとき、それらの '?' を "ABC" のいずれかに置き換えることで3^q個の文字列が作られる それぞれの文字列に含まれるABC数の和を求める (ABC数: 文字列から3文字抜き取って左か…

問題 n個の都市とm本の列車があり、i本目の電車は区間[li, ri]を走っている 各クエリで[l,r]に「走る区間が完全に含まれる」ような列車の本数を出力するn 解法 区間[l,r]を走る列車について考える これを二次元平面上の (y座標,x座標) = (l,r) の点とみなす…

問題 各マスにAかBと書かれた1列のボードがある AliceとBobが順番に「まだコインが置かれていない任意の連続する区間にコインを置く」という操作を繰り返す ただしこの操作で全マスをコインで埋めてはいけない コインが置かれていないマスが1マスだけ残った…

問題 以下のどれかを満たす文字列を良い括弧列と定義する 1) 空文字列 2) ある良い括弧列を()で囲んだもの 3) 2つの良い括弧列を並べて繋げたもの 与えられる文字列sを良い括弧列にするために追加する必要のある括弧の最小値を求める 解法 sを左から見ていき…

問題 今回のSRMは75分で3問あり、i問目はp[i]点満点で、現在の実力では開いてからs[i]分かければ確実に解ける 問題を開いてからt秒後に提出した場合に貰える得点は以下の通り 1問目: p[0]-2t 2問目: p[1]-4t 3問目: p[2]-8t また最初にluckをlポイント持って…

問題 白いマスが横一列に無限個並んでいる クエリがn個与えられ、i番目のクエリでは以下の操作を行った後に駒が置かれている位置を出力する 1) マスa[i]に駒を置き、カウンタを0に初期化する 2) 駒のあるマスが白ならそのマスを黒に塗ってカウンタを1増加さ…

問題 n両編成の電車にm人の整備士が乗っており、最初i人目の整備士はa[i]両目にいる 各整備士は1分で隣の車両に移動することができ、今いる車両を一瞬で点検できる 全ての車両を少なくとも1人の整備士が点検するには最短何分かかるか n 解法 i人目の整備士が…

問題 最初(sx,sy)にいる 1マス移動するのには1秒かかる また3つのテレポート装置のペア(∴ 計6点)があり、それらを使うと片方の点から対応するもう片方の点に10秒で飛べる (gx,gy)まで最短で何秒で行けるか0 解法 始点・終点・テレポート装置6点の計8頂点でグ…

問題 64枚のカードがあり、i番目のカードの片面には2^i個の点が書いてある 裏は真っ白 a 各操作では目的達成に必要な最小枚数しかひっくり返さず、複数枚ひっくり返す必要があるときは、書いてある点が多いカードから順にひっくり返す ある瞬間に見えている…

問題 n個の街とm本の無向辺があり、これらの街を2つの州に分けたい ただし同じ州内のどの2つの都市も直接道で結ばれているように分けないといけない そういうふうに分けたときの、"両端の都市が同じ州内に属しているような道"の本数の最小値を求める 解法 条…

問題 長さnの数列に対し「長さkの区間を選び、その中の最小の要素を取り除く」という操作をq回行う 取り除いた要素の最大値をx、最小値をyとしてx-yの最小値を求める 解法 最小値を決め打ちして最大値を最小化する方針 最小値をyにするには、y未満の数字を含…

問題 1〜nが重複なく書かれた白/黒のボールが各n個ずつ計2n個一列に並べられている 「隣り合う2つのボールをswapする」という操作を繰り返して、「任意のペアi,j (i＜j)について、iと書かれた黒/白のボールがjと書かれた同色のボールより左にある」という状…

問題 長さnの数列aに対して「好きな要素を1減らす」という操作を行い、[1,n-2]の任意のiで a[i-1]+a[i+1] 最低何回操作が必要か求める 解法 両端は操作しても損しかしないから考えなくていい 1 a[i]で条件を満たすように減らすと今度はa[i-1]で条件を満たさ…

問題 文字列sの連続とは限らない部分文字列の中で辞書順最大のものを求める 実装 sを後ろから見ていって、今まで見た中で最大の文字以上の文字を見つけるたびに追加していき、最後に反転 class LargestSubsequence { public: string getLargest(string s) { …

問題 数字nが書かれたボールを殴ると、nが合成数であるとき、dとn/dが書かれた2つのボールに分裂する(d:ランダムなnの約数) 合成数でないときは何も起こらない 何度でもボールを殴れるとき、数字tが書かれたボールを必ず作ることができるかを判定 解法 t=nな…

問題 cypher textリストに載っている任意の数字cについて「plain textリストのどれかの数字pを暗号化キーXでxorするとcになる」が成り立つようなキーの数を求める 解法 条件は「各cとXのxorは必ずplain textリストに載っている」と言い換えられる 各cypher t…

問題 n行m列の行列がある i行目[j列目]の要素全てのxorが各i,jで与えられる これに矛盾しない行列が存在するか判定し、存在するなら1個示す 解法 ↓みたいにすればa[n-1], b[m-1]以外は全て矛盾しない n-1行m-1列の数字をXとおくと、Xは X = a[n-1] ^ (b[0] ^…

問題 2行n列の畑があり、マスごとに毎秒生えるキノコの本数が決まっている 最初vasyaは1行1列にいて、キノコは畑全体に1本も生えていない 1マス移動するのには1秒かかる 全マスをちょうど1回ずつ通り、通る時にそのマスに生えているキノコを全て収穫するとき…

問題 H行W列のマス目の各マスに英小文字が書かれている 任意の異なる2行/列をswapするという操作を何度でも行えるとき、マス目が点対称になるようにできるか判定 H,W 解法 行のswapと列のswapは可換 行のswapの仕方が決まっているとき、列をうまくswapして条…

問題 ある目盛りから見て時針がh度、分針がm度を指している時計がある しかし時計が真ん丸なのでどの目盛りが0時なのかわからない あり得る時間として最小のものを求める (存在しない場合は空文字列を返す) 解法 12個の目盛りを全て0時にしてみて、矛盾しな…

問題 与えられるリストに載っている任意の数字nについて「x/y方向に±n、y/x方向に±1進む」という操作を何度でもできるとき、(0,0)から(x,y)に辿り着けるか判定 解法 リストに偶数が含まれていればどのマスでも行けるから無条件にYES 奇数しかなければi+jが偶…

問題 2次元平面に横長の板がn枚浮いていて、それぞれ高さが違う 板は1刻みで横に動かせる 動かせる範囲の上限はある いくつかのボールがいろいろなx座標に落とされるとき、全てのボールが地面に落ちるようにする板の配置は何通りあるか 解法 前準備として、…