CodeChef の勧め 〜インド入門〜
みなさんこんにちは.お久しぶりです.
競プロ er の中では,よくインドという風な呼ばれ方をすることで有名な?CodeChef について説明していこうと思います.
CodeChef は AtCoder と同様有志コンテストと公式の rated コンテストが分かれています.
主に,公式の rated コンテストについて説明していこうと思います.
公式コンテストは現在主に毎月 4 回行われており,
- Starters
- Challenge
- Cook-off
- Lunchtime
があります.これに加えて,数回 rated が加わる月もあります.
よく,インドはカスだという印象があるかもしれませんが,公式の rated コンテストはかなりまともです.
共通のルール
基本的に register はありません.イメージとしては, yukicoder に近くて,時間になったら問題が表示されて,解いていくシステムです.
フルフィードバックです.全てのテストケースに対して,ジャッジが行われ,その結果が帰ってきます.hack や challenge などの他人の submit を攻撃するシステムはないです.ただ,その結果に対してどの程度の情報が得られるかはコンテストごとに違います.Starters はほとんど出たことがないのでわからないですが,Cook-off は全てに対する結果のみ,Challenge と Lunchtime はそれぞれのテストケースの結果が得られます.Codeforces などと同様に, Div. ごとに分かれています.
- Div. 1 (2000-)
- Div. 2 (1600 - 1999)
- Div. 3 (-1599)
という感じです.Div. の実力の分かれ方はほぼ CF と同じという体感があります.
Starters
最近始まりました. Div. 3 のみが rated で初心者向けのコンテストです.あまり出たことないので,細かいルールは知りませんが,難易度はだいたい CF の CR (rated for Div. 3) より少し優しいかなーぐらいのイメージです.
Challenge
10 日間のコンテストです. ルールは,ペナルティなし,時間なしの点数のみで順位が決まります.つまり,同じ点数なら,同じ順位です.subtask 形式で,部分点が存在します.アルゴ + マラソン のコンテストです.アルゴ + マラソンといっても,APRIL21 だと,9 割がアルゴで, 1 割がマラソンです.個人的な印象で言うとほぼアルゴで順位が決まります.
Cook-off
(最近は) 180 min のアルゴのコンテストです.ルールは,CF の ECR とほぼ同じで,AC 数が多い方が順位が高く,AC 数が同じなら累積の時間で順位が決まります. ペナルティは 10 分です.
Lunchtime
180 min のアルゴのコンテストです.ルールは,イメージで言うと OI ルールです.点数が多い方が順位が高く,点数が同じなら最後の点数獲得時間で順位が決まります. ペナルティはありません. subtask 形式で,部分点が存在します. Um_nik や 300iq が admin をしているのが Lunchtime の特徴でもあります.
有志コン
ほぼ毎日やっています.ジャッジが間違っている,サンプルが間違っているなどはもちろんのこと,問題文がほぼないや,順位表が壊れてるなどもあります.これはこれで面白いのでおすすめです.ジャッジとの正真正銘エスパーバトルです.
Laddus
CodeChef 内のお金で,順位が良かったりするともらえます.これは有志コンでもらえることもあります.
CodeChef のグッズがもらえたりもします.
Codeforces Round #715 (Div. 1) C. Complete the MST
解説
補グラフにおいて, 1 つは XOR の値を,それ以外は全て 0 として損をしません.
補グラフにおける辺をいったん全てコスト 0 としてすべてつなげます.そして,元のグラフの分をクラスカル法の要領でくっつけていきます.
補グラフにサイクルを含むとき
サイクルの 1 つに XOR の値をおしつければいいので,捕グラフの辺のコストを全て 0 と考えても問題なく,おしまいです.
補グラフが森の時
このとき,捕グラフでつなげた連結成分のどこかの1つを加算しなければなりません.加算するのは, XOR と 補グラフの連結成分の頂点組であり,元のグラフでクラスカルの要領でくっつけた辺だけでは連結ではない頂点組のコスト最小値の小さい方です.
実装例
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <utility> #include <tuple> #include <cmath> #include <numeric> #include <set> #include <map> #include <array> #include <complex> #include <iomanip> #include <cassert> #include <random> #include <valarray> using ll = long long; using std::cin; using std::cout; using std::endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int inf = (int)1e9 + 7; const long long INF = 1LL << 60; namespace KKT89 { struct UnionFind { std::vector<int> par; UnionFind(int n) { par.assign(n, -1); } int root(int a) { if (par[a] < 0) { return a; } return par[a] = root(par[a]); } int size(int a) { return -par[root(a)]; } bool connect(int a, int b) { a = root(a); b = root(b); if (a == b) { return false; } if (size(a) < size(b)) { std::swap(a, b); } par[a] += par[b]; par[b] = a; return true; } bool same(int a, int b) { return root(a) == root(b); } }; } void solve() { int n, m; cin >> n >> m; std::vector<std::tuple<int, int, int>> edges; edges.reserve(m); std::vector<std::pair<int, int>> vp; vp.reserve(m); int XOR = 0; for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; u -= 1, v -= 1; if(u > v) std::swap(u, v); XOR ^= w; edges.emplace_back(w, u, v); vp.emplace_back(u, v); } std::sort(edges.begin(), edges.end()); std::sort(vp.begin(), vp.end()); auto edge_exist = [&](int u, int v) { if(u > v) std::swap(u, v); return std::binary_search(vp.begin(), vp.end(), std::make_pair(u, v)); }; std::set<int> s; for (int i = 0; i < n; ++i) { s.emplace(i); } KKT89::UnionFind uf1(n), uf2(n); int cnt = 0; for (int i = 0; i < n; ++i) { if(s.find(i) == s.end()) continue; std::queue<int> q; q.emplace(i); s.erase(s.find(i)); while(not q.empty()) { const int cur = q.front(); q.pop(); for(auto itr = s.begin(); itr != s.end();) { if(not edge_exist(cur, *itr)) { q.emplace(*itr); uf1.connect(cur, *itr); itr = s.erase(itr); } else { itr = std::next(itr); } } } cnt += 1; } int min = XOR; ll res = 0; for(const auto &[w, u, v] : edges) { if(uf1.same(u, v) and not uf2.same(u, v)) { chmin(min, w); } if(uf1.connect(u, v) and uf2.connect(u, v)) res += w; } if(n - (1LL * n * (n - 1) / 2 - m) == cnt) { res += min; } cout << res << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int kkt = 1; //cin >> kkt; while(kkt--) solve(); return 0; }
yukicoder Matrix Eraser
April Challenge 2021 PAIRFLIP
解説
問題文を 2 段階言い換えます.まず, と が 2 つあるのが大変なので 1 つにまとめます.
"""
が ? のときは, ? で,そうでない時は, となるグリッド を考えます.
このとき, の同じ行または同じ列の 2 つのセルを選んで,反転させる.( ? は ? のまま) から 1 が消えるために必要な操作回数が最小となるような操作の一例をあげよ.
"""
となります.1 を消す操作は主に 4 通りあって,上から順に得です.( 2 番目と 3 番目は同じ得レベル)
- 同じ行や列の 2 つの
1
を 1 手で0
にする. - 行や列を共有していない 2 つの
1
を 2 手で0
にする. ?
と同じ行や列の 1 つの1
を 1 手で0
にする.?
と行や列を共有していない1
を 2 手で0
にする.
3 番目と 4 番目の操作は ?
が存在するときにのみ使用できます.
グリッドのまま考えるのは大変です. グリッドの,x 座標と,y 座標を頂点とし,1
の x 座標と y 座標に 辺を貼った無向グラフ を考えてみます. このとき,次のように問題文を言い換えられます.
"""
となる頂点組において,辺がある状態とない状態を反転させる. このとき, ? のところを除き, 上から辺がなくなるために必要な操作回数が最小となるような操作の一例をあげよ.
"""
と言い換えます.これでグラフの問題になり,消せる条件が頂点に注目するだけになり見通しが良くなりました.各連結成分に注目します.次の事実が言えます.
"""
1 番目の操作のみだけで,連結成分の辺の数が偶数なら全て消せて,辺の数が奇数なら,1つ残すのみにすることができる.
"""
1 番目の操作は 2 本ずつ辺を削除するので,偶数の場合は全部消すのが,奇数の場合は 1 つ残すよりも良くすることができないです.次に可能なことを具体的な操作を構築することで示します. 上の図のように,DFS 木を取って,葉のほうから,辺を削除することを考えます.
注目してる頂点につながっている辺が偶数本の場合は,1 番目の操作で全て削除することができます.奇数本の場合を考えます.奇数本の場合どのように操作しても,1 番目の操作のみでは 1 本残ります.どの辺を残すかを考えます.子に辺が残っている場合,葉から見ていることから,ここで削除しないと削除できないので,削除するのが得です.後退辺と親につながる辺は,どちらを残していても,あとで消すことができますが,親につながる辺を残すことで,もし辺が残っているなら,DFS 木上の辺のみとなることから,実装上が楽なのでおすすめです.この操作を全部葉から繰り返していくことで,連結成分の辺の数が,偶数の場合は全て削除でき,奇数の場合は辺を 1 つ残すのみにすることが可能ということがわかります.
グラフ全体の辺の数に注目します.
グラフ全体の辺の数が偶数の時.
1 番目の操作をすることで,1 本辺が残っている連結成分は偶数個です.これらは,2 番目の操作をすることで,全て削除できるので,グラフ全体の辺の数が偶数の時は求めることができました.
グラフ全体の辺の数が奇数の時.
?
がないときは,どのように操作しても,2 つずつしか消せないので,1
を全て消すことはできません.以下,?
が存在する場合を考えます.3 番目の操作,または 4 番目の操作を (適切に) 1 度すれば,グラフ全体の辺の数が偶数の場合の話に帰着できます.3 番目の操作は 4 番目の操作より得であるので, 3 番目の操作を適用できる場合を考えます.連結成分の辺の数が偶数の連結成分には適用をするのは損です.連結成分の辺の数が偶数の連結成分は,操作 1 のみで全て削除することが可能だからです.よって,連結成分の辺の数が奇数の連結成分の辺に適用できるときは,1 度だけ 3 番目の操作を適用することで,グラフ全体の辺の数が偶数の時に帰着できます.3 番目の操作が適用できない時は, 4 番目の操作を適用し,グラフ全体の辺の数が偶数の時に帰着させて解くことができました.
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <utility> #include <tuple> #include <cmath> #include <numeric> #include <set> #include <map> #include <array> #include <complex> #include <iomanip> #include <cassert> #include <random> #include <chrono> using ll = long long; using std::cin; using std::cout; using std::endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const int inf = (int)1e9 + 7; const long long INF = 1LL << 60; namespace KKT89 { struct UnionFind { std::vector<int> par, edge; UnionFind(int n) { par.assign(n, -1); edge.assign(n, 0); } int root(int a) { if (par[a] < 0) { return a; } return par[a] = root(par[a]); } int size(int a) { return -par[root(a)]; } bool connect(int a, int b) { a = root(a); b = root(b); edge[a] += 1; if (a == b) { return false; } if (size(a) < size(b)) { std::swap(a, b); } edge[a] += edge[b]; par[a] += par[b]; par[b] = a; return true; } bool same(int a, int b) { return root(a) == root(b); } int get_edge(int a) { a = root(a); return edge[a]; } }; } void solve() { int n, m, E; cin >> n >> m >> E; std::vector a(n, std::vector<int>(m)); KKT89::UnionFind uf(n + m); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c; cin >> c; a[i][j] = c - '0'; } } //?のあるとこ std::pair<int, int> question(-1, -1); std::vector<int> R(n, -1), C(m, -1); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c; cin >> c; if(c == '?') { a[i][j] = -1; question = {i, j}; R[i] = j; C[j] = i; } else a[i][j] ^= (c - '0'); } } std::vector<std::vector<int>> g(n + m); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if(a[i][j] == 1) { uf.connect(i, n + j); g[i].emplace_back(n + j); g[n + j].emplace_back(i); } } } std::vector<bool> used(n + m); std::vector<int> dep(n + m); std::vector<std::tuple<int, int, int>> res; auto dfs = [&](auto&& self, const int cur, int pre, bool &f)->int { used[cur] = true; std::vector<int> v; for(const auto nxt : g[cur]) { if(not used[nxt]) { dep[nxt] = dep[cur] + 1; auto p = self(self, nxt, cur, f); if(p == 1) { v.emplace_back(nxt); } } else if(dep[nxt] < dep[cur]) { if(nxt != pre) v.emplace_back(nxt); } } int ret = 0; int que = -1; if(cur >= n and C[cur - n] >= 0) que = C[cur - n]; if(cur < n and R[cur] >= 0) que = R[cur] + n; bool usepre = false; if(f and que != -1 and (pre >= 0 or not v.empty())) { if(not v.empty()) { res.emplace_back(cur, que, v.back()); v.pop_back(); } else { usepre = true; res.emplace_back(cur, pre, que); } f = false; } for (int i = 0; i + 1 < (int)v.size(); i += 2) { res.emplace_back(cur, v[i], v[i + 1]); } if((int)v.size() % 2 == 1) { if(pre == -1 or usepre) { ret = 1; } else { res.emplace_back(cur, pre, v.back()); } } else { if(pre >= 0 and not usepre) ret = 1; } if(pre == -1 and ret == 1) { return v.back(); } return ret; }; int cnt = 0; for (int i = 0; i < n + m; ++i) { if(uf.root(i) == i) { if(uf.get_edge(i) % 2 == 1) { cnt += 1; } } } bool f = cnt % 2; std::vector<std::pair<int, int>> vp; for (int i = 0; i < n + m; ++i) { if(used[i]) continue; int r = 0; if(uf.get_edge(i) % 2 == 0) { bool t = false; r = dfs(dfs, i, -1, t); } else r = dfs(dfs, i, -1, f); if(r > 0) { if(i >= n) { vp.emplace_back(r, i); } else { vp.emplace_back(i, r); } } } if(question == std::pair<int, int>(-1, -1) and (int)vp.size() % 2 == 1) { cout << -1 << "\n"; return; } for (int i = 0; i + 1 < (int)vp.size(); i += 2) { res.emplace_back(vp[i].first, vp[i].second, vp[i + 1].second); res.emplace_back(vp[i + 1].second, vp[i].first, vp[i + 1].first); } if((int)vp.size() % 2 == 1) { res.emplace_back(question.first, question.second + n, vp.back().second); res.emplace_back(vp.back().second, question.first, vp.back().first); } cout << (int)res.size() << "\n"; if(E == 1) { for(auto [t, p, q] : res) { if(t >= n) { cout << "C " << t - n + 1 << " " << p + 1 << " " << q + 1 << "\n"; } else { cout << "R " << t + 1 << " " << p - n + 1 << " " << q - n + 1 << "\n"; } } } } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int kkt = 1; cin >> kkt; while(kkt--) { solve(); } return 0; }
各コンテストサイトのアカウントの消し方
AtCoder
マイプロフィール -> 設定 -> 退会
Codeforces
現状ではありません.
Mike は個人情報などを全て削除してから,放置をしておくことを推奨しています.
これは,ブログなどの情報はコメントを含めて消えるべきではないという考えかららしいです.
Topcoder
support@topcoder.com に登録したメールアドレスでメールを送ります.
1つは自動でメールが帰ってきます.
僕の場合は,わりとすぐに2通目のメールが来て,受け入れられました
CodeChef
Account -> Edit Profile -> Privacy -> I don't want to continue with CodeChef
からできます.
じゅぴろ
実はskebで絵を依頼してたんですが、なんと今日完成して届きました!
ちょ~かわいいい~
か。つくんのお友達という理由だけで頼んでたんだけど、かわいすぎてうれしい~
これを見ながら頑張って卒業をします