問題 codeforces.com 解法 桁 DP するだけです。dp[keta][carry] = (keta 目の桁で, 繰り上がりが carry であるような場合に, 和を N にするような 6 つの数字が存在するか)みたいなことをやります。各状態では, 6 つの数字を 0, 4, 7 のどれにするかを 3^6 …

問題 codeforces.com 解法 まず, 問題文をちゃんと把握します。 普通の問題と違って, この問題の場合だと, それまでに通ってきた文字列が一致していれば, 自分のターンに遷移させるマスが変わっても良いというのがポイントです。 と言ってもアレなので例を挙…

問題 codeforces.com 解法 左からいくつの荷物を取るかで全探索します。左から i 個の荷物を取るとすると, 「連続して同じ手を使うとコストが増える」というのを無視した場合かかるコストは l * (w[0]+w[1]+...+w[i-1]) + r * (w[i]+...+w[n-1]) となります…

問題 codeforces.com 解法 配列がすべて d の倍数になるように出来るとすると, 配列のすべての数が m*d + x (x は min(k, d-1) 以下の数)という形で表せることになるので, このようになっているかを調べます。d を全列挙したとしても, これを調べるのにかか…

Codeforces Round #331 (Div. 2) に参加しました。 AB しか解けず撃沈。C は誤読して難しい問題を解いていたようでアレですが, それに気づいてからも実装に時間がかかるなどしてやっぱり実装力無いなぁと。 問題 codeforces.com 解法 とりあえず誤読してない…

問題 codeforces.com 解法 各マグネットの中心(重心)座標しか興味ないので入力値からそれを求めます。この時, double で管理しようとすると不幸になるのですべての座標が 2 倍されてると考えて座標が整数になるようにしましょう。この重心座標については, ど…

つい最近, 作問ミスをしたので他人事ではない。 問題 codeforces.com 解法 なんとなく思うのは, Warrior 側の人は, 端っこ以外の数字をとっても得しないということです。つまり, Warrior 側の人が取る数字は左端から l 個, 右端から r 個 (l+r = (n-2)/2) と…

問題 codeforces.com 解法 問題の様にセンサを取り付けると, センサはサイクロイドと呼ばれる軌道を描きます。 d = f-s とすると, d の の部分の倍数の部分はどうなろうと関係ないので, 結局のところ調べるべき図形は以下のような部分だけになります。 は左…

問題 codeforces.com 解法 Darsein さんの解法を参考にしました。方針としては, dp[m][l][r] = (m 個の n 文字で作ったカッコを並べた時, regular bracket sequence にするために左側に "(" を l 個つける必要があって, 右側に ")" を r 個つける必要がある…

気づくべきことはすぐ気づいたのに漸化式間違えて時間食った。 問題 codeforces.com 解法 要するに, 反転数が 0 になるために何回操作が必要か, という問題です。方針としては, とにかく反転数を減らすのが良いです。状態は反転数のみで記述できて, 反転数が…

Codeforces Round #204 (Div. 1) の練習会に参加しました。今回は B 問題 codeforces.com 解法 まず, 各実数の整数部分は関係ないのでそぎ落としましょう。すると, 基本的には ai の床関数を取ることは ai に対応する整数として 0 を取ることに, ai の天井関…

問題 codeforces.com 解法 まず, 攻撃されていない町をスタート地点にしても得しない, というか損するのでスタート地点は少なくとも攻撃されている都市のいずれかである, ということがわかります。攻撃されている町全体が連結になるように木を作ることが出来…

問題 codeforces.com 解法 まず, w と b の最小公倍数 lcm ごとになにか周期になっているっぽいことは明らかです。で, この問題の場合は L が n * lcm + a (0 自然数) と表せる場合のみ結果が引き分けになります。ただ, n = 0, a = 0 の場合は問題の都合上除…

問題 codeforces.com 解法 半分全列挙するだけです。覚えておく量は, 「L と M の差」, 「L と W の差」だけで十分です。 const int MAXN = 30; const int INF = 1e9; int Q[MAXN][3]; int n, N; struct quests { vector<int> select; int L, M, W; }; map<pii, quests> qs; vo</pii,></int>…

問題 codeforces.com 解法 Stern Brocot 木というのが元にあるようです。実は, この操作は Stern Brocot 木の操作とそれぞれ対応しています。 まず, Alice がみかんを, Bob がりんごを最初に 1 個ずつ持ってる状態は Stern Brocot 木では (0/1, 1/0)(分数と…

問題 codeforces.com 解法 lca を使って lca と同じようなテクニックを使って解きます。lca の時と同じように, vals[logk][v] = (v から 2^logk だけ上までの頂点における, ID の小さい順の数列 p1, p2, ..., p10) というのを保持しておきます。 で, 頂点 u …

問題 codeforces.com 解法 dp[k][i] = (数列 a をつなげた個数が k 個で, 末尾の添字が i となるような場合の数) とします。これがわかれば, 数列が k 個つないでいるようなものが大体 p = L/N - k 個あるのでそれを数えて dp[k][i] * p の和を取っていけば…

Div2 A, B の絶望的な読みにくさに比べるとこちらはややマシ。まだ言いますけど Div2 A, B は関係ないこと書きすぎでホント英語弱者に優しくない 問題 codeforces.com 解法 dp[t][row][col] = (時間 t に row, col にいてゴールすることは可能か)をやるだけ…

あまりの問題文の長さに撤退してしまったこどふぉ。ただ最近言い訳ばっかして Splatoon やってるだけなのでちょっと頑張らないといけないですね〜 問題 codeforces.com 解法 子供の診察順に処理していきます。i 番目の子の治療ができるかを確かめるために, …

問題 codeforces.com 解法 順列の置換は, 一般に巡回置換の積で表すことが出来ます。巡回置換については wikipedia を参考に -> 置換 (数学) - Wikipedia巡回置換の積それぞれのパーツを分析していきます。一つの巡回置換が A 個の成分で構成されているとす…

こういう地頭みたいな問題全く解けないの本当に悲しい。 問題 codeforces.com 解法 わからなかったので解説を参考にしました。codeforces.comとりあえず目標となる順列 s が 1 2 3 4 ... n となるように p を調整しておきます(下のコードでは間違えて p を目…

問題 codeforces.com 解法 本番は「素数 和 奇数」で検索したらいい感じの結果が出たのでそれを参考にしてやりました。多分「弱いゴールドバッハの予想」というのが出てくると思います。さらに下の方まで読んでいくと「5より大きい奇数は 1 個の奇素数と 2 …

Codeforces Round #324 (Div. 2) に参加しました。結果は 4 完でした。D は問題としては結構面白いと思ったんですが確信を持てないのがちょっと… 問題 codeforces.com 解法 s1, s2 の i 文字目と s3 の i 文字目と, f(s1, s3)(f1 とする) と f(s2, s3)(f2 と…

これジャッジ解も(C++ で) 300ms くらいかかってるのに時間制限が 1000ms しか無いのはどうかと思うんですがどうなんですかね。 問題 codeforces.com 解法 長さ s を固定して考えてみます。で, が superior であるとすると, まず が比較されるすべての数字 …

こどふぉの仕様変更でまた div2 になってしまいましたがまぁ div1 B はあんまり解けないので仕方ないですよね。ただ採点結果を見るのに時間がかかるのがちょっと辛いです。 問題 codeforces.com 解法 動的計画法で解きます。dp[p][i][j] = (p 回数列が繰り返…

問題 codeforces.com 解法 数列 a を大きい順に並べた時, と並ぶとします。この時, GCD table の一番大きな値は と一致します。なぜかというと, 任意の整数 p, q について, gcd(p, q) が GCD table の最大値よりも小さかったとすると, GCD table の最大値を…

問題 codeforces.com 解法 よく考えると, 長方形を並べるパターンは, サンプル 1 のように長方形を縦に並べるパターンか, サンプル 2 のようにひとつの長方形が上に来て残りの長方形がエリアを分け合う感じのいずれかしかないことがわかります。うまいこと場…

起きれなかったので virtual participation で参加しました。ABCD 解けてそこそこです。ただ D 解くのが遅かったので反省です。 問題 codeforces.com 解法 dp[state][f] = (今までに選んだ食事が state で表されて, 一番先頭に選んでいる食事が f の時の, 最…

問題 codeforces.com 解法 まず, 数列 a の weakness の値 w(x) は x に関する凸関数になることを把握します。 これは, w(x) が abs(S-x) (S は区間ごとの和) の最大値を取るような感じになっていることからわかります。よって, この問題では w(x) の値をあ…

問題 codeforces.com 解法 一回 x を掛け算すると x は 2 以上なのでビットは 1 以上左にシフトします。よって, 一つの数に集中的に x を掛け算するのが良いです(もしバラバラに x を掛け算すると, 左にシフトする数が少なくなるので不利)。ということで, す…