問題 No.285 消費税２ - yukicoder No.286 Modulo Discount Store - yukicoder No.287 場合の数 - yukicoder 解法 No.285 はタネあかしすると簡単で, 元の値段に 108 を掛けたあと, それを 100 で割った商が整数部分, 100 で割った余りが少数部分になります…

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

ぽよ〜 問題 code-festival-2014-morning-hard.contest.atcoder.jp 解法 dp で解けます。dp[n][x] = (n 番目の人が, もとの位置から x 以下だけずれた座標にいるような場合の数) とすると, n 番目の人は, p[n]+x-1 以下の座標にいるか, p[n]+x の座標にいる…

問題 code-festival-2014-morning-middle.contest.atcoder.jp 解法 貪欲法で解きます。右端ができるだけ左にあるものから採用するほうが最適です。ということで, アルゴリズム的には以下のようなことをやります。・a[i] が x[cur] 以下のもののうち, まだ使…

問題 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 と…

問題 code-festival-2014-qualb.contest.atcoder.jp 解法 stack でがんばります。まず, この問題では「右側に見える範囲」及び「左側に見える範囲」を別々に求められれば良いことがわかります。ということで, 右側に見える範囲を求めてみましょう。それがわ…

これジャッジ解も(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 の最大値を…

問題 code-festival-2014-morning-hard.contest.atcoder.jp 解法 単純に漸化式を解くだけです。「n 回ボタンを押した時点で ON になっている確率」を とします。すると, 特性方程式は となるので, よって, (初期条件を考慮した)。 となるので, これをそのま…

本当に Nim だった(grundy 数かもとも思っていたのだけれど) 問題 ttpc2015.contest.atcoder.jp 解法 実は, 「距離が奇数のものからの Nim」ということで解くことが出来ます。距離が奇数のもの全体の状態が (n1, n2, ..., nk) で表されるとしましょう。 まず…

東京工業大学プログラミングコンテスト2015 の M - コインと無向グラフ を解こうとして Nim かなーと思って Nim について調べました。 今度はちゃんと Nim について理解できた気がしたのでざっくり書いていきます。問題設定とかは以下の記事を参考にします。…