mayoko’s diary

プロコンとかいろいろ。

CodeChef

CodeChef Chef and cities

問題 Contest Page | CodeChef数列 F が与えられる。以下のクエリを処理せよ。 F[p] = f とする R が与えられるので, F[0]*F[R]*F[2*R]*...*F[(N-1)/R*R] の値について, 10 進法における一番上の数, 10^9+7 で割ったあまり を求める 解法 自分の解法だと 100…

CodeChef Chef and Rectangle Array

まためっちゃ久しぶりに記事書いてますね…最近心に余裕がなくて全然解いてない… 問題 Contest Page | CodeChefN*M の行列が与えられる。これに対して Q 個のクエリが投げられるのでそれぞれに答えよ。 整数 a, b が与えられるので, N*M 行列の中にある a*b …

CodeChef Chef and his study plans

問題 Contest Page | CodeChefN 個の区間 [Si, Ei] が与えられる。以下の Q 個のクエリに答えよ。 s, e が与えられるので, 上記 N 個の区間のうち, [s, e] におさまるものの個数の最大値を求める。ただし, 区間同士は交差してはいけない。i.e. [Si, Ei] と […

CodeChef Longest Increasing Subsequences

問題 Contest Page | CodeChef1, 2, ..., N の順列を使って, LIS が K 個あるようなものを作れ。ただし, 1 解法 とりあえずチェックプログラムを作っておくほうが良さそうなので, まずそっちを作りましょう(下のプログラムで check ってやつ)。LIS の個数を…

CodeChef Sharing Candies

問題 Contest Page | CodeChef整数 A, B, C, D が与えられる。abs( (A+p*C) - (B+q*D) ) を最小化するように p, q(p, q >= 0) を取った場合の, abs の値を求めよ。 解法 これは超典型的で, C, D の最大公約数 g に対して, abs(A+g*p - B) (p は任意の整数) …

CodeChef Ciel and Quiz Game

問題 Contest Page | CodeChefN 問の問題が与えられる。それぞれの正答率は P[i] である。この中から K 問を選んで K-1 問正解する確率を最大化したい。K 問の選び方を構成せよ。 解法 前の GCJ の問題と似ています。mayokoex.hatenablog.comこれと同じよう…

CodeChef Floor Division Game

問題 Contest Page | CodeChefA 君と B 君が数の集合 S1, S1, ..., Sn を使ってゲームをする。ゲームは A 君と B 君が交互に以下の行動をすることで進む。 まだ残っている数から一つ選び, その数を Si/div に変更して再び集合にもどす。ただし, 2 集合に数が…

CodeChef Better Maximal Sum

これが一番難しかったです。 問題 Contest Page | CodeChef数列 a の maximal sum とは, 空でない a の連続した数列の要素の和のうち, 最も大きいものである。数列 a の要素を最大 1 個取り除いてよいとき, a の maximal sum を求めよ。 解法 まず基本的な問…

CodeChef K-good Words

問題 https://www.codechef.com/problems/KGOOD文字列 s が与えられる。s 内に現れる文字 c0, c1 について, |(c0 が s 内で現れる回数)-(c1 が s 内で現れる回数)| 解法 最小回数現れる文字 c を決めうちします。すると, s 内で c より現れる回数が少ない文…

CodeChef Ciel and Battle Arena

問題 https://www.codechef.com/problems/CIELBTL 解法 基本的に dp[va][vb][m] = (自分の残り HP が va で敵の残り HP が vb で残り MP が m である時の勝率)という DP で解けますが, いろいろ難しいところがあるので, ひとつずつやっていきます。まず, 「…