AtCoder Grand Contest046-B Extension 解説
実質1行のDPなんですが、コンテスト後のTLを観たら結構いろんな解き方がされていて、割と自分の実装は短く済んでいる方だということがわかったので結論だけ簡単に示しておこうと思います。
問題ページ：https://atcoder.jp/contests/agc046/tasks/agc046_b
解法
dp[i][j] := 縦iマス、横jマスの長方形になった時の黒マスの塗り方 とします。i < A or j < B ならdp[i][j] = 0です（なぜなら最初から縦Aマス、横Bマスの状態で出発し、サイズが小さくなることはないから）。また、dp[A][B] = 1です。求める答えはdp[C][D]です。
現在、縦(i - 1)、横jの長さの長方形ができているとします。この時、「横」を選んで、縦方向に1拡張する操作を操作Aとしましょう。操作Aの結果新たに塗られる黒いマスの塗り方は、j通りです。 同様に、縦i、横(j - 1)の長さの長方形に対して「縦」を選んで横方向に1拡張する時新たに塗られる黒いマスの塗り方はi通りです（この操作を操作Bとします）。
縦i、横jの長方形にたどり着く直前の操作は上述の操作AまたはBのいずれかに限られます。ところで、操作Aで拡張された長さjの辺において、一番右端のマスを黒く塗った場合、それによって得られる長方形の模様は操作Bからは絶対に得られないことがわかります（なぜなら、操作Bを行う前に、縦の長さはiになっており、その時点で、横幅(j-1)の長方形グリッドの一番上の行のどこかは必ず黒マスになっているからです）操作Bで一番上のマスを黒く塗った場合も同様です。
一方で、操作Aで拡張された長さjの辺において、一番右端以外のマスを黒く塗って得られる長方形の模様は、操作Bからも得られます。操作Bも同様です。
これらの考察から、はじめに操作A、操作Bによって得られうる長方形の模様を全部計算しておき、そこから、マス(i , j)を黒く塗らないような塗り方を引くことによって重複を取り除くことができます。実装は次の通りです。
mint dp[3030][3030]; // mint : modint class void solve(){ dp[a][b] = 1; for(int i = a + 1;i <= c ;i++){ dp[i][b] = dp[i-1][b] * (mint)b; } for(int i = b + 1;i <= d ;i++){ dp[a][i] = dp[a][i-1] * (mint)a; } for(int i = a + 1;i <= c ;i++){ for(int j = b + 1;j <= d ;j++){ dp[i][j] = dp[i][j-1] * (mint)i + dp[i-1][j] * (mint)j - (mint)((i-1)*(j-1))*dp[i-1][j-1]; } } cout << dp[c][d] << '\n'; }
(i-1)*(j-1)*dp[i-1][j-1]は、縦(i-1)、横(j-1）の長方形を縦と横にそれぞれ1ずつ拡張して、拡張された辺に1つずつ黒マスを付ける付け方を数えています。書いておいてなんですが改めて見るとこれで通るのはちょっと不思議な感じがしています。
Google Code Jam2020 Round1B参加記
今更ですが、GCJ R1Bが4/20 午前1:00（！）にあったので出場しました。流石に時間が遅いので出るか迷いましたが、別にレートがつくわけではないので（ABCもレートがつきませんでしたね）、爆死しても損はないと言うことでダメもとで出場しました。
結果
845位と言うことで、無事通過できました！ A問題のテストセット1、2と、B問題をフルマークして合計47点でした。Aはlargeを解きに行こうとして全くの嘘をやっていたので全く通らず、最終的に終了10分前にsmallを通すためのBFSシミュレーションでゴリ押しました。
Bの解説だけ以下記述します。
B問題
概要
2e9四方の正方形盤と、半径がA以上B以下の円形の的が与えられる。あなたは300回まで座標を指定して、そこが的の中心(CENTER)か、的の丸の中(HIT)か、丸の外かの情報を得ることができる。的の中心の座標（CENTER)を得よ。
GCJのインタラクティブ問題はテストランナースクリプトがpythonで与えられるのですが、自分はこのスクリプトの使い方がわからずqualからずっと放置していました。結局terminalで手でテストして送りました。
解法
この問題は制約が最大の本質で、Hiddenの制約を見ると与えられる半径は5e8以上1e9以下とあるので、(±5e8 or 0,±5e8 or 0)の 9点のいずれか一つは必ずHITになることがわかります。
まず1つのHITを得られた点を(X,Y)としましょう。そうすると、直線x = Xの上で、Xより左側とXより右側に「HITとMISSの境界」がただひとつ存在することがわかるので、その境界を二分探索して求めます。左側の境界をL、右側の境界をRとしましょう。すると、円の中心のx座標Cxは(R + L)/2として求められます。y座標についても同様に求めれば良いです。
//52行目から編集 #include <iostream> #include <limits.h> #include <algorithm> #include <bitset> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <list> #include <map> #include <numeric> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #include <queue> #include <unordered_map> #include <unordered_set> #include <cassert> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define rrep(i,n) for(int i=n-1;i>=0;i--) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define eb emplace_back typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vector<int> > vvi; typedef vector<vector<ll> > vvl; typedef pair<int,int> pi; typedef pair<ll,ll> pl; template<class T> bool chmin(T& a,T b){if(a > b){a = b;return true;}else return false;} template<class T> bool chmax(T& a,T b){if(a < b){a = b;return true;}else return false;} /////////////////////////////////////////////////////////// string s;//judge long long candr = 1e9 / 2; long long candx[9] = {0,1,1,0,-1,-1,-1,0,1}; long long candy[9] = {0,0,-1,-1,-1,0,1,1,1}; ll X,Y; bool output(ll x,ll y){ cout << x << ' ' << y << '\n'; cout << flush; cin >> s; if(s == "CENTER")return true; else return false; } void main2(){ // 9箇所のポイントを全部試す for(int i = 0;i < 9;i++){ ll x = candr * candx[i]; ll y = candr * candy[i]; if(output(x,y)){ return; }else if(s == "HIT"){ X = x,Y = y; break; } } //(x,y)から上下の境界ポイントを二分探索する ll ub = 1e9,lb = Y; while(lb + 1 != ub){ ll mid = (lb + ub)/2; if(output(X,mid)){ return; }else{ if(s == "HIT"){ lb = mid; }else{ ub = mid; } } } ll CYU = lb; ub = Y,lb = -1e9; while(lb + 1 != ub){ ll mid = (lb + ub)/2; if(output(X,mid)){ return; }else{ if(s == "HIT"){ ub = mid; }else{ lb = mid; } } } ll CYD = ub; ll ansY = (CYU + CYD)/2; ub = 1e9,lb = X; while(lb + 1 != ub){ ll mid = (lb + ub)/2; if(output(mid,Y)){ return; }else{ if(s == "HIT"){ lb = mid; }else{ ub = mid; } } } ll CXU = lb; ub = X,lb = -1e9; while(lb + 1 != ub){ ll mid = (lb + ub)/2; if(output(mid,Y)){ return; }else{ if(s == "HIT"){ ub = mid; }else{ lb = mid; } } } ll CXD = ub; ll ansX = (CXU + CXD)/2; output(ansX,ansY); } int main(void){ cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(20); int testcase;cin >> testcase; ll a,b;cin >> a >> b; for(int i = 1;i <= testcase;i++){ main2(); } return 0; } /* *!!CHECK!! * 制約をよく読め：まず最も愚直な解法を考えろ * intの掛け算をしてる場合：overflowは大丈夫？ * 制約の下限・上限は大丈夫？ * 木構造は一直線にした時TLEしない？ * */
次回Round2は5月？にあると思うので、せっかくのチャンスなので、Tシャツを目指して頑張ろうと思います。
Google Code Jam 2020 Round 1A参加記
こんにちは。今回はGCJ2020 Round1Aに参加した記録を残そうと思います。
私、lynmisakuraは、現在AtCoder水色、codeforces青色です。もちろんWorld Finalsに本気で出られるなどとは思っていませんし、Tシャツだって現実的には厳しいと思いますが、せめてR1突破ぐらいは達成できるのではないかと思い、Qualification Roundで42点分の問題を解いてRound1に進出しました。
GCJ Round1は、3回のラウンドに分けて実施され、Round A,B,Cそれぞれ異なる時間帯に開催されます。そのため、どの地域であっても一度は「人権のある」時間に参加できるよう、考慮されています。日本では、今回私が参加したAラウンドは午前10時（土曜日であることを考慮すると十分に人権時間と言えます）、Bラウンドは午前1時（流石に厳しいでしょう）、Cラウンドは午後1118時（訂正：思い切り間違ってましたすみません...）開催ですから、最も競プロerにとって出やすい時間はおそらくCラウンドということになると思いますが、せっかくなのでAラウンドから出る人も多かったと思います。ちなみにこのR1は、各回上位1500名がRound2に進出し、Aラウンドで落ちてしまてもBラウンド、Cラウンドと突破するまで全てのラウンドに出場することができます（逆に、一度でも上位1500に入ってしまうとそれ以降のRound 1には参加できないようです）。
結果は？
さて、ラウンド1Aに参加した結果ですが、
2889位、という、少々口惜しい結果となってしまいました。 今回の1500位は、A、Bの2完あたりにラインがあったようです。私は、A問題をなんとか全てのテストケースに大して正解することができましたが、B問題のvisible（制約の緩い）ケースのみに特化したコードを提出し、C問題に移ったものの、C問題において誤読をしてしまいvisibleすら解くことができませんでした。
A問題
最初に見たときにペナソニックパナソニックE問題を思い出しました（もちろん内容は異なるのですが...）
概要：A＊B＊Cのような、大文字とアスタリスクのみで構成された文字列が複数与えられる。＊は、0文字以上の任意の文字列で展開することができる。次の条件を満たす文字列Sを構成せよ：与えられた全ての文字列の＊を適切に展開することでSと等しい文字列を作ることができる。
はじめに、それぞれの文字列を [prefix] [other] [suffix] の3部分に分解して管理します。ここで、prefixとは、文字列を左から順番に見ていって最初に＊が出現する手前までの接頭辞を指します。同様にsuffixは、文字列中で最後に＊が出現した直後から文字列の末尾までの接尾辞を指します。otherは、最初に出現した＊から最後に出現する＊までの部分文字列です。
ここで、全ての文字列のprefixを纏めて見ると、prefixたちはすべて終端記号によって構成されているので、"AAB"をprefixとする文字列と"AAC"をprefixとする文字列とから同時に展開される文字列Sが存在し得ないことが明らかにわかります。つまり、全てのprefixはそれ自身より長いprefixの接頭辞であることが文字列Sの存在に対する必要条件です。
これと同様のことがsuffixについても言えます。
上述のprefix,suffixについてのチェックを突破したら、文字列Sは「構成可能」であることが、次の構成方法の存在によって言えます。最初の下準備で得られたotherの文字列たちは、必ず＊...＊の形をとっています（...の部分はemptyかもしれません）から、Sの中では、other文字列中の終端記号がその順番で一度以上現れれば良いことがわかります。例えば、otherが
＊ABC＊
＊ATCO＊DER＊
＊
＊TOP＊CO＊DER＊
のようなものであったら、 ABCATCODERTOPCODER とすれば良いです。
要するに、other中の終端記号を全部前から順番につなげていくだけで良いです。
以上の内容をコードにして提出すると通ります。考察自体はそれほど難しくありませんでしたが、非常にバグをたくさん産んでしまい、これを通すのに1時間以上かかってしまい、また朝食で得た体力をほとんど使い果たしてしまいました。下の実装はコンテスト中のACコードを少し綺麗に書き直したものです。
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define all(x) (x).begin(),(x).end() #define pb push_back #define eb emplace_back /////////////////////////////////////////////////// int n; int l,r; vector<string> pre,suf,mid; bool compare(const string& s1,const string& s2){ return s1.size() < s2.size(); } string get_pre(string& s){ int len = s.size(); for(int i = 0;i < len;i++){ if(s[i] == '*'){ l = i; return s.substr(0,i); } } } string get_suf(string& s){ int len = s.size(); for(int i = len - 1;i >= 0;i--){ if(s[i] == '*'){ r = i + 1; string res = s.substr(r,len - r); reverse(all(res)); return res; } } } string get_concat(){ string res = ""; for(auto s : mid){ for(char x : s){ if(x != '*')res += x; } } return res; } bool check_pre(){ for(int i = 1;i < n;i++){ if(pre[i].substr(0,pre[i-1].size()) != pre[i-1]){ return false; } } return true; } bool check_suf(){ for(int i = 1;i < n;i++){ if(suf[i].substr(0,suf[i-1].size()) != suf[i-1]){ return false; } } return true; } void main2(void){ cin >> n; pre.clear(),suf.clear(),mid.clear(); vector<string> a(n); for(int i = 0;i < n;i++){ cin >> a[i]; pre.push_back(get_pre(a[i])); suf.push_back(get_suf(a[i])); mid.push_back(a[i].substr(l,r - l)); } sort(all(pre),compare); sort(all(suf),compare); if(!check_pre() || !check_suf()){ cout << "*" << '\n'; return; } string A = pre[n - 1]; string B = get_concat(); string C = suf[n - 1];reverse(all(C)); cout << A + B + C << '\n'; } int main(void){ cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(20); int testcase;cin >> testcase; for(int i = 1;i <= testcase;i++){ cout << "Case #" << i << ": "; main2(); } return 0; }
B問題
概要：パスカルの三角形上において、通った数の和がNになるような長さ500以下のパスを構成せよ。
visibleは、Nが1000以下なので、各行の左から2列目、上から1,2,3,...となるような部分を上から順に拾っていくと、1,2,...,Kまでの和がK(K+1)/2となるので、余った部分は最左列に移って、1を回収して帳尻を合わせる、ということを実装しました。Hiddenは...多分数学か算数でパズルすると解けるんだろうなぁと思いつつ、考える気力をほとんど失ってしまっていたため解くことができませんでした。後半に体力を残すためにも前半でバグを発生させないような実装をすることが肝要であると思いました。一応、visibleの提出コードを下に書いておきます。
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define rrep(i,n) for(int i=n-1;i>=0;i--) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define eb emplace_back typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<vector<int> > vvi; typedef vector<vector<ll> > vvl; typedef pair<int,int> pi; typedef pair<ll,ll> pl; template<class T> bool chmin(T& a,T b){if(a > b){a = b;return true;}else return false;} template<class T> bool chmax(T& a,T b){if(a < b){a = b;return true;}else return false;} /////////////////////////////////////////////////////////// void main2(){ cout << '\n'; int n;cin >> n; vector<pair<int,int>> ans; if(n == 1){ cout << 1 << ' ' << 1 << '\n'; return; } n--; int k = 1; ans.eb(1,1); while(1){ if(k * (k+1) / 2 <= n and n < (k+1)*(k+2)/ 2){ break; }else k++; } for(int i = 2;i <= k + 1;i++){ ans.eb(i,2); } int need = n - k*(k+1)/2; if(need-- > 0)ans.eb(k + 1,1); for(int i = 0;i < need;i++){ ans.eb(k + 2 + i,1); } for(auto i : ans)cout << i.first << ' ' << i.second << '\n'; } int main(void){ cin.tie(0); ios::sync_with_stdio(false); //cout << fixed << setprecision(20); int testcase;cin >> testcase; for(int i = 1;i <= testcase;i++){ cout << "Case #" << i << ": "; main2(); } return 0; }
C問題
結局要求されている考察を全くできなかったので概要も書きませんが、多分visibleはシミュレーションをすると通るんだと思います。これぐらいは通したかったですが、多分通せても1500には入れなかったと思います。
まとめ
難しかったですが、楽しく、生を実感できる貴重な時間を与えてくれる競技プログラミングコンテストには日々感謝しています。
ここ最近の競技プログラミングは実装で詰まってしまうことが多く、どうにかバグを生まない実装の仕方や注意力アップを模索しています。今回のラウンドAで、上位1500人がごっそりといなくなるので次回のラウンドB、Cで突破を目指したいと思います。犠牲にできるだけの体力と生活習慣は#STAYHOMEあってのものですので、皆さんも不要不急の外出を控え、快適な競技プログラミングライフを送られることを願っています。最後まで御読みいただきありがとうございました。
2020/01/04
昼から酒を飲むなどしたあとコーヒーを決めてなんとかこどふぉに出た。案外頭は回ったが（9時スタートはAtCoderと同じなのでそれに体が慣れてるとは思う）紫は遠いと思った
今日の精進
codeforces
精進はしていないのでHello 2020で解いた問題だけ
https://codeforces.com/contest/1284/problem/A
まあ流石にやるだけ
https://codeforces.com/contest/1284/problem/B
ascendingな配列とそうでない配列を別々に考える、非ascendingな配列は最大と最小をそれぞれについてもっておけばそれを使うことで左側においた配列に対して右側においたとき全体がascendingになる配列の個数は二分探索で出せる
https://codeforces.com/contest/1284/problem/C
簡単な数学で前計算O(N)
Dみたいな区間をいじいじする問題は苦手なのでこれもちゃんと纏めて対策しないとなぁ（あとこどふぉで苦手なのが括弧列（文脈自由文法みたいなやつ））
2020/01/03
今日の精進
最近全然こどふぉを埋められていない...
AtCoder
400点なのにちょっと捻ったDPは全然書けない。最初1次元のDPで、1個前とK個前とを参照すればいいと思ってた
学生最強コン予選F。数列に対する数学の典型必須要素が詰まってるんだろうなと感じた（解説だけ読んだ、まだ通せていない）
これは簡単だった
2020/01/02（その2）
昨日ブログ書いたのが日付変わったあとだったのでこう言う題名になってしまった。書いてる途中で日付が変わってしまった
今日の精進
AtCoder
・冬休み中に数列の扱いについて「典型」を明文化できるように（ある程度）したいのでScoresの点数でソートして全部の問題をチェックしてピックアップして解くみたいなことをすることにした
解説を読んでお気持ちだけ理解した問題、記事たち
→ 蟻本を読んでmaxflow/mincutについてお気持ちだけなんとなく察したが、実装を習得するには達していない（ライブラリだけ持ってる状態）。典型らしいので冬休み中にマスターしたい
https://atcoder.jp/contests/arc099/tasks/arc099_d
→ 令和ABCーFにありそうなRollingHashの問題。変換の線形性から簡単な式変形で理屈はわかるがロリハが自分で書けないのでどこかでお勉強してからまたやる これも冬休み中にマスター
埋めた問題
https://atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_c
→ 昔解こうとして解けなかったやつ 不等式の連結を紙の上で並べてゴニョゴニョするの受験数学でよくあった（苦手だった）ことを思い出して懐かしさを覚える
あと何問か過去問の復習
2020/01/02
あけましておめでとうございます。もう1月2日になってしまいましたが、みなさん今年もよろしくお願いします。
感想1 歳を感じる。明らかに新年を作業的に迎えるようになってしまった。
感想2 新年早々飲酒をしましたが、生ゴミみたいな後味のビールを飲むと本当に気分が悪くなりますね
精進
AtCoder
大晦日あたりからの精進。具体的にはunratedになった例のABC149のEF。あのセットはどちみちEFが解けなくてBで2度もWAをはいた（）影響により冷えが確定していたのでunratedになって救われた部分もある。
https://atcoder.jp/contests/abc149/tasks/abc149_e
・二分探索で解けると言うのが想定解ではあるが、得点の和が高々105のオーダーしかないことから、得点の和で決め打ちしてそれを満たす手の出し方が何通りあるかを数える方針（こう言う視点の変え方は競プロで基礎的なはずだが...）をするとFFTが通る。原理はともかくFFTなんぞやは割と最近勉強したばかりなのでこれがきちんと出てこなかったのは残念であった。
https://atcoder.jp/contests/abc149/tasks/abc149_f
・こっちはコンテスト中に方針は立っていた（rated続行なら通せていたかもしれない）。ところで解説を見ると全方位木DPと言うらしいが、結局この問題は各頂点を根としたときの部分木の頂点数を数えることで算数すれば良いだけと言うことが比較的簡単な考察からわかるので、あとは根を0にしたときの各頂点の部分木の個数を一度計算しておけば、各の頂点を根に変えたときの部分木の頂点の計算は容易である。ここでやってることがReRootingなのか、まだよく分かってない
とりあえずこれを読んでお気持ちだけ分かった気になった
・大晦日に無理やり虚無を埋めまくってなんとか500ACに達した。できればstreakを一年つなげていきたいが、虚無埋めで繋ぐモチベーションも正直そこまでないので、途切れがちになってしまうかなぁ...
・今年は昨年ほとんど手を出していなかったyukicoderも埋めたい。codeforces埋めが本当はメインでやっていきたいが、問題文の英語は読めてもeditorialの英語が全く読めないので進捗があまり良くない...
