くれなゐの雑記

例を上げて 自分で手を動かして学習できる入門記事を多めに書いています

CODE FESTIVAL 2016 qual A. D - マス目と整数 / Grid and Integers

解説に乗ってるけどちょっとわかりにくかったので自分の言葉に置き換えて整理します。 あとイラレの練習(
http://code-festival-2016-quala.contest.atcoder.jp/data/other/code-festival-2016-quala/editorial.pdf
)

要約

行列A = [a_{i,j}], (i \in [1,R], j \in [1,C]) が与えられる.
N個の要素には, すでに値が記入されている.
すべての値は, 以下の条件を満たさなければならない.

条件1. すべての範囲内のi,jに対して,  a_{i,j}+a_{i+1,j+1} = a_{i+1,j} + a_{i,j+1}
条件2. a_{i,j} >= 0

問題の変形

この問題では, 変形が重要です.

条件1の変形

条件1を変形すると,
 a_{i,j}-a_{i,j+1} = a_{i+1,j} - a_{i+1,j+1}
となり, 左右同士の差は上下で等しいことがわかります。図の矢印方向の差が等しいということですね
f:id:kurenaif:20160925221650j:plain
上下で等しい 上下で等しい… と下へ下へつなげていくと, 結局同じ列どうしの比較だと, 行にかかわらず差が等しいことがわかります。
f:id:kurenaif:20160925222232j:plain

さすがに, 列が違うと差は変わってきます.(同じだと思ってた時期が私にもありました…)
ここで, それぞれの行の一番左の値(a_{1,1} ,\cdots,a_{R,1}) を 簡単のためにx_1, \cdots, x_R とおき,
a_{i,0}-a_{i,1}, a_{i,1}-a_{i,2}, \cdots, a_{i,C-1}-a_{i,C}y_1, \cdots, y_C とおきます.
f:id:kurenaif:20160925223126j:plain

すると, a_{i,j} = x_i + y_1 + y_2 + \cdots + y_C と表記できることがわかります.

yy_j = y_1 + y_2 + \cdots + y_j = \sum_{i=1}^{j} y_i と置き換えると,

a_{i,j} = x_i + y_j と簡単にすることができます。(画像つくり忘れたんですけど, 矢印が左端からそのマスまでたどり着いてるイメージですね)

詳しい証明は解説参照で, ざっくりいうと, 条件1が成立するためには,
すべてのa_{i,j} = x_i + y_j を満たすような, (x_1,\cdots,x_R), (y_1,\cdots,y_C) が存在しなければならない.
ということになります.

条件2の変形

条件2は, 条件1と組み合わせて,
すべての i,jで,
a_{i,j} = x_i + y_j >= 0
が成立する必要があります. 全通り試すともちろん時間が足りないので, 工夫が必要です.
実は, x_i, y_j のとり方はuniqueではありません. 例えば, x_iを+1したら, y_jを-1したら良いです.
一番小さいところからスタートして(x), 一番小さい値を足す(負の数)と, a_{i,j} の最小値が求まり, これが0以上になればOKっぽそうです

実装方針

a_{i,j} = x_i + y_j を求める.

グラフを使って求めます. x_iy_iを頂点と捉えます.
その間を入力r,c,aを使って
x_ry_c をつなぐ重さaの辺を貼ります.
この時辺と頂点の関係を, x_r + y_c = a と定義します.

二変数なので, なにか一つ値を決めないといけません. 一つ値を適当に0(なんでもいいです)と決めると, あとは随時決まっていくのがわかると思います.
(例えば, x_0 + y_1 = 3, x_0+y_2 = 4 という風に辺が張られていたら, x_0=0と定めると, y_1, y_2は自ずと決まってきます)

こんな感じでDFSで求めていきます.

条件2

DFSと一緒に, xの最小値とyの最小値を更新しながら探索していきます.
xの最小値+yの最小値 < 0 ならば, "No" となります.

実装する上での注意点

xの最小値とyの最小値の初期値に注意しなければなりません
処理をするときに, x_i + y_j のように描いていると, オーバーフローするのでこのような実装をするならば, LLONG_MAX/2-1程度を上限にすると良いでしょう.

SourceCode

const ll INF = LLONG_MAX / 2 - 1;


struct Edge {
	ll t;
	ll c;
	Edge(ll to, ll cost):t(to),c(cost){}
	Edge(){}
};

vector<ll> weigh;
ll R, C;

bool DFS(ll node, vector<vector<Edge> >& edge, ll& xmin, ll& ymin) {
	if (node < R) xmin = min(xmin, weigh[node]);
	else ymin = min(ymin, weigh[node]);
	for (auto &to : edge[node]) {
		if (weigh[to.t] == INF) {
			weigh[to.t] = to.c - weigh[node];
			if (not DFS(to.t, edge, xmin, ymin)) return false;
		}
		else {
			if (weigh[to.t] + weigh[node] != to.c) return false;
		}
	}
	return true;
}

void solve() {
	cin >> R >> C;
	ll N = in();
	weigh.resize(R + C, INF);
	vector<vector<Edge> > edge(R+C);
	REP(i, N) {
		ll r, c, a; cin >> r >> c >> a;
		--r; --c;
		edge[r].emplace_back(R+c,a);
		edge[R+c].emplace_back(r, a);
	}

	bool res = true;
	ll xmin, ymin;
	REP(i, R + C) if(weigh[i] == INF and edge[i].size() > 0) {
		xmin = ymin = numeric_limits<int>::max();
		weigh[i] = 0;
		if (not DFS(i,edge,xmin,ymin) or xmin+ymin < 0) {
			cout << "No" << endl;
			return;
		}
	}
	cout << "Yes" << endl;

CODE FESTIVAL 2016 qual A. C - 次のアルファベット / Next Letter

解き方

この操作をして, 辞書順を小さくするためには, 'b'より大きいものを一周させて'a'にする以外ない.

辞書順最小にするためには, 手前から見ていって, 'a'にできるものは'a'にして, それ以外は無視する と言った処理をすればよい.

この処理は, K 回必ず行わなければならないので, 余ったやつも必ず処理をしなければならない。

まず, アルファベットを何周もさせることができるので, 残ったやつから'z'-'a'+1分だけMODを取った値にすることができる.

さらに残ったものは, 後ろから回していく.(後ろの1文字だけ変更になるはず)

SourceCode

void solve() {
	string S = in();
	ll K = in();
 
	REP(i, S.size()) {
		if (K <= 0) break;
		ll cost = 'z' - S[i] + 1;
		cost %= ('z' - 'a' + 1);
		if (K - cost >= 0) {
			S[i] = 'a';
			K -= cost;
		}
	}
 
	if(K > 0) K %= ('z' - 'a' + 1);
	RFOR(i,0,S.size()) {
		if (K <= 0) break;
		ll cost = min((ll)K, (ll)('z' - S[i]));
		S[i] += cost;
		K -= cost;
	}
	cout << S << endl;
}

Codeforces #712 Div.2 D. Memory and Scores

要約

a,b,k,t が与えられる.
a: Memoryさんの初期点数
b: 相手の初期点数
k: 1ターンに[-k,k]の点数を得ることができる
t: 2tターン行う

Memoryさんがかつことができるのは何通りか(MOD 1e9+7)

以下のようなdpを組む

dp[\mathrm{time}][\mathrm{diff}] := その時間(time)で, Memoryさんのスコア-相手さんのスコアがdiffのときの場合の数

更新方法は簡単で,

dp[t][d] := \sum_{i=d-K}^{d+K} dp[t-1][i]

  • sumはしゃくとり的にやって計算量を減らす.
  • 素数2k+1 なので注意する(1敗)

最終的に, d>0 の部分がMemoryさんが勝つ場合の数なので,

 \mathrm{res} = \sum_{i=1}^{配列の最大} dp[2T][i]
が答えになる
配列の最大要素, K*T くらいとっとけばいいと思ったけどなんかうまくいかなかった.
また, このままだと負の要素にアクセスすることになるので適当にオフセットかける

SourceCode

const int MOD = 1e9+7;
void solve() {
	ll A, B, K, T; cin >> A >> B >> K >> T;
	//dp[time][diff] := cnt
	vector<vector<ll> > dp(2, vector<ll>(2*1000*(210) + 1));
	int offset = 1000*(210);

	int cur = 0, tar = 1;
	if (A - B + offset <= 0) {
		cout << 0 << endl;
		return;
	}
	dp[tar][A-B+offset] = 1;
	for (int i = 0; i < 2 * T; ++i) {
		//REP(i, dp[tar].size()) cout << dp[tar][i];
		//cout << endl;
		ll sum = 0;
		//全範囲更新 TLEしそうだったら頑張る しゃくとり的に
		REP(j, 2 * K+1) sum = (sum+dp[tar][j])%MOD;
		FOR(j, K, dp[cur].size()-K-1) {
			dp[cur][j] = sum;
			sum = (sum-dp[tar][j - K] + MOD)%MOD;
			sum = (sum+dp[tar][j + K + 1])%MOD;
		}
		swap(cur, tar);
	}
	//REP(i, dp[tar].size()) cout << dp[tar][i];
	//cout << endl;
	ll res = 0;
	//REP(j, dp[tar].size()) {
	FOR(j,offset+1,dp[tar].size()){
		res = (res + dp[tar][j]) % MOD;
	}
	cout << res << endl;
}

謝辞, 参考

arrogantldiotさんのソースコードを参考にさせていただきました
codeforces.com

Codeforces #712 Div.2 C. Memory and De-Evolution

要約

正三角形2つが与えられる.
それぞれの辺の長さは, [tex:x, y (y

やること

非縮退三角形とは, 以下の条件を満たす三角形(つまり普通の三角形) 三角形の辺の長さをa,b,c とすると,
 a+b > c \\ b+c > a \\ a+c > b

少し変形して, 辺aに着目すると, 以下のような式になる

|b-c| < a < b+c

辺の長さを減らしていく方向に考えると, 他の辺を減らす量が減ってしまうことがあり, 貪欲に考えることができない.
しかし, 辺の長さを増やしていく方向に考えると, 増やせば増やすほど他の辺もいっぱい増やせるので貪欲に増やすことができる
不等号が含まない不等号なのに注意して,

 a = max(b+c-1, x)

となるようにする.
同様に, a,b,cyから初めて順に大きくしていってxになった時点で終了

SourceCode

void solve() {
	//y -> x
	int x, y; cin >> x >> y;
	vector<int> vx(3, y);
	vector<int> vy(3, x);

	ull cnt = 0;
	ull ok = 0;
	for (ull i = 0;; ++i) {
		int tar = i % 3;
		if (vx[tar] != x) {
			vx[tar] = min(vx[(tar + 1) % 3] + vx[(tar + 2) % 3] - 1, x);
			++cnt;
		}
		else ok |= 1 << tar;
		if (ok == (1 << 3) - 1) break;
	}

	cout << cnt << endl;
}

Codeforces #712 Div.2 B. Memory and Trident

要約

R,L,U,D (Right, Left, Up, Down)の4つからなる文字列が与えられる. それぞれの方向に1ずつ移動する
Memoryさんは, 文字を書き換える能力がある.
文字を書き換えて, 最終的に原点に戻ってくるようにしたい.
なん文字書き換えればよいか. 無理のときは-1を出力する

やること

各文字の出現回数を数える.
RとL, UとDが両方共それぞれ偶数同士, 奇数同士ならばOK
また,
RとL, UとDが両方共それぞれ偶数奇数同士ならば, 一文字書き換えると上記の条件に当てはまるのでOK
それ以外の場合は-1を出力する.

偶数奇数同士の時は, max(R,L) -> min(U,D) に変化させてやる.

最後に, max(R,L) - ave(R,L) + max(U,D) - ave(U,D)の個数+前処理の変化回数(1か0)が答えになる

SourceCode

void solve() {
	string str = in();
	int mapping['Z'];
	mapping['R'] = 0;
	mapping['L'] = 1;
	mapping['U'] = 2;
	mapping['D'] = 3;

	vector<int> cnt(4);

	int res = 0;

	REP(i,str.size()) ++cnt[mapping[str[i]]];
	if (cnt[0] > cnt[1]) swap(cnt[0], cnt[1]);
	if (cnt[2] > cnt[3]) swap(cnt[2], cnt[3]);

	int lsb[4]; REP(i, 4) lsb[i] = (cnt[i] & 1);

	if (lsb[0] != lsb[1] and lsb[2] != lsb[3]) {
		--cnt[1]; ++cnt[2];
		++res;
	}
	else if(not(lsb[0] == lsb[1] and lsb[2] == lsb[3])){
		cout << -1 << endl;
		return;
	}

	cout << cnt[1] - (cnt[0] + cnt[1]) / 2 + cnt[3] - (cnt[2] + cnt[3]) / 2 + res << endl;
}

Codeforces #712 Div.2 A. Memory and Crow

要約

数列b_1, b_2, \cdots,b_n が与えられる.
a_i = b_i-b_{i+1}+b_{i+2}-\cdots+b_{n} を満たすような a_i を求めよ

やること

後ろから考えると速い. n が思いの外大きかったのでTLEに気をつけよう

a_i = b_i - \sum_{j=i}^{N} (-1)^{j-i}*a_j

を求めるんだけど, 総和の部分は以下のソースコードのように反転させながら足していかないとTLEする(2敗)

SourceCode

今回からSolve関数のみとなります

void solve() {
	int N = in();
	vector<int> b = in(N);
	vector<int> res(N);

	int add = 0;
	res[N - 1] = b[N - 1];
	add += res[N - 1];

	RFOR(i, 0, N-1) {
		add *= -1;
		res[i] = b[i] - add;
		add += res[i];
	}

	REP(i, N) cout << res[i] << (i == N - 1 ? "\n" : " ");
}

c++でpython風のinput()を作った(戻り値型推論的なやつ)

Motivation

int i = input();
string s = input();

みたいなのをしたい気分になった

SourceCode

以下のやつをコピペすれば動きます

struct input_returnner { template<typename T>operator T() const { T t; cin >> t;   return t;} };
input_returnner input() { return input_returnner(); }

/// ---template---

int main(void) {
    string a = input();
    cout << a << endl;
    return 0;
}

簡単な解説

変換演算子を持つ独自クラスを返すクラスを作って, input_returnner{} とかでもかけるんだけどクッソ気持ち悪かったので関数で囲ってやった

あとがき

でも

vector<int> v(N); for(auto &a:v) cin >> a;

って普段やってるしあまり活躍しなさそう

参考文献

C++で戻り値の型推論 • C言語交流フォーラム ~ mixC++ ~