約1時間30分間気付かなかったミス
数を長さNで循環シフトさせて、その後の偶奇を知りたかった。
if((x - shift + N) % N % 2 == 0) ...
としなければいけないところを
if((x - shift) % 2 == 0) ...
とかしていた。
当たり前だが、((x mod m) mod n = x mod n)は一般には成り立たない。
例えば((9 mod 3) mod 2) = 0 だが、(9 mod 2) = 1。
今回の場合、1回考えて書き直したらこのバグは直っていたかもしれない。
書きなおすことも考えよう。
SRM 596 DIV1 本番
少し調子が悪かった。
Coding
Easy (250)
最初全くわからず、焦った。
なんていうか2倍の操作は共有されるけどそれ以外は独立だから全部独立に求めた後上手く合成すればいけるのでは？と考える。
とりあえずDPで(数 * 2倍を使った回数 -> 最小のインクリメント回数)を求める。
さて、それを合成するにはどうしたら…
2倍にする回数は全部で固定なのでそれを全部試せばいいんじゃね？と、解けた。
テストをしてから提出。
Medium (500)
全然わからず。とりあえず辞書順最小はN*60回判定するのでいいな、とかは考える。
なんかマッチングとかフローっぽいな、とか考えながらうまく進められずに時間が経つ。
その間にいろいろ考えた。
まず、各ビットでそれを含む数の個数は2以下である必要がある。また、各数同士の無向ペアに対して少なくとも1つビットを共有してなければいけない。つまりグラフを考えるとクリークである必要がある。
ここまでわかってもそれをどう適用したらいいかがわからず時間が経つ。そして残り25分くらいの時にやっと思いついた。
(ビット位置, 各ペア)の二部グラフを考えて、そのビット位置がそのペアに含まれることができるならそこに辺を張る。そして全てのペアを使うマッチングが存在するかどうかを判定する。
さて、どこに辺を張れるかをどのようにして決めればいいのか？これは残り10分くらいでやっと思いつけた。
まず、そのビットがこのペアのどちらか片方で既に決まっていて(subsetに含まれていたり、既に決定されている)、その値が0なら張れない。
また、このビットを既に決めている数が存在して、その数がこのペアのうちどちらでも無い場合も張れない。
あとすこし引っかかったところが。辞書順最小greedyとはいっても、(subset以外の列が辞書順最小 <-> (答え = subset∪subset以外)が辞書順最小)は成立するのか？とりえあえずは成立すると信じた。
残り5分程度。テストもしたが解法に自身が持てない。しかし時間も無くしょうがないので提出。
が、落ちた。
subsetが最初から条件を満たしてない(3要素に共通するビットがある)ケースで落ちているようだった。その判定を入れたら通った。
Challenge
greedy解法とか知らないのでEasyのgreedyっぽい人のを写して、自分のものと答えが合うことを確認しただけ。他に1人だけ落とされてた。
SystemTest
遅延らしい。さて、通るか…
Medium落ちた。うーん…
結果
Easy: 227.48 / 250
Medium: Failed System Test / 500
Challenge: 0/0 = +0
Division Place: 368 / 792
Rating: 1957→1906
コメント
練習しよう。
落ちた理由がわからなかったのは久しぶりな気がする。
テストすればわかったよなあ。「焦っていても」コーナーケースをきちんと考えてテストをするべきだ。と、テストの重要性を再認識した。もちろん、書きながら気づけたらいいのだけれど…
コード
Easy
#include <vector> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f using namespace std; struct IncrementAndDoubling { int getMin(vector <int> desiredArray) { static int dp[1001][11]; mset(dp, INF); dp[0][0] = 0; rer(i, 0, 1000) rer(j, 0, 10) { int x = dp[i][j]; if(x == INF) continue; if(i*2 <= 1000 && j+1 <= 10) dp[i*2][j+1] = min(dp[i*2][j+1], x); if(i+1 <= 1000) dp[i+1][j] = min(dp[i+1][j], x + 1); } int n = desiredArray.size(); int r = INF; rer(j, 0, 10) { int x = j; rep(i, n) x = min(INF, x + dp[desiredArray[i]][j]); r = min(r, x); } return r; } };
約40分気付かなかったミス
rep(j, a.size()) aa[a[j]] = 1;
とすべきところを
rep(j, a.size()) aa[j] = 1;
としていた。
解法がMaximumFlowであって、そっちがバグってるんじゃないかと思っていたが単純なミスだった。
解法・ライブラリ・変な所が間違ってるんじゃないかと思って確認して、それでもミスが見つけられなかったら、1回全体をきちんと見直すべきだ。
SRM 595 DIV1 本番
朝のSRM。少し眠くて心配だったが緊張で眠気は吹き飛んだ。
Coding
900がMedより簡単なこと稀にあるよなーとか考え、Medより前に900を開こうと考えた。
Easy (250)
最初に、「2^(他の[L[j],R[j] ]に被覆されないiの数)？」と考えた。実際にはこれは合っていた。
しかしどうもそれが納得できなくて、罠ありそうだなーと考えてしまった。
次に「同じ色で塗らないといけないセルをまとめて、そのグループの数を数えればいい？」とおもった。
これはUnionFind(無駄に動的)でやった。
何も塗られない場所のグループは1、それ以外は2を答えに掛け算する。
結構テストして、心配ながらも提出。
Hard (900)
まず期待値といえば期待値の線形性だよな、と考えた。
それには凸包を分解する。三角形分解を考えて、それを足せばいいんじゃないか？と思った。
しかし肝心の「この三角形が凸包の三角形分解」になる確率がわからず、さらにそれは重複して数えてしまうことに気づいた。
そしてわからなくなった。Mediumが時間かかるもので解けないとだめだと思い、あきらめてMediumへ。
Medium (500)
とりあえず左右を別個に「left[i][j] = 区間[i,j)で右側の連続するG(途中でminGreen個以上出てるならminGreenで固定)」と「right[i][j] = 区間[i,j)で左側の連続するG(同上)」というように2つ計算すればいいと、割と素直に考えられた。
これの計算は普通に区間を拡張してく感じで計算してけばいい。
さて、左と右を組み合わせなければいけない。
左の区間を[i,j]とすると、この区間に対応できる右の区間は{ [k,l) | j <= k, right[k][l] >= minGreen - left[i][j] }となる。これを高速に数えるにはどうしたらいいだろうか？
この答えも素直に思いつけた。Fenwick木を動的に使えばいい。tをFenwick木とする。
jを右端から左へ移動させる。ループ中では全てのlに対してtのright[j][l]の位置をインクリメントする。
その後各i,jに対してtの[minGreen - left[i][j],∞)のsumを求めればよい。このsumが答えとなる。
テストを何回かした。その時システムが不調でテストに時間がかかって、それで30ptくらい減った。しかしテストは重要なので良い。落ちたら0点なのだから、数十点で一喜一憂してはいけない。
Challenge
4人落とされてたけど、読んでもなんで落ちたのかわからなかった。その程度のChallenge力。これは改善すべき。
SystemTest
通ってよかった。
結果
Easy: 204.51 / 250
Medium: 379.92 / 500
Hard: Opened / 900
Challenge: 0/0 = +0
Division Place: 23/455
Rating: 1820→1957
コメント
練習を続けよう。Challenge練習もしたいところ。
今回はMediumを速く解けたのでよかったけれど、Hardを先に開くのはやはり自分には少し早い気もする。やめよう。
コード
謎コード
Easy
#include <vector> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) using namespace std; typedef long long ll; struct UnionFind { vector<int> data; UnionFind(int size_) : data(size_, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; struct LittleElephantAndIntervalsDiv1 { long long getNumber(int M, vector <int> L, vector <int> R) { int n = L.size(); UnionFind uf(M+1); rer(p, 1, M) { bool white = true; rep(i, n) white &= !(L[i] <= p && p <= R[i]); if(white) uf.unionSet(0, p); } rer(p, 1, M) rer(q, 1, M) { bool b = true; rep(i, n) { bool x = L[i] <= p && p <= R[i], y = L[i] <= q && q <= R[i]; if(x && y) b = true; if(x ^ y) b = false; } if(b) uf.unionSet(p, q); } ll r = 1; rer(p, 0, M) if(uf.root(p) == p) { if(uf.findSet(p, 0)) r *= 1; else r *= 2; } return r; } };
Medium
#include <string> #include <vector> #include <cstring> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define each(it,o) for(auto it = (o).begin(); it != (o).end(); ++ it) #define mset(m,v) memset(m,v,sizeof(m)) using namespace std; typedef long long ll; struct FenwickTree { typedef ll T; vector<T> v; FenwickTree(int n): v(n, 0) {} void add(int i, T x) { for(; i < v.size(); i |= i+1) v[i] += x; } T sum(int i) { //[0, i) T r = 0; for(-- i; i >= 0; i = (i & (i+1)) - 1) r += v[i]; return r; } T sum(int left, int right) { //[left, right) return sum(right) - sum(left); } }; struct LittleElephantAndRGB { long long getNumber(vector <string> list_, int minGreen) { string s; each(i, list_) s += *i; int n = s.size(); static short dpleft[2501][2501], dpright[2501][2501]; mset(dpleft, 0); rep(i, n) { dpleft[i][i] = 0; rer(j, i+1, n) { int x = dpleft[i][j-1]; if(x == minGreen) dpleft[i][j] = minGreen; else if(s[j-1] == 'G') dpleft[i][j] = x + 1 >= minGreen ? minGreen : x + 1; else dpleft[i][j] = 0; } } mset(dpright, 0); rer(j, 1, n) { dpright[j][j] = 0; for(int i = j-1; i >= 0; i --) { int x = dpright[i+1][j]; if(x == minGreen) dpright[i][j] = minGreen; else if(s[i] == 'G') dpright[i][j] = x + 1 >= minGreen ? minGreen : x + 1; else dpright[i][j] = 0; } } FenwickTree t(minGreen+1); ll r = 0; for(int j = n; j >= 1; j --) { rer(l, j+1, n) t.add(dpright[j][l], 1); rep(i, j) { int x = dpleft[i][j]; r += t.sum(minGreen - x, minGreen+1); //j <= l, dpright[l][k] >= minGreen - x } } return r; } };
SRM400〜594(今まで)のDIV1 Easy,Mediumを埋めた
見た問題の表 - antaの競技プログラミング練習日記
最近練習してなくて惨敗し続けていたのでむしゃくしゃしてやった。
さらにSRM400〜のHardをやろう。
ptrdiffの左右
(p - str)とかしてインデックスを求めることはそれなりにある。
しかしこれ(p - str)を(str - p)としても何の警告も出ない！(もしかしたらstrが配列の時は何かあるかも？)
(node - nodes)とか紛らわしい名前を使っていると、(nodes - node)としてしまっても気づきにくい。
SRM 589 DIV1 本番
一番自明なことに気づかないとかChallengeしない主義者！とか
Coding
Easy (250)
なんか変な解法を思いついて、それはExampleを通るものの、まあ嘘だなと思い考えなおす。
考えてみた：「文字aを文字bに変え、その後に文字bを文字cに変えることは意味がない」
考え：a→bのコストがx、b→cの独立のコストがyだとして、a→b, b→cの順番にやると一回目でx、二回目で(x+y)のコストがかかってしまう。それは独立にやった時の(x + y)以下なので、意味がない。
さて、推移が無いとするとサイクルも無いので、全ての書き換えを独立に考えることが出来る。
そうすると、書き換えがStarグラフの集合のグラフになる。
集合はUnionFindでやって、それぞれのStarに対して真ん中をgreedyに選べば良い。
結構時間かかってしまった。
Medium (450)
最初にどうせ2部マッチングとかフローとかだろ、とか思ってた。
しかしどうも考えをまとめることができなくて、フローのグラフを試行錯誤したりして時間を潰していた。
そのうち、これ頂点被覆か？と思った。
それぞれの色に対して方向を全探索して、「辺があって向きが同じ2点」に辺を張る。
でも頂点被覆とかNP-Hardだろーとか思って指数時間アルゴリズムが問題の制約でなんかあれなのかなーとか思いながらタイムアウト。
結局、本当に自明に二部グラフなのであった。
何故なら、3つとも同じ向きということは無意味だからでからである。絶対向きをバラけさせたほうが良いので。これが感じられなかった。
そして、頂点被覆と考えても独立集合と考えても(たぶん)良い。
Challenge
Easy絶対落とせるだろうなーと眺めて、怪しいgreedyをいっぱい見つける。
しかし考えているうちにどんどん他の人に落とされていく。
他の人のChallengeも遅くて、考えてケースを作れる十分な時間の余裕があったのにもかかわらず、何もできない。
結局他の人に8Challengeをされた。
SystemTest
Easyは通った。みんなMedium解けてるし、Easy点数低すぎる。
結果
Easy: 183.16/250
Challenge: 0/0 = +0
Division Place: 261/758
Rating: 2045→2015
コメント
レーティングは順調に下がっていて
コード
Easy
#include <string> #include <vector> #include <algorithm> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define INF 0x3f3f3f3f using namespace std; typedef vector<int> vi; struct UnionFind { vector<int> data; UnionFind(int size_) : data(size_, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; struct GooseTattarrattatDiv1 { int getmin(string S) { int n = S.size(); UnionFind uf(26); rep(i, n/2) { char a = S[i], b = S[n-i-1]; uf.unionSet(a-'a', b-'a'); } int r = 0; for(int a = 0; a < 26; a ++) if(uf.root(a) == a) { vi v; for(int b = 0; b < 26; b ++) if(uf.findSet(a, b)) v.pb(b); int x = INF; each(i, v) { int y = 0; each(j, v) if(*i != *j) y += count(all(S), (char)('a' + *j)); x = min(x, y); } r += x; } return r; } };
