ferinの競プロ帳

競プロについてのメモ

ukuku09コンテスト 001-photography

Hamako Online Judge

区間と言われたので累積和を取りたくなる。累積和をSで書くことにするとl番目の要素を区間の左端とするとき P+S[l-1] 以上のもっとも右にある要素の位置が分かればl番目が区間の左端のときの最適な区間が求まる。右端がO(1)かO(logn)くらいで求められればできそう。累積和がN以上のもっとも右にある要素の位置を持っておけばよさそう。累積和の値は大きすぎて配列でもつのは不可能なのでmapでもつ。
累積和を取ったあと後ろから見ていって、今まで見た中で一番大きい値であれば更新してmapに値を設定する。mapを使えば区間の左端を指定した時に二分探索すれば右端がO(logn)でわかるのでO(nlogn)でできる。

(嘘解法じゃないかちょっとこわい)

SRM716 div2 hard

概要

最初のm個がp[i] != iとなっているという条件を満たす長さn+mの順列pの個数をmod 10^9+7で求める。

解法

条件がなかったとしたら順列の個数は(n+m)!となる。次にm個のうち1個が条件を満たしていない個数を考える。m個の中から1個を選び、残りのm+n-1個の順列を取れば求まるため C(m, 1) * (m+n-1)!となり、これを引く。ここで、1点のみを固定して考えたとき重複してカウントしてしまっているパターンがある。m個の中から2個が条件を満たしていない場合の順列の個数は同様に考えると、C(m, 2) * (m+n-2)!となるため、これを足す。同様に重複して足した場合…と考えていくと、iが奇数の場合引いて、偶数の場合足している。つまり包除原理で解くことが出来る。

SRM 716 div2 med

概要

文字列sと文字列tが与えられる。sの各文字をtの文字で置き換えることができる。tの文字はそれぞれ1回ずつしか使用できない。書き換えた後の辞書順最大となるsを出力する。

解法

先に現れる文字を大きいものにしたほうが辞書順としては後のものになる。貪欲法でsの文字を最初から確かめていきtの文字より小さければ置き換えていく。

SRM 717 div2 easy

概要

要素が0か1の2次元配列tが与えられる。x[i] xor y[j] == t[i][j] となる要素が0か1の配列x、yを構成することが可能か判定する。与えられる配列のサイズは5×5以下。

解法

1行目(y[0])を0か1で固定すれば残りの列の数字(x[i])は一意に定まる。残りの行に対して正しければ"Nice"、正しくなければ"Not nice"を返す。
後から考えたらすべての行について同じものかbit反転したものかで判定できそう。

経験した罠

自分がやらかした実装ミス(罠踏んだら追加する)

  • #define int ll
  • 区間l, rに対してmodを取るときにl > rとなっているときを考慮しない
  • 負の数にMODをとって正の値がほしいところに負の値をつっこむ
  • int -> double へのキャストをしない
  • 配列サイズ足りない
  • str.size()とかのsize_t型(unsigned)を負にして値をオーバーフローさせる
  • 出力フォーマットが整数なのに小数を出力

codeforces 415 div2 C

Problem - C - Codeforces

入力列をソートしておいても関係ないため、あらかじめソートされた入力列について考える。
また、関数F(a)は頂点の集合の最大値・最小値にのみ依存する。

例として数列8, 6, 5, 3, 2, 1が入力されたときを考える。
このときの答えは

(8-6)*1 + (8-5)*2 + (8-3)*4 + (8-2)*8 + (8-1)*16
        + (6-5)*2 + (6-3)*4 + (6-2)*8 + (6-1)*16
                  + (5-3)*4 + (5-2)*8 + (5-1)*16
                            + (3-2)*8 + (3-1)*16
                                      + (2-1)*16
= 8*(2^5-1) + 6*(2^4-1) + 5*(2^3-1) + 3*(2^2-1) + 2*(2^1-1)
  -{1*(2^5-1) + 2*(2^4-1) + 3*(2^3-1) + 5*(2^2-1) + 6*(2^1-1) 

となる。最大値と最小値を固定したとき、その集合の個数は 1 + 2 + 4 + … + 2^(n-1) = (2^n)-1で求められる。よって、それぞれの数が最大値として使われる回数と最小値として使われる回数をO(1)で求めることができ、合計でO(n)で答えを求められる。オーバーフローに注意。

TDPD I イウィ

tdpc.contest.atcoder.jp

区間DPの問題。AOJ 1161ダルマ落としと似てる。

dp[l][r] = {lからrまでの区間で操作をできる回数}としてDPする。
区間lからrで間の区間(l+1からr-2orl+2からr-1)が全て削除でき、削除したあとに残る文字列がiwiならばその区間は全て削除できる。
また、区間内でk番目(l <= k < r)で区切り、dp[l][k] + dp[k+1][r] の最大がdp[l][r]となる。
幅が小さい区間から試していくことでO(|S|^3)で計算できる。