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
)
要約
行列 が与えられる.
個の要素には, すでに値が記入されている.
すべての値は, 以下の条件を満たさなければならない.
条件1. すべての範囲内のに対して,
条件2.
問題の変形
この問題では, 変形が重要です.
条件1の変形
条件1を変形すると,
となり, 左右同士の差は上下で等しいことがわかります。図の矢印方向の差が等しいということですね
上下で等しい 上下で等しい… と下へ下へつなげていくと, 結局同じ列どうしの比較だと, 行にかかわらず差が等しいことがわかります。
さすがに, 列が違うと差は変わってきます.(同じだと思ってた時期が私にもありました…)
ここで, それぞれの行の一番左の値() を 簡単のために とおき,
を とおきます.
すると, と表記できることがわかります.
は と置き換えると,
と簡単にすることができます。(画像つくり忘れたんですけど, 矢印が左端からそのマスまでたどり着いてるイメージですね)
詳しい証明は解説参照で, ざっくりいうと, 条件1が成立するためには,
すべての を満たすような, , が存在しなければならない.
ということになります.
条件2の変形
条件2は, 条件1と組み合わせて,
すべての で,
が成立する必要があります. 全通り試すともちろん時間が足りないので, 工夫が必要です.
実は, のとり方はuniqueではありません. 例えば, を+1したら, を-1したら良いです.
一番小さいところからスタートして(), 一番小さい値を足す(負の数)と, の最小値が求まり, これが0以上になればOKっぽそうです
実装方針
を求める.
グラフを使って求めます. とを頂点と捉えます.
その間を入力を使って
と をつなぐ重さの辺を貼ります.
この時辺と頂点の関係を, と定義します.
二変数なので, なにか一つ値を決めないといけません. 一つ値を適当に0(なんでもいいです)と決めると, あとは随時決まっていくのがわかると思います.
(例えば, , という風に辺が張られていたら, と定めると, は自ずと決まってきます)
こんな感じでDFSで求めていきます.
条件2
DFSと一緒に, xの最小値とyの最小値を更新しながら探索していきます.
xの最小値+yの最小値 < 0 ならば, "No" となります.
実装する上での注意点
xの最小値とyの最小値の初期値に注意しなければなりません
処理をするときに, のように描いていると, オーバーフローするのでこのような実装をするならば, 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'にして, それ以外は無視する と言った処理をすればよい.
この処理は, 回必ず行わなければならないので, 余ったやつも必ず処理をしなければならない。
まず, アルファベットを何周もさせることができるので, 残ったやつから'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
要約
が与えられる.
: Memoryさんの初期点数
: 相手の初期点数
: 1ターンにの点数を得ることができる
: 2tターン行う
Memoryさんがかつことができるのは何通りか(MOD 1e9+7)
以下のようなdpを組む
その時間(time)で, Memoryさんのスコア-相手さんのスコアがdiffのときの場合の数
更新方法は簡単で,
- sumはしゃくとり的にやって計算量を減らす.
- 要素数は なので注意する(1敗)
最終的に, の部分がMemoryさんが勝つ場合の数なので,
が答えになる
配列の最大要素, くらいとっとけばいいと思ったけどなんかうまくいかなかった.
また, このままだと負の要素にアクセスすることになるので適当にオフセットかける
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
やること
非縮退三角形とは, 以下の条件を満たす三角形(つまり普通の三角形) 三角形の辺の長さを とすると,
少し変形して, 辺に着目すると, 以下のような式になる
辺の長さを減らしていく方向に考えると, 他の辺を減らす量が減ってしまうことがあり, 貪欲に考えることができない.
しかし, 辺の長さを増やしていく方向に考えると, 増やせば増やすほど他の辺もいっぱい増やせるので貪欲に増やすことができる
不等号が含まない不等号なのに注意して,
となるようにする.
同様に, をから初めて順に大きくしていってになった時点で終了
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
要約
数列 が与えられる.
を満たすような を求めよ
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;
って普段やってるしあまり活躍しなさそう