問題ページ D: AtCoder Express - AtCoder Beginner Contest 076 | AtCoder 考えたこと 各区間で場合分けして見ていくのを考える。サンプルを見ていると無限に場合分けがありそうで確実にバグらせるのでやめる。 現在の速度を持っておいて1秒ごとにシミュレ…

問題ページ C: Dubious Document 2 - AtCoder Beginner Contest 076 | AtCoder 解法 O(|S||T|)で愚直に探索していく。文字列S内に文字列Tが内包されることがありうるかをこの時点で判定し存在しなければ終了。文字列Tを当てはめるために変換する?以外は全部a…

問題ページ C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder 解法 まず、max(a[i]) = Xの距離のグラフをつくることを考える。このグラフをつくるのに * Xが偶数のとき 距離がX/2の頂点が1個、X/2+1～Xまでの頂点が2個ずつ必要 * Xが奇数のとき 距…

問題ページ E: Frequency - AtCoder Regular Contest 069 | AtCoder 解法 辞書順最小なのでその時点で追加できる最小のものを追加していくようにする。 0 1 2 3 4 5 6 7 8 9 1 2 1 3 2 4 2 5 8 1 -> 8が3(=(8-5)*(8以上の数の個数))回追加 (最大の石の数は8)…

解法 まず、回文が存在する条件として * それぞれの文字種の個数が全て偶数 * 一つの文字種だけ奇数でそれ以外は偶数 のいずれかの条件を満たす必要がある。文字種ごとに文字列内の個数を数え、奇数のものが2個以上あれば存在しないので0を出力する。 cnt[i]…

考えたこと 題意がよくわからなかったのでサンプルを試してみると、同じ高さのビルをi個(1<=i<=N)つくるために必要なコストをA[i]としたとき、A[1]^A[2]^…A[N]を出力すればよさそう。離れた階層のビルの高さを同じにする利点はないのでソートして考える。 dp…

考えたこと PをAに置き換えるためにはPをどこか別の空マスに移し、Aをどこかから持ってくるため2手かかる。.をAに置き換えるためには1手かかる。 ある長方形の範囲を条件を満たす範囲とできるかを考える。Aが2個、Pが1個、.が1個ある範囲を全てAに置き換える…

考えたこと 中心が(0, 0)で半径がrの円と中心が(X, Y)で半径がRの円が共有する部分を持つ条件について考える。半径rが （2円が外接する半径r_1）<= r < （2円が内接する半径r_2）の条件を満たすときと言い換えられる。 r_1 = max(0, sqrt(XX+YY)) (円の中に(…

考えたこと ゲームで石の山だしgrundy数かなあと思いつつ問題文を読む。敗北条件を考えると石の数が1個以下の山しか存在しない場合か山が2個以下しかない場合になる。サンプルを読んでいると山の石の数は2個以上か1個の2パターンしか考慮しなくていいことに…

考えたこと サンプルのグラフを書いてみると、parent1[i]とparent2[i]が2つの異なる値で分類できれば可能であると判定できそうなことに気づく。これはparent1[i]とparent2[i]をつないだグラフが2部グラフであるかどうか判定すればできる。提出したら通った。…

概要 長さnのケーキがあり友人に配るためケーキを切っておきたい。友人には同じ長さの連続したピースのケーキを渡せるようにしたい。来る友人の人数はn以外のnの約数の人数ということしかわかっていない。この条件を満たすような最小のピースの数を出力しろ…

問題ページ C - 4/N 考えたこと 何かうまい構成方法でO(1)？と思ったがよくよく考えると全探索できる。誤差死とオーバーフローに気をつけつつ算数をすると通った。 時間かけすぎで反省。 解法 hとnを決めるとwは一意に決まるのでO(35002)の探索をする #inclu…

問題ページ D - IntegerotS 考えたこと ナップザック問題っぽさを感じる。Kをそのまま配列に持つのは無理なのでbitが立ってる本数を配列に持つのかなあと考えるがうまくいきそうにない。 いろいろ実験してるとKのある桁を1から0にしたとき、それ以下の桁は全…

問題ページ E - CARtesian Coodinate 解法 解説を見た。 https://img.atcoder.jp/tenka1-2017/editorial.pdf www.youtube.com まず、N点からのマンハッタン距離の和が最小になる点について考える。マンハッタン距離はx座標、y座標それぞれ独立に足すことがで…