2019-08-30

ABC106-D AtCoder Express2

問題概要

東西に伸びるN個の都市1,2,...Nについて、M本の列車が存在して、列車iは都市Li~Riの区間を走っている。この時、都市piからqiまでの間に完全に含まれる列車の本数が何本かという問いがQ個与えられるので質問それぞれに対して答えを求めよ。

制約

1 <= N <= 500
1 <= M <= 200000
1 <= Q <= 100000
1 <= Li <= Ri <= N
1 <= pi <= qi <= N

方針・所感

最初、1次元の累積和で行けるかな〜って思ったんですけど、終点がどこから来た列車の終点なのかが区別できないことに気づいて断念しました。しかし2次元に落とし込めばうまくいくんじゃないかと座標を書いてみたところ、2次元平面のある領域にある点の数に帰着できることに気づけて、(飛躍していますが)これは所謂2次元BITなのでは、とネットから2DBITのライブラリを探してきて(

https://www.slideshare.net/hcpc_hokudai/binary-indexed-tree

)貼り付けたところACできました。(ACした後に解説をみたら、点の更新がないので2次元累積和で十分(かつ高速)だと気づいたのは後の祭りというやつですね)

補足

二次元累積和とは、x軸y軸方向に累積和を求めておくことによって、二次元平面上のある範囲の和をO(4)で求めることができるやつですね。使うことができるとめっちゃ早い。点の更新があるなら上記のような2DBITを使う必要が出てきます、

細かいところ・デバッグの記録など

脳死で2DBITのクラスを写経したら一発AC、ライブラリ最高！
初の二次元累積和(そして初の2DBIT)なのでとても勉強になりました。
二次元累積和のコードは公式解説参照

実装

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;

template <typename T>
struct twodimBIT{
private:
 vector<vector<T> > array;
const int n;
const int m;
public:
//初期化
twodimBIT(int _n, int _m) : array(_n + 1, vector<T>(_m + 1, 0)), n(_n), m(_m) {}

// (1,1)から(x, y)までの累積和を求める
 T sum(int x, int y){
 T s = 0;
for(int i = x; i > 0; i -= i & (-i))
for(int j = y; j > 0; j -= j & (-j))
 s += array[i][j];
return s;
 }

//[(x1, y1), (x2, y2)]の要素のわ
 T sum(int x1, int y1, int x2, int y2){
return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1-1, y1-1);
 }

//(x, y)に要素kを追加
void add(int x, int y, T k){
for(int i = x; i <= n; i+=i&(-i))
for(int j = y; j <= m; j += j&(-j))
array[i][j] += k;
 }
};

int main(){
int N, M, Q; cin >> N >> M >> Q;
 vector<pair<int, int>> Trn(M), Qst(Q);
 
rep(i, M) cin >> Trn[i].first >> Trn[i].second;
rep(i, Q) cin >> Qst[i].first >> Qst[i].second;

 twodimBIT<int> cnt(N,N);
rep(i, M){
cnt.add(Trn[i].first, Trn[i].second, 1);
 }

rep(i, Q){
 cout << cnt.sum(Qst[i].first, Qst[i].first, Qst[i].second, Qst[i].second) << endl;
 }
}

2019-08-30

ABC123-D Cake

AtCoder ABC 400点半分全探索

atcoder.jp

問題概要

1,2,3の形をしたキャンドルがついたケーキがそれぞれX,Y,Z種類ある。それぞれのケーキには美味しさが割り振られている。1,2,3のついたキャンドルをそれぞれ一つずつ買う選び方で、3つのケーキの美味しさの合計を大きい順にK番目まで出力しなさい。

制約

1<=X, Y, Z <= 1000
1 <= K <= min(3000, X*Y*Z)
1 <= 各美味しさ <= 1e10
入力は全て整数

方針・所感

この回は公式の解説がかなり充実しているので、感想、思考回路を書きます。

単純に考えると全探索してsortした上位K個を出力すればいい分けですが、これだと計算量がO(XYZlog(XYZ))となり確実に間に合いません。高速化するためには何か工夫すべきで、僕は最初に最大の解を作ってから一つずつ引いて解を構成しようとしたのですが、作った解の集合が本当に上位K番目までの集合を含むのか証明できなくて死にました（公式解説にも同様の方針がありますが、証明されてないですよね？）。

見方を変えたところ、集合が3つだから複雑なのであって、先に2つの集合について全探索してから解になり得ないものを切ってしまえば、残りで全探索して十分間に合いそうなことに気づいて解くことができました(所謂半分全探索的な)。

3つの集合、というところにアンテナを張っているべきだったのかもですね🤔

細かいところ・デバッグの記録など

i,jでタイポして大変なことになっていたのでこれからはrepを使うことに

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)

const int MAX_X = 1e3 + 10;
const ll INF = 1e14;

int main(){
 ll X, Y, Z, K; cin >> X >> Y >> Z >> K;
 vector<ll> A(X), B(Y) , C(Z);
rep(i, X) cin >> A[i];
rep(i, Y) cin >> B[i];
rep(i, Z) cin >> C[i];

 vector<ll> D;
 priority_queue<ll> PQ;
rep(i, X) rep(j, Y) D.push_back(A[i] + B[j]);
sort(D.begin(), D.end(), greater<ll>());
D.resize(min(X * Y, K));
 ll W = D.size();
rep(i, W) rep(j, Z) PQ.push(D[i] + C[j]);

rep(i, K){
 ll ans = PQ.top(); PQ.pop();
 cout << ans << endl;
 }
}

2019-08-30

ABC109-D Make Them Even

AtCoder ABC 400点易しめ構築

atcoder.jp

問題概要

縦 $H$ 行横 $W$ 列に区切られたマス目があり、上から $i$ 番目、左から $j$ 列目のマスをマス $(i, j)$ と呼びます。

マス $(i, j)$ には $a_{i j}$ 枚のコインが置かれています。

あなたは以下の操作を何度でも行うことができます。

操作: まだ選んだことのないマスのうち $1$ 枚以上のコインが置かれているマスを $1$ つ選び、そのマスに置かれているコインのうち $1$ 枚を上下左右に隣接するいずれかのマスに移動する

偶数枚のコインが置かれたマスの数を最大化してください。

方針・所感

操作回数を最小にして出力しなきゃならないのかと思いきや、そのような指定はないので左上のマス目から順番にコインが偶数枚ならそのままコインを動かさず、奇数枚ならコインを右か下に動かせばいいだけです。これで一番右下のマス以外は必ず偶数枚になるので偶数枚のコインが置かれたマスの数は最大になります。下の実装だと操作回数を少なくするために場合分けを多くしていますが、ACするだけならいらないでしょう。

細かいところ・デバッグの記録など

形式を守らず複数回WAを出してしまった。ちゃんと空白を入れるか入れないかは場合分けしましょう(・ω<) ﾃﾍﾍﾟﾛ

実装

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i < b; i++)
using namespace std;

const int MAX_H = 510, MAX_W = 510;

int main(){
int H, W; cin >> H >> W;
int a[MAX_H][MAX_W] = {0};
FOR(i, 1, H + 1){
FOR(j, 1, W + 1){
 cin >> a[i][j];
 }
 }
 
int cnt = 0;
 vector<vector<int>> ans;
FOR(h, 1, H + 1){
FOR(w, 1, W + 1){
 vector<int> tmp;
if(a[h][w] % 2 == 1 && !(h == H && w == W)){
 cnt++;
tmp.push_back(h);
tmp.push_back(w);
if(w + 1 <= W && a[h][w+1] % 2 == 1){
a[h][w+1]++;
tmp.push_back(h);
tmp.push_back(w+1);
 }else if(h + 1 <= H && a[h+1][w] % 2 == 1){
a[h+1][w]++;
tmp.push_back(h+1);
tmp.push_back(w);
 }else if(w + 1 <= W){
a[h][w+1]++;
tmp.push_back(h);
tmp.push_back(w+1);
 }else if(h + 1 <= H){
a[h+1][w]++;
tmp.push_back(h+1);
tmp.push_back(w);
 }
ans.push_back(tmp);
 }
 }
 }
 cout << cnt << endl;

rep(i, ans.size()){
rep(j, 4){
 cout << ans[i][j];
if(j != 3) cout << " ";
 }
 cout << endl;
 }
}

2019-08-29

EDPC-O Matching

AtCoder EDPC DP ビットDP 数え上げメモ化再帰

atcoder.jp

問題概要

N人の男性、N人の女性がいる。それぞれ1~Nの番号が振られ、男性iと女性jの相性がいい1(a_i,j = 1)か悪い(a_i,j = 0)かはわかっている。N組の相性が良いペアを作る方法は何通りか？1e9 + 7で割った余りを求めよ。

方針・所感

N <= 21なのでbitDP感がつよいです。これを信じてbitDPの解法を考えてみると実際、男性を1人目から見ていって、男性がどの女性を選んだかをbitとして持って、再帰的に男性がn人目までに女性をbitで選んだ時の場合の数を計算していけば、最後の人は一人しか選べないので下から順に場合の数は求まります。今回はメモ化再帰的に求めました。

細かいところ・デバッグの記録など

最初メモ化再帰をサボって「if(dp[bit] != 0) return dp[bit]」のように書いていたら、dp[bit] == 0で計算済みのところを再計算することになりTLEしました。used[bit]大事
良いbitDPの練習になりました。

実装

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
template<int MOD> struct ModInt {
static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
int get() const { return (int)x; }
 ModInt &operator+=(ModInt that) { if *1{
dp[bit] += rec(depth + 1, bit | (1 << i));
 }
 }
return dp[bit];
}

int main(){
 cin >> N;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
bool t; cin >> t;
if(t) FLAG[i] += (1 << (N-1-j));
 }
 }
 cout << rec(0, 0) << endl;
}

参考にしたサイト等

https://www.hamayanhamayan.com/entry/2019/01/11/002356

*1:x += that.x) >= MOD) x -= MOD; return *this; }

ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }

ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }

ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }

ModInt operator+(ModInt that) const { return ModInt(*this) += that; }

ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }

ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }

ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }

ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;

while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }

return ModInt(u); }

bool operator==(ModInt that) const { return x == that.x; }

bool operator!=(ModInt that) const { return x != that.x; }

ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }

};

template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };

template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {

ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }

typedef ModInt<1000000007> mint;

const int MAX_N = 21;

int N;

int FLAG[MAX_N];

mint dp[1 << 21];

bool used[1 << 21];

mint rec(int depth, int bit){

if(depth == N) return 1;

if(used[bit]) return dp[bit];

used[bit] = 1;

for(int i = 0; i < N; i++){

if((1 << i) & (~bit & FLAG[depth]

2019-08-29

ABC113D-Number of Amidakuji

AtCoder ABC 400点数え上げ DP

atcoder.jp

問題概要

長さH+1の平行な縦棒がW本与えられる。この縦棒の1,2,...Hの高さに横線を引いてあみだくじを構成する。この時、横棒は

互いに端点を共有しない
それぞれの横棒の２つの端点は同じ高さになければならない
横棒は隣り合う縦線を繋がなければならない

という制約を守って引く。この時、左から1番目から出発してK番目に到着するようなあみだくじの構成の方法の数を1e9 + 7で割った余りを答えよ。

方針・所感

解説をチラ見してACしました。あみだくじを2次元の座標と見てDPして数え上げていくという発想が足りませんでした。要精進です。

上から順に数え上げていくという発想さえ分かればあとは素直に解いていけます。「dp[h][k] := 高さhのk番目の棒に1を出発してたどり着く方法」と定義して、また、「f(i,j):=i,j番目の棒に横棒を引かないで、hの高さに横棒を配置する場合の数」と定義すると、

dp[h][k] = dp[h-1][k] *f(k) + dp[h-1][k-1] * f(k-1,k) + dp[h-1][k+1] * f(k, k+1)

と漸化式が建てられDPできます。よって、あとはfさえ計算できればDPテーブルをうめていくO(HW)の計算量で大丈夫そうです。

fの計算は、横棒を引けない棒によって分けられる棒それぞれについて棒の引き方を考えてその積を取れば求められそうです。ここで、Wは高々8なので、8本以下について予め計算しておけばあとはO(1*2)で求められそうです。これは、左から順番に考えていくと、左側の棒がまだ横棒を引いていなかったら横棒を引けて、引いていたら横棒が引けないので、i本目に横棒を引くか引かないかの2つの状態を持って漸化式を計算していけばこの数は計算できます(ちなみに、i本目に横棒を引かない状態の数はフィボナッチ数列となるので、考察する余裕があったらフィボナッチ数列として計算するとコードがすっきりします)。

以上よりdp[H][K-1]が答えとなります。

細かいところ・デバッグの記録など

下方向をh軸正としています。
方針が分かればやるだけ

実装

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
template<int MOD> struct ModInt {
static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
int get() const { return (int)x; }
 ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
 ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
 ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
 ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
 ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
 ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
 ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
 ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
 ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
return ModInt(u); }
bool operator==(ModInt that) const { return x == that.x; }
bool operator!=(ModInt that) const { return x != that.x; }
 ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
 ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<1000000007> mint;

const int MAX_H = 110, MAX_W = 10;

int main(){
int H, W, K; cin >> H >> W >> K;
 mint ans = 0;

 mint dp[MAX_H][MAX_W] = {0};
 mint memo[MAX_W][2], count[MAX_W];
memo[1][0] = 1;
memo[1][1] = 0;
count[0] = 1;
count[1] = 1;
for(int i = 2; i < MAX_W; i++){
memo[i][0] = memo[i-1][0] + memo[i-1][1];
memo[i][1] = memo[i-1][0];
count[i] = memo[i][0] + memo[i][1];
 }

dp[0][0] = 1;
for(int i = 1; i <= H; i++){
for(int j = 0; j < W; j++){
dp[i][j] = dp[i-1][j] * count[W - 1 - j] * count[j];
if(j - 1 >= 0)dp[i][j] += (dp[i-1][j-1]) * count[j-1] * count[W - 1 - j];
if(j + 1 < W)dp[i][j] += (dp[i-1][j+1]) * count[j] * count[W - j - 2];
 }
 }
 cout << dp[H][K - 1] << endl;
}

参考にしたサイト等

AtCoder公式解説

2019-08-29

ABC114D_756

AtCoder ABC 400点数え上げ素因数分解約数

atcoder.jp

問題概要

整数 $N$ が与えられます。 $N!$ $(= 1 \times 2 \times . . . \times N)$ の約数のうち、七五数は何個あるでしょうか？

ここで、七五数とは約数をちょうど $75$ 個持つ正の整数です。

方針・所感

約数の個数は「素因数分解して、それぞれの指数に1を足して、全部掛け合わせる」ことで計算できることが有名です。(出典:高校数学の美しい物語様

https://mathtrain.jp/numberofd)

なので、N!をとりあえず素因数分解して75 = (1 + 2) * (1 + 4) * (1 + 4) = (1 + 4) * (1 + 14) = (1 + 2) * (1 + 24) = (1 + 74)を満たすような素因数分解した指数p(,q,r)の組み合わせを調べれば良さそうです。実際、N!の素因数分解はO(N^(3/2))で出来て、数え上げはせいぜいO((NlogN)^3)に収まりそうなので計算量は余裕です。

細かいところ・デバッグの記録

(p,q,r) = (2,4,4)の時に重複を防ぐために数値の順序付けを行なっています
素因数分解ライブラリは作っておいた方が楽

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// N!を素因数分解してmapに表示
unordered_map<long long, int> prime_factor(long long N){
 unordered_map< long long, int> ret;
for(long long n = 1; n <= N; n++){
 ll tmpn = n;
for(long long i = 2; i * i <= n; i++){
while(tmpn % i == 0){
ret[i]++;
 tmpn /= i;
 }
 }
if(tmpn != 1) ret[tmpn]++;
 }
return ret;
}

int main(){
 ll N; cin >> N;
 unordered_map<ll,int> ret = prime_factor(N);
int cnt = 0;

//a^2b^4c^4パターン
for(auto e: ret){
for(auto f: ret){
if(e == f) continue;
for(auto g: ret){
if(e == g || f == g) continue;
if(f.first > g.first) continue;
 
if(e.second >= 2 && f.second >= 4 && g.second >= 4) cnt++;
 }
 }
 }
 
//a^4b^14パターン
for(auto e: ret){
for(auto f: ret){
if(e == f) continue;

if(e.second >= 14 && f.second >= 4) cnt++; 
 }
 }

// a^3b^25パターン
for(auto e: ret){
for(auto f: ret){
if(e == f) continue;

if(e.second >= 24 && f.second >= 2) cnt++;
 } 
 }

// a^74パターン
for(auto e: ret){
if(e.second >= 74) cnt++;
 }
 cout << cnt << endl;
}

参考にしたサイト等

AtCoder公式解説

2019-08-29

ABC115D_Christmas

AtCoder ABC 400点再帰

atcoder.jp

問題概要

とある世界では、今日はクリスマスです。

高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル $L$ バーガー ( $L$ は $0$ 以上の整数) とは次のようなものです。

レベル $0$ バーガーとは、パティ $1$ 枚である。
レベル $L$ バーガー $(L \geq 1)$ とは、バン $1$ 枚、レベル $L - 1$ バーガー、パティ $1$ 枚、レベル $L - 1$ バーガー、バン $1$ 枚、をこの順に下から積み重ねたものである。

例えば、パティを P、バンを B で表すと、レベル $1$ バーガーは BPPPB (を $90$ 度回転したもの)、レベル $2$ バーガーは BBPPPBPBPPPBB といった見た目になります。

高羽氏が作るのはレベル $N$ バーガーです。ダックスフンドのルンルンは、このバーガーの下から $X$ 層を食べます (パティまたはバン $1$ 枚を $1$ 層とします)。ルンルンはパティを何枚食べるでしょうか？

方針・所感

サンプル1を見て少し考えると、パンの位置を考えるには"B(BPPPB)P(BPPPB)B"と5つに分けてどの部分にあるかを見て、そこから対応するさらに低い次元でのパティの枚数、位置を考えれば出来そうな感じがします。実際にそのまま5つに場合分けして書くと出来てしまいます。非常に教育的な、典型的な問題ですね。

細かいところ・デバッグの記録

公式解説だと3つに場合分けした解法が載っていますが、コンテスト中にやるなら素直に5つに場合分けした方が楽だと思います。
レベルNバーガーのPB合わせた枚数は漸化式を解くだけで数学的に求められそうですが、楽さを優先して素直に実装しました。

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 50;
ll dp[MAX_N+1]; // dp[i] := レベルiバーガーのPB合わせた枚数

ll rec(ll N, ll X){
if(N == 0) return 1;

if(X == 1) return 0;
else if(X < (dp[N] + 1) / 2)return rec(N-1, X-1);
else if(X == (dp[N]+1)/2) return rec(N-1, dp[N-1]) + 1;
else if(X < dp[N]) return rec(N-1, dp[N-1]) + 1 + rec(N-1, X - (dp[N]+1)/2);
else return 2 * rec(N-1, dp[N-1]) + 1;
}

int main(){
 ll N, X;cin >> N >> X;
for(int i = 0; i <= N; i++){
if(i == 0)dp[i] = 1;
else dp[i] = 2 * dp[i-1] + 3;
 }
 cout << rec(N, X) << endl;
}

参考にしたサイト等

AtCoder公式解説