kurarrr's memooo

主に競プロ備忘録

ARC 060 E 高橋君とホテル

AtCoder 競プロ

問題概要

直線上のN個の点x_iが与えられる.
1回に合計距離Lまでの点から点への移動が可能として, 以下のQ個のクエリを処理せよ.
- a,b間の移動には何回移動が必要か
1 <= N <= 105, 1 <= Q <= 105

解法

r[i][k] := (iから2k回正方向に移動してたどり着ける頂点)
初期化 r[i][0] = (2分探索でx[i]+L以下の最大の点)
遷移 r[i][k+1] = r[r[i][k]][k]
とダブリングで下処理をしておいて,
クエリa,b(a<b)には,kを逆順として
- r[a][k] < b ならr[a][k]に移動 を繰り返す.
計算量はO((N+Q)logN)

メモ

ダブリング全般として,クエリの判定のところで r[a][k] < bは等号がつかないのに引っかかった.
(等号をつけると無駄な回数足してしまう可能性がある)

コード

Typical DP Contest H - ナップザック

AtCoder 競プロ

問題概要

N個の荷物の重さwi,価値vi,色ciが与えられる.
重さW以下,色C色以下で達成できる最大価値を求めよ.
1 <= N <= 100,1 <= W <= 105, 1 <= C <= 50

解法

dp(i,j) := (i色以下,重さj以下で持てる最大価値) としてdp(i,j)を更新していく.
w,vは色ごとに持っておいて,各色でその色を使う時を考えていくが,
色c を見ている時,各cについてdp(i,j) の更新のために
dp2(i,j) := (c以下の色をi色以下使った時の重さj以下の最大価値) を用意する.
するとある色cの荷物w,vを見る時に各i,jについて以下の3つを遷移すれば良い.
dp2(i+1,j) = max(dp2(i+1,j), dp2(i+1,j-w)+v, dp(i,j-w)+v ) .. ( * )
前から 荷物を持たない場合,荷物を持ちその色の荷物を既に持っていた場合,荷物を持ちその色の荷物を初めて持つ場合となる.
なおjは逆順に遷移する.これは昇順に遷移すると,j->j+w->j+2wと更新され,荷物が無限個あることになってしまうからである.
上の式を更新し終わったら i,jについて dp(i,j) = max(dp(i,j),dp2(i,j)) としてdpテーブルを更新する.
ここでわざわざdpとdp2を分けるのは ( * ) の処理の時にdp(i,j)が色c-1以下だけを使ったテーブルである必要があるためである.
計算量は O(N C2 W)となって十分.

メモ

最初各色についてDPしようとしたらO(NCW2)となって無理だった.難しい.

コード

Educational Codeforces Round 38 D. Buy a Ticket

Codeforces 競プロ

問題概要

N頂点M辺の無向グラフと各辺の距離が与えられる.
また各頂点に対してコストc[i]が与えられる.
各i (1<=i<=N)に対し min_j(2dist(i, j)+c(j))を求めよ.
2 <= N <= 2105, 1 <= M <= 2*105

解法

Dijkstraで各頂点とそのコストを初期位置としてキューに入れると,
各頂点に対し各(始点のコスト)+(始点からの距離)を更新していくので解ける.

メモ

始点複数のDijkstraを初めて見たのでできなかった. 言われて見ると,そうだね,という感じ.
オーダーがすごく見積もりにくい気がするのだけどまあO(E+Vlog(V))かな
こういうタイプは無向グラフには使えないので注意.
一回やってれば解けそう.

コード

Educational Codeforces Round 38 C. Constructing Tests

問題概要

0,1からなる行列で,どのMxMの小行列をとってもいずれかの要素に0が含まれる行列をM-free Matrixという.
整数xが与えられ,1の要素数を最大化したNxNのM-free Matrixで,1の要素数がxであるようなN,Mを答えよ.
というクエリがt個与えられるので各々出力せよ.
1 <= x <= 109, 1 <= t <= 100

解法

NxN行列に対して左上から重ならないようにMxMの小行列を取っていけば求めるN,Mが
N2 - (floor(N/M))2 = x を満たしていれば良いことがわかる.
S = floor(N/M)とすると, x<=109 から N<=105ほどまで全探索すれば十分であることがわかる.
(正確には floor(N/M) ~ N/M として評価すれば上から挟める)

N,Sを見つければ,floor(N/M) = S なるMが存在するかという問題を解けば良い.
これは M=floor(N/S)として上の式を満たすかどうかを確かめれば十分であり,満たさなければ他の解を探索する.
厳密には, N = SM + k (0<=k<M)と表されるので,
SM <= N < (S+1)M <-> N/(S+1) <M <= N/S (1) から,
floor(N/(S+1)) < floor(N/S) であれば良い(*1の範囲が整数を跨いでいる)
そのようなMは複数あるかもしれないが,存在する場合はN/Sで十分となる.

メモ

難しく考えすぎて解けなかった..

コード

ARC 058 E - 和風いろはちゃん / Iroha and Haiku

AtCoder 競プロ

問題概要

整数N,X,Y,Zが与えられる.
整数1〜10から成り,XYZを含む要素数Nの数列をmod1e9+7で求めよ.
なお{a_i}がXYZを含むとは
sum(x<=i<y)(a_i) = X, sum(y<=i<z)(a_i) = Y, sum_(z<=i<w)(a_i) = Z
を満たす 0 <= x < y < z < w <= N が存在することとする.
1 <= N <= 40, 1 <= X,Z <= 7, 1 <= Y <= 5

解法

数え上げDP.
数列{a}に対し全単射の写像f({a})が存在すれば,各0<=i<N,f({a}),1<=k<=10に対し
dp[i+1][f({a}+{k})] += dp[f({a})] とすると, O(10N * size(f)) で求められる.

問題はこの写像をどう定義するか. 単に数列を並べたもの,もしくは数列自体にするとsize(f)=10Nとなりとても終わらない.
この問題だと末尾から和がX+Y+Z-1以下になるような部分だけを覚えておけばいいことがわかる.
ex. X,Y,Z = 5,7,5 , {a} ={1,3,4,4,1,1,6,2}だと {4,1,1,6,2} の部分.
これは 1 = 1, 2 = 10, 3 = 100,..とすればうまくいく.
ex. f({1,2,3}) = 110100となる
X+Y+Z-1以下だけ見ていけば良いので, size(f) = 2X+Y+Z-1 になる.
下からX+Y+Z,Y+Z,Zのビットが立っているようなものがXYZを含む数列になるので,
そのようなものを数え上げる.(コードだとjインデックスの最後に置いている)
この写像の立て方をしなくても,このような数列に対しインデックスをつけて下処理すればできるっぽい kmjpさんのブログ

メモ

和の通り数をコンビネーションで解こうとして無理だった.
(数え上げDPの典型処理ができなかった.)

コード

ARC 081 E - Don't Be a Subsequence

AtCoder 競プロ

問題概要

英小文字から成る文字列Sが与えられる.
Sの部分列でないような最短の文字列を求めよ.
ここでS'がSの部分列とは S'[i] = S[a_i] (1<=i<=|S'|) なる単調増加なa_iが存在するものとする.

解法

まず,S[i,N)で一番最初に出てくる文字j(j='a'〜'z')を後ろから見て行き,c[i][j]とする.
dp[i] := S[i,N) の条件を満たす文字列の最短長さ とすれば,
先頭にjを使って文字列を作る場合は dp[c[i][j]+1]+1 となるから
dp[i] = min_j( dp[c[i][j]+1] + 1) で後ろから遷移していけば求められる.
c[N][j] = N, dp[N] = 1, dp[N+1] = 0 に注意する.
もうその文字がない場合はi=Nとし,それに対応するのがdp[N+1] = 0,
また空文字列に対する答えは'a'としてdp[N] = 1.

dp[i] が求められれば前から dp[i] = dp[c[i][j]+1] + 1であるようなjをaから見て行き,
そのようなjを連結して出力すれば良い.

メモ

文字列に関するDPに不慣れだったのと,逆に辿っていくのに時間がかかった.

コード

第3回ドワコン予選 D - ネタだけ食べたい寿司

AtCoder 競プロ

問題概要

{X_i},{Y_i} (0<=i<N, X_i > Y_i) と自然数Mが与えられる.
各i についてX_i,Y_i を選んでいく.
ただし,X_iを選べるのはM回までで,i<N-1でM回選んでしまうとそれ以降のY_iは得られない.
得られる合計を最大化せよ.
1 <= N,M <= 105

解法

まず, M>=Nのケースは全てX[i]を選べば良い.
その他のケースについて,Z[i] := [0,i) で得られるM-1個以下の和の最大値 とする.
これは最小値を取り出すpriority_queueを用いれば更新できる.
sum _ ( 0 <= i < N ) Y [ i ] を求めておいて,以降X[i]を取るものを選び X[i] - Y[i]を足す.
i個目を最後に選ぶとそれ以降を取れなくなってしまうから, sum ( i < j < N ) ( Y [ i ] ) を引けば良く
後ろから X[i] - Y[i]+ Z[i] - sum_ ( i < j < N ) ( Y [ i ] )をの最大値を見ていけば良い.

メモ

M=1のケースに注意.
超典型っぽいのにseg木とか考えてやたら時間を使ってしまったので反省.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 100005;

priority_queue<int,vector<int>,greater<int>> que;
int X[MAX_N],Y[MAX_N],Z[MAX_N];

int main(){
  int N,M; cin >> N >> M;
  rep(i,N) scanf("%d%d",X+i,Y+i);
  int ans = 0;
  if(N<=M){
    rep(i,N) ans += X[i];
    cout << ans << endl;
    return 0;
  }
  rep(i,N) ans += Y[i];
  int temp = 0; fill(Z,Z+N,0);
  rep(i,M-1) que.push(X[i]-Y[i]), temp += X[i] - Y[i];
  // Z[i] := [0,i) から M-1個 とった時のmax(sum(X[j]-Y[j]))
  if(M>1){
    REP(i,M-1,N){
      Z[i] = temp;
      if(que.top()<X[i]-Y[i]){
        temp += X[i]-Y[i]-que.top();
        que.pop(); que.push(X[i]-Y[i]);
      }
    }
  }
  temp = 0; int ma = -INF;
  RREP(i,N-1,M-1){
    ma = max(ma,X[i]-Y[i]+Z[i]-temp);
    temp += Y[i];
  }
  cout << ans + ma << endl;
  return 0;
}