赤色を1, 白色を0とする。すると4種類のコマは
0 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0
となる。要するに、左右と上下は独立。
ここで、線がつながってることに注目。すると、とある列/行だけ取り出した時の値は
0 1 1 0 0 1 1 0 0 1 ... みたいになってる。つまり最初が0か1かでその列は一意に決まる。
よって、本質的には長さHの数列 a_i とWの数列 b_i だけを考えれば良い。値は0か1だけである。
よって、サイクルがあるとNGという条件を無視すると、答えは 2H+W.
ここで、"サイクルがある"と"長さ4のサイクルがある"は同値であることに注目。証明は略。
そして、"長さ4のサイクルがある" と "a_i = a_i+1, b_j = b_j+1, ((a_i) + j) % 2 == ((b_j) + i) % 2, なるi, jが存在"は同値であることが示せる。
あとはちょっと実装が重いDP。
大反省。
チームとしての性能がヤバかった。今回で言えば、うまく動けば7問は解けていた(そもそもG以外は正しい解法が出ていた)のに、-2問、もちろん完璧に動くのは無理だけど、それでも許せるのはせいぜい-1問だと思う。
僕個人の話だけど、なぜかDEを連続で実装して、バグらせた。(そもそもCを任せたのもpirozさんに連続実装させていて意味不明すぎる。何をやりたかったんだろう。意味不明。pirozさんごめん。)
自画自賛みたいになるけど、チームとして出来てくれば相当強いチームになるとは思う、3ヶ月あるのでボチボチ頑張りたい。
なんかチーム練習でもそうだったんだけど、実装力<<解法力っぽくて、常に実装待ちキューに数問溜まっている。ただ実装するべき問題をうまく選べていない感はある。これを直せば実力急上昇↑↑
今回激ビエしたので、激ビエポイントを使い果たした→つまりアジアは？？？
Matrix Calculatorとは、知る人ぞ知るアホ問題です。
サンプルを見ただけで嫌になるすごい問題なんですが、今回はパーサジェネレーターで楽々解決を目指します。
使用したのは
です。C++でのソースコードが出力に出てくるので、プロコンにうってつけですね。
まず、構文ファイルがこちら。
%token Digit<V> Var<V> Add Mul Sub Space LBranket RBranket LMatBranket RMatBranket SemiColon Comma Quote; %namespace calc; Expr<V> : [Identity] Term(0) | [MakeAdd] Expr(0) Add Term(1) | [MakeSub] Expr(0) Sub Term(1) ; Term<V> : [Identity] Fact(0) | [MakeMul] Term(0) Mul Fact(1) ; Fact<V> : [Identity] Prim(0) | [MakeNot] Sub Fact(0) ; Prim<V> : [Identity] Inum(0) | [Identity] Var(0) | [Identity] Mat(0) | [Identity] IdxPrim(0) | [Identity] LBranket Expr(0) RBranket | [Identity] TransPrim(0) ; IdxPrim<V> : [MakeIdx] Prim(0) LBranket Expr(1) Comma Expr(2) RBranket ; TransPrim<V> : [MakeTrans] Prim(0) Quote ; Mat<V> : [Identity] LMatBranket RowSeq(0) RMatBranket ; RowSeq<V> : [Identity] Row(0) | [RowMerge] RowSeq(0) SemiColon Row(1) ; Row<V> : [Identity] Expr(0) | [ColumMerge] Row(0) Space Expr(1) ; Inum<V> : [Identity] Digit(0) | [InumMerge] Inum(0) Digit(1) ;
長いですが、問題文のBNFをほとんどそのまま書き下しただけです。でも20分ぐらいかかった。
次にソースがこちら
#include <iostream> #include <algorithm> #include <array> #include <vector> #include <cassert> using namespace std; using ll = long long; using ull = unsigned long long; template<uint MD> struct ModInt { uint v; ModInt() : v(0) {} ModInt(ll v) : v(normS(v%MD+MD)) {} uint value() {return v;} static uint normS(const uint &x) {return (x<MD)?x:x-MD;}; static ModInt make(const uint &x) {ModInt m; m.v = x; return m;} const ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));} const ModInt operator-(const ModInt &r) const {return make(normS(v+normS(MD-r.v)));} const ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);} const ModInt operator-() const {return make(normS(MD-v));}; ModInt& operator+=(const ModInt &r) {return *this=*this+r;} ModInt& operator-=(const ModInt &r) {return *this=*this-r;} ModInt& operator*=(const ModInt &r) {return *this=*this*r;} static ModInt inv(const ModInt &x) { return pow(ModInt(x), MD-2); } }; template<class D> struct Matrix { vector<vector<D>> d; int N, M; Matrix() {} Matrix(int N, int M) : N(N), M(M), d(vector<vector<D>>(N, vector<D>(M, D(0)))) {} vector<D>& operator[](int p) {return d[p];} const vector<D>& operator[](int p) const {return d[p];} const Matrix operator+(const Matrix &right) const { assert(right.N == N && right.M == M); Matrix res(N, M); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { res[i][j] = d[i][j]+right[i][j]; } } return res; } const Matrix operator-() const { Matrix res(N, M); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { res[i][j] = -d[i][j]; } } return res; } const Matrix operator*(const Matrix &right) const { if (N == 1 and M == 1) { return right * d[0][0]; } if (right.N == 1 and right.M == 1) { return *this * right[0][0]; } assert(M == right.N); Matrix res(N, right.M), r(right.M, right.N); for (int i = 0; i < right.M; i++) { for (int j = 0; j < right.N; j++) { r[i][j] = right[j][i]; } } for (int i = 0; i < N; i++) { for (int j = 0; j < right.M; j++) { for (int k = 0; k < M; k++) { res[i][j] += d[i][k]*r[j][k]; } } } return res; } const Matrix operator*(const D &x) const { Matrix res(N, M); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { res[i][j] = d[i][j]*x; } } return res; } }; using V = Matrix<ModInt<(1<<15)>>; #include "parser.hpp" class unexpected_char : public std::exception {}; struct SemanticAction { void syntax_error() {} void stack_overflow() {} void downcast(V& x, V y) { x = y; } void upcast(V& x, V y) { x = y; } V Identity(V n) { return n; } V MakeNot(V n) { return -n; } V MakeMul(V x, V y) { return x * y; } V MakeAdd(V x, V y) { return x + y; } V MakeSub(V x, V y) { return x + (-y); } V MakeTrans(V x) { V res(x.M, x.N); for (int i = 0; i < x.N; i++) { for (int j = 0; j < x.M; j++) { res.d[j][i] = x.d[i][j]; } } return res; } V MakeIdx(V d, V x, V y) { V res(x.M, y.M); for (int i = 0; i < x.M; i++) { for (int j = 0; j < y.M; j++) { res[i][j] = d[x[0][i].v-1][y[0][j].v-1]; } } return res; } V RowMerge(V x, V y) { assert(x.M == y.M); V res(x.N+y.N, x.M); for (int i = 0; i < x.N; i++) { for (int j = 0; j < x.M; j++) { res.d[i][j] = x[i][j]; } } for (int i = 0; i < y.N; i++) { for (int j = 0; j < y.M; j++) { res.d[x.N+i][j] = y[i][j]; } } return res; } V ColumMerge(V x, V y) { assert(x.N == y.N); V res(x.N, x.M+y.M); for (int i = 0; i < x.N; i++) { for (int j = 0; j < x.M; j++) { res.d[i][j] = x[i][j]; } } for (int i = 0; i < y.N; i++) { for (int j = 0; j < y.M; j++) { res.d[i][x.M+j] = y[i][j]; } } return res; } V InumMerge(V x, V y) { V res(1, 1); res[0][0] = x[0][0] * 10 + y[0][0]; return res; } }; V var[26]; class scanner { public: using char_type = char; private: string s; int pos; public: scanner(string s) : s(s), pos(0) {} calc::Token get(V& v) { char c = getc(); switch (c) { case '+': return calc::token_Add; case '*': return calc::token_Mul; case '-': return calc::token_Sub; case ' ': return calc::token_Space; case '(': return calc::token_LBranket; case ')': return calc::token_RBranket; case '[': return calc::token_LMatBranket; case ']': return calc::token_RMatBranket; case ';': return calc::token_SemiColon; case ',': return calc::token_Comma; case '\'': return calc::token_Quote; case '.': return calc::token_eof; } if (isdigit(c)) { v = V(1, 1); v[0][0] = c - '0'; return calc::token_Digit; } if ('A' <= c and c <= 'Z') { v = var[c - 'A']; return calc::token_Var; } cerr << c << endl; throw unexpected_char(); } private: char_type getc() { if (pos == s.size()) return EOF; return s[pos++]; } }; int main() { while (true) { int n; cin >> n; cin.ignore(); if (n == 0) break; V last; for (int i = 0; i < n; i++) { string s; getline(cin, s); int VC = s[0] - 'A'; s = s.substr(2); scanner scn(s); SemanticAction sa; calc::Parser<V, SemanticAction> parser(sa); calc::Token token; while (true) { V v; token = scn.get(v); if (parser.post(token, v)) { break; } } V v; if (parser.accept(v)) { var[VC] = v; last = v; } for (int i = 0; i < last.N; i++) { for (int j = 0; j < last.M; j++) { printf("%d", last.d[i][j].v); if (j != last.M-1) { printf(" "); } else { printf("\n"); } } } } printf("-----\n"); } return 0; }
自動mod取り構造体やら行列やらを使いまくっているので読むのが大変。
ACしてません。出力がインデントを消しても40kbyteぐらいあって、AOJに投げられません。残念。
実装時間も63分かかったようです。
ですが、構文解析部分がバグらないというのは非常に強く、デバッグ時間は10分程度です。(サンプルが通っただけなので実際に正しいかはわかりません) かなり強力なんじゃないかと思いました。(ICPCではもちろん使えないんだけど…)
本質部分は、1~Kのうち、gcd(x, K)=1なるxの二乗和。(K <= 1,000,000,000)
Kの素因数を列挙して適当に包除すれば良い。
Hardを頑張ってちょいちょい解いていきたい。メモ。
[0, A)のフィボナッチ表現のi桁目の立っているbitの個数の偶奇がわかれば良い(いつもの)
桁を固定して考えると、直感的にフラクタル的な感じになりそう…と決めうちして考えると、フィボナッチ文字列みたいになっていることがわかる
あとは適当に計算すればOK。計算量はO(log2)かlog3か
3*Nの行列が与えられる。
K回、以下の動作ができる。
どういう行列なら、すべての値を0以下にできるか？
というのが本質部分です。
これについて考えていたら、面白い結論が出たのでメモします。
実は、すべての列とすべての行について値の総和がK以下であることが必要十分です。
N*Nの値が非負整数の行列が与えられる。
K回、以下の動作ができる
どのような行列ならばすべての値を0にできるか？
実はこの問題も同様に、すべての列と行について値の和はKであることが必要十分になるはずです。
数学的帰納法で考えると、以下のような問題になります。
N*Nの行列が与えられ、すべての列と行について和の値はKである。
以下の条件を選ぶようにマス目をN個選べるか？
こういう選び方をすれば、K -> K-1という遷移ができるのでOKです。
ここで、ネットワークフローを考えます。
左に頂点がN個、右に頂点がN個あります。s -> 左の頂点の容量と、右の頂点 -> tの容量は全て1、さらに、左の頂点から出て行く辺の容量と右の辺に流れ込む辺の容量の和は全てK。このようなグラフで必ず最大マッチングはNとなることがわかればOKです。
ですが、これはホールの結婚定理を使うときれいに示せます。左側の頂点を幾つか選んだ時に、対応する右側の頂点の集合の数は、辺の容量の和の制約から必ず左側の選んだ数より大きくなるからです。
これが言えると元の問題が解けるのか？というと非自明です。(これだけでもD1easyくらいはありそう)
以下白字(にしたかったんですが、画像はどうしようもない)
3*Nの行列について、(列と行の値の和がK以下 => K回の取り除く動作で全て0以下になる)
が言えれば良い(逆は自明)。
3*Nの行列を、(3+N) * (3+N)の行列へ拡張することを考える。
まず、3N -> 3(N+3)への拡張だが、これは下図のようにする。
いい感じにa, b, cを設定することで、行ごとの和が全てKになるようにできる。
このあと、下にN*(3+N)をくっつけるが、これもいい感じに加えると、全ての列の和がKになるようにできる。
これは一般化した問題なので、K回の取り除く動作で全部の値が0に出来る。その操作を3*Nの行列について取り出せば、いい感じ。
