問題 レストランが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 = …

問題 Ethanは「各頂点に数字が割り振られている木を与えられ、通る頂点の数字をpre-order travesal(通りがけ順)に並べた数列を作る」という課題を与えられた しかし間違えてpost-order traversal(帰りがけ順)の数列を作るアルゴリズムを作ってしまった1) Eth…

問題 タテ3マス・ヨコwマスのグリッドに左上から入り右下から出たい 道は90度曲がったパイプを繋げて作る パイプは回転できる パイプの繋ぎ方は何通りあるか数える 解法 タテが3マスしかない => 左に戻ることができない (戻ろうとすると必ずパイプが衝突する…

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

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

問題 一直線にN個の島がN-1本の橋で繋がっている 島a[i]とb[i]を行き来できなくしてほしい、という形の要望M個を全て叶えるために取り除く必要のある橋の本数の最小値を求める 解法 クエリをa[i]の降順に見ていき、取り除いた橋の中で一番左の橋の番号rを保…

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

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

問題 重複しない数字が書かれたn枚のカードがある kが書かれたカードを取り除くとk-1, k+1が書かれたカードも消える 最大で何枚のカードを手で取り除けるか 解法 ソートして端から取り除くのが最善 (端以外から取り除くと1回で最大3枚消えるが端から順だと最…

問題 パンが数種類あり、各パンが固有の値Xを持ち、焼き時間がX未満のものをundertoasted、X超過のものをovertoastedと呼ぶ underのパンとoverのパンがいくつかあり、それらの焼き時間のリストが与えられる このリストに含まれるパンの種類数の最小値を求め…

問題 [000000000,999999999]の10^9個の数字のうちどれか1つが書いてある宝くじを1枚適当に買う 与えられるvectorのうち1個以上のstringが買った番号のsuffixになっていれば当選する 当選する確率を求める 解法 例えば"1234" と "34"が与えられたら後者が前者…

問題 0から始めて「xを足す」「yをかける」という操作を各a/b回好きな順番で行う 最後に得られる値の最大値を求める 解法 求める値は (((x+x+..+x)*y +x+..+x)*y +x+...+x)*y +... = x(y^k1 + y^k2 + ... + y^ka) (b>=k1>=k2>=...>=ka) こういう形になる yを…

問題 n人いてそのうち何人かは追い出したい人を決めている 最初は全員vulnerableな状態から始まり、以下の流れを繰り返す 1) 追い出したい人を決めている人たちは対象がvulnerableならそいつらに投票 2) 他の人たちは順番にvulnerableの人の中で今最も票が少…

問題 長さ2Nの文字列Sを「赤色で塗った文字列を左から右に読んだもの と 青色で塗った文字列を右から左に読んだもの が同じになる」ように塗る方法は何通りあるか求める 解法 半分全列挙 前半N文字の塗り方を決め、赤/青で塗った文字列をx/yとすると、条件を…

問題 SnukeとSotheがカードをn枚ずつ、合計2n枚持っていて、各カードには1〜2nの数字が重複なしで書かれている この状態からnターンのゲームをする 各ターンではお互いにカードを1枚同時に出し、数字がより大きいカードを出した方が1点得る Sotheがiターン目…

ABC100まで 体感難易度(★)、問題概要、一言コメント 自分で辞書的に使うために作ったもの まだ解いてない問題の大まかな解法(累積和とかDPとか)を知りたくない人は見ないように