問題 nimのある状態において、その1手で勝利を確定させられるような石の取り方をwinning moveと呼ぶ (ただし例えば(3,2,3)という状態から(1,2,3)と石を取るのと(3,2,1)とするのは別のmoveとする) 以下の条件を全て満たすnimの状態を1個作る ・山の数はn個 (1…

問題 最初キャンディがn個あり、左から昇順に1-nの番号が書かれている キャンディが1つだけになるまで以下の操作を繰り返す 操作: 番号が平方数のキャンディを全て捨て、残ったキャンディにまた左から昇順に番号をつける 最後に残るキャンディは初期状態で何…

問題 h*wのグリッドのいくつかのマスにアヒルがいる (ただし各行[列]にいるアヒルはたかだか1匹) アヒルはコスト1で上下左右に1マス動かせる 全てのアヒルを連続する1行[列]に整列させるためにかかるコストの最小値を求める1 解法 ①まず全てのアヒルを上下移…

問題 タテhヨコwの長方形のいくつかのマスにコインが置いてある 「長方形全体を上下左右方向どれかに1マスぶん動かす」という操作ができ、その際に最初長方形があった領域からはみ出したマスに置いてあったコインは落下して消える 長方形に載ったコインの総…

問題 自然数nを"素数でない自然数"の和で表すとき最小で何個の数が必要か1 解法 nが3のときは3 (1+1+1) そうじゃないときはnが素数なら2 (1 + (n-1)) nが素数じゃないなら1 (n) ∵ nとn-1が両方素数になるのはn=3のときだけだから class MagicDiamonds { publ…

問題 a+bx、c*d^y (01 1 解法 2^40≒10^12だからc*d^yの方はdが2以上ならすぐ全通り試せる a+bxで表せるm以下の数字の個数を(m-a)/b+1で求めてからc*d^yを一個ずつ見ていき、その数がa+bxで表せない数なら答えを+1数字pがa+bxで表せるとき、a+bx = p ∴ x = (p…

問題 各マスに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ポイント持って…

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

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

問題 長さ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…

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

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

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

問題 レストランがn日だけ営業する レストラン利用客は以下のルールを課される 1) 1日1つの料理だけ買える 2) i日目にタイプjの料理を買った場合、i+7日目は同じタイプjの料理しか買えない 3) 何も買わない日があるとその後二度と買えない i日目のタイプjの…

問題 各動物が「自分と同じ動物で、かつ自分より背の高い奴の数」はa[i]であると言っている 各動物はウサギかネコで、全ての動物の身長は異なる 全ての情報と矛盾しないようなウサギ・ネコの当てはめ方は何通りあるか 解法 答えが0通りのケースは以下の2つ1)…

問題 4/7以外の数字を0個か1個含む数をAlmostLuckyNumberと呼ぶ 区間[a,b]にそんな数が何個あるか求める 解法 一瞬で「これは桁dpしかねえ！！」ってなって考えることをやめたんだけどワンチャン全列挙の方が楽？ 実装 dp[i][j][k][L] i: i桁目まで確定して…

問題 全ての桁が4か7の数字をLuckyNumberと呼ぶ 区間[a,b]からまずJohn君が長さalの区間Sを取り出し、次にBrus君がSから長さblの区間Tを取る Tに含まれるLuckyNumberの個数をゲームのスコアとする John君はスコアを最大化、Brus君は最小化しようとするときス…

問題 数字aを文字とみなしたときの全ての(連続とは限らない)subsetの和を9で割った余りを求める 解法 10^k %9 = 1より各桁を独立に考えることができる 全ての桁についてその数(と10^kの積)を含む部分列は2^(n-1)個あるからこれの総和%9を求めればいいex) 123…

問題 n個の箱の左からm番目を開けたいが、Manaoはいま一番左にある箱を開けることしかできない 以下の操作を最小何回行えば目的を達成できるか 1) 箱をp(=nの素因数)分割し、目的の箱を含む区間だけ残し、n/pを新しいnとする 2) 箱の列を1だけ左/右にシフト…

問題 箱の6面に手持ちのステッカーを隣り合う面が異なる色になるように貼れるか判定 解法 ある面とその裏は同じ色でもいい 実装 a: 塗れる面の枚数 同じ色が2個以上あれば+2、1個しかなければ+1 class CubeStickers { public: string isPossible(vector<string> s) {</string>…

問題 足し合わせてnを作るために最小で何個の末尾4/7の数字が必要か求める 解法 4, 4*2, 4*3, 4*4、それらに7を足したもの、7, 4*5 で全ての1の位をカバーできる これらに10kを足したものは構成要素のどれかに10kを足せば要素数を増やさずに作れる ex) 19 = …

問題 n個の街があり街iの人口はa[i] 好きな順で街を合併して新しい街を作り、人口が大きかった方(同じなら好きな方)の名前をつける 最後にまとまる1つの街の名前としてあり得るものの個数を求める 解法 各街の視点に立って、人口が自分以下の街を貪欲に吸収…

問題 与えられた数列の1要素だけ変えて全要素の積と和が同じ値であるようにできるか判定 (1要素は必ず変更しないといけない 何もしないのはダメ) 解法 各要素について条件を満たすような数字が存在するかを二分探索する 解法自体よりコーナーケースとかオー…

問題 H*Wの長方形をN*M個に区切り、そのうちいくつかの部分の面積を知っている 全体の面積を知りたいとき追加で必要な区間の面積の情報の最小値を求める 解法 Rx*Cx, Rx*Cy, Ry*Cx, Ry*Cyのうち3つの面積がわかれば残り1つの面積がわかる これを利用して盤面…

問題 黒と白の玉が入ったスタックを上から順に処理していく 白の玉を取り出したらスタックの上下がひっくり返る 黒の玉を取り出したら中の玉の色が全て反転する 全ての玉を取り出すまでに黒の玉を何度取り出すことになるか計算 解法 実装をする 実装 反転をr…