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あってのものですので、皆さんも不要不急の外出を控え、快適な競技プログラミングライフを送られることを願っています。最後まで御読みいただきありがとうございました。
