問題 解法 解答 問題 atcoder.jp 解法 x99999... とするのが最適．しかし，N が x99999... という形であった場合，問題文にある X != N という条件を満たせない．そこで，例えば X = N = 199999 となってしまったとき，X = 289999 とすることで回避できる．…

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j, k) := i - 1 日目までで，j 回好意をほのめかし，前回のほのめかしから k 日経過しているときの，i 日目以降に得られる機嫌の合計の最大値 と DP をおく．このとき遷移は，i 日目に好意をほのめかすかどうかの…

問題 解法 解答 問題 atcoder.jp 解法 N を素因数分解したときの項数よりも K が大きいとき，条件を満たす解はない． そうでないとき，答えの 1 ~ K - 1 項まで順番に N の素因数を小さい順に当てはめていけばよい．最後に残った素因数を全て掛け合わせたも…

問題 解法 解答 問題 atcoder.jp 解法 デートする日を最小化することを考える．以下，最小のデート回数を考える． B = 0，すなわち，記念日が無いとき，最小のデート回数は N / A． そうでないとき，0 日目と最初の記念日の間，B - 1 箇所ある隣り合う記念日…

問題 解法 解答 問題 atcoder.jp 解法 木を頂点，枝を辺として無向グラフを考える．このとき，前に移動した枝の隙間の大きさを状態として加えたダイクストラ法を用いて，頂点 1 から各頂点まで休まなければいけない最小の回数が求まる．よって，答えは (dist…

問題 解法 解答 問題 atcoder.jp 解法 数列 A のある隣り合う 2 つの要素の一方が負の数でもう一方が正の数であるとき，両方に -1 をかけるという操作はマイナスの符号を負の数のものから正の数のものへ移動させることと同値である． これを踏まえると，A に…

問題 解法 解答 問題 atcoder.jp 解法 数列 A のうち 1 つを選び，任意の整数に書き換えられるということは，その選んだ数は A 全体の GCD に影響を与えないということと同値である．なので，ある個所を選んだ時の GCD は，その箇所より左の部分列の GCD と…

問題 解法 解答 問題 yukicoder.me 解法 操作を行った後の数列 A の和が最も大きくなるのは，1 回も操作を行わないときになる（つまり (1, 2, ... , N)）．この和を max ( = N * (N + 1) / 2) とおく．また，操作を行った後の A の和が最も小さくなるのは，A…

結果 C - Stones D - Three Colors 結果 ４問中１問正解（300 / 2500 点, 12:06），1101 位中 459 位，パフォーマンス 1709，新レート 1540 (+20)．C 問題を早解き出来ていれば黄色パフォを取れていたので残念だった． C - Stones babcs2035.hateblo.jp D - …

問題 解法 解答 問題 atcoder.jp 解法 a の和を sum とすると max({R, G, B}) < sum / 2 が成り立っていれば三角形を構成出来る．なので，R, G, B のどれかが 1 つでも sum / 2 以上の値であるとき，三角形は構成できない． ここで，塗り分ける場合の数全体…

問題 解法 解答 問題 atcoder.jp 解法 黒の右には白はないので，操作後の石の列は「白白白白白...」か「黒黒黒黒黒...」か「白白白...黒黒黒...」となる．よって，左から何個かを白にして，そのほかを黒にすればよい．この「何個」を 0 ~ N まで試せばよい．…

問題 解法 解答 問題 yukicoder.me 解法 まず，ニワトリ i が k 回食料として利用されるとき，ニワトリ i - 1 は必ず k 回以上利用されなければならない．そうでなければ，問題のルールに反してしまう． 次に，各ニワトリに分けて考える．各ニワトリについて…

問題 解法 解答 問題 yukicoder.me 解法 コインの枚数の境目は最大でも 2 * N 個しかできないので，コインの数字を座標圧縮することを考える．そうすると，空間計算量を O(N) に減らせる．各コインの枚数の区間において，その区間に属するもともとのコインの…

問題 解法 解答 問題 yukicoder.me 解法 A + B は C の倍数であるので，C は A + B の約数となる．よって，A + B の約数を列挙し，これらを C の候補とし，条件を満たす候補があるかどうかを試せばよい．O(√(A + B))． 解答 yukicoder.me

問題 解法 解答 問題 atcoder.jp 解法 スタートからゴールまでの移動は，まずスタートから全てのマスが移動できるマスであるような行まで移動し，ずっと右へ進み続け，その後ゴールのマスまで下がっていくようになる．到達可能である条件は「全てのマスが移…

問題 解法 解答 問題 atcoder.jp 解法 入口と出口を全てのマスについて試していては TLE となってしまうので，候補を減らすことを考える．すると，それぞれ A_i, B_i の座標全てについて調べれば十分であるので，候補を減らすことが出来た．O(N^3)． 解答 at…

問題 解法 解答 問題 atcoder.jp 解法 まず，最も長くなるような 1 の連続する部分列をただ 1 つ作るのが最適になる．なぜならば，わざわざ間に 0 をいくつか挟み複数の 1 が連続する部分を作るのであれば，複数の 1 の部分のうち最も長いものの両端の 0 の…

問題 解法 解答 問題 atcoder.jp 解法 タイルを塗り替えた後の S は 01010... か 10101... の 2 通り．つまり，この 2 つと初期状態の S を比べ，違う色の枚数の少ない方を塗り替えたあとの S として採用すればよい．O(|S|)． 解答 atcoder.jp

問題 解法 解答 問題 yukicoder.me 解法 まず，各クエリで与えられる頂点を始点としてダイクストラ法を用いて全頂点への最短距離を求める．ここで，到達できる頂点の数が最大の友達の数になる． 次に，各頂点と始点の頂点が何日で友達になるかを調べる．1 日…

問題 解法 解答 問題 yukicoder.me 解法 N の素因数をあらかじめ求めておき，1 ~ N - 1 の全ての数について素因数を求め，N の素因数と共通しているものが K 以上あるものは約数の個数を計算し，その約数の個数を最大化するように更新していく．最大の約数の…

問題 解法 解答 問題 atcoder.jp 解法 （解法の証明をせず通してしまった） 数列 a の中の最大値である箇所が何回かの操作によって最小値になるまでにかかる最小の操作の回数を二分探索で求め，操作後の a をソートし，またこの二分探索を繰り返していき，最…

問題 解法 解答 問題 atcoder.jp 解法 XYZ 通り列挙していては当然間に合わないので，まず XY 通り全て列挙する．この XY 通りのうち，K + 1 番目以降は最終的な答えの K 個の中に入らない（これは実験すると明らか）．なので XY 通りをソートし，大きいもの…

問題 解法 解答 問題 atcoder.jp 解法 A, B, C, D, E のうち最も少ない人数に合わせて人を運ぶという方針でよい．なぜなら，それより多い人数を運んでも，容量の小さい箇所で人が溜まってしまい，結局は同じになってしまうから．よって，容量の小さい箇所を …

結果 A - Ilya and a Colorful Walk B - Alyona and a Narrow Fridge C - Ramesses and Corner Inversion D - Frets On Fire 結果 ８問中４問正解（4134 / 18000 点），4753 位中 1081 位，新レート 1587 (+100, Highest)．誤答無しで４問通すことが出来たの…

問題 解法 解答 問題 codeforces.com 解法 まず S をソートしておき，重複しているものは取り除いてよい． ここで，各クエリで与えられる区間の「位置」は答えに影響を与えず，「長さ」が影響を与える．なぜならば，区間が [l, r] としたら，その区間にあっ…

問題 解法 解答 問題 codeforces.com 解法 問題にある操作は「任意の x1 < x2, y1 < y2 となるような 4 つの値を選び，マス (x1, y1), (x1, y2), (x2, y1), (x2, y2) の値を反転させる」と言い変えることが出来る．また，マス目 A, B で異なっている箇所をマ…

問題 解法 解答 問題 codeforces.com 解法 何本までを冷蔵庫に入れるか (k) を固定して考えたとき，a_1, a_2, ... , a_k をソートしたものを b とおく．まず，高さ b_k のものを入れなければならないので，仕切りは必ず b_k の高さが入るような空間が出来る…

問題 解法 解答 問題 codeforces.com 解法 各色ごとに最も小さい座標と最も大きい座標を求め，それぞれソートしておく．その後，ある色を固定したとき，ほかの色の最大値を求めその差の max を取り答えにする．ほかの色の最大値を求めるのには事前に各色の最…

結果 Foregone Solution You Can Go Your Own Way 結果 50 / 100点，31663 位中 6285 位．予選通過基準である 30 点を超えることが出来たので，Round 1 に進めることになった． Foregone Solution babcs2035.hateblo.jp You Can Go Your Own Way babcs2035.h…

問題 解法 解答 問題 codingcompetitions.withgoogle.com N * N マスを左上から右下まで移動する手順が与えられる．この手順のパスを通らずに右か下への移動だけを用いて左上から右下まで移動する手順を1 つ出力する問題．なお，入力で与えられるパスと交わ…