GCJ 2問
JOI 1問
Google Code Jam 2020 Round 1A A - Pattern Matching
問題
prefixとsuffixさえ合ってたら適当に繋げて答えが得られる。サンプルが豊富で助かる、Google社最高
提出
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
for (int i = 0; i < sz(v); i++) {
os << v[i];
if (i < sz(v) - 1) os << " ";
}
return os;
}
int main() {
int t;
cin >> t;
for (int _ = 1; _ <= t; _++) {
cout << "Case #" << _ << ": ";
int n;
cin >> n;
vector<pair<int, string>> left(n), right(n);
string ans = "";
rep(i, n) {
string s;
cin >> s;
string l = "", r = "";
while (sz(s)) {
if (s.back() == '*') {
s.pop_back();
break;
} else {
r += s.back();
s.pop_back();
}
}
reverse(all(r));
reverse(all(s));
while (sz(s)) {
if (s.back() == '*') {
s.pop_back();
break;
} else {
l += s.back();
s.pop_back();
}
}
reverse(all(l));
reverse(all(s));
for (char c : s) {
if (c != '*') ans += c;
}
left[i] = make_pair(sz(l), l);
right[i] = make_pair(sz(r), r);
}
sort(all(left));
reverse(all(left));
sort(all(right));
reverse(all(right));
bool ok = 1;
string ans1 = left[0].second;
rep(i, n) {
string t = left[i].second;
ok &= t == ans1.substr(sz(ans1) - sz(t), sz(t));
}
string ans2 = right[0].second;
rep(i, n) {
string t = right[i].second;
ok &= t == ans2.substr(sz(ans2) - sz(t), sz(t));
}
reverse(all(ans1));
cout << (ok ? ans1 + ans + ans2 : "*") << endl;
}
}
Google Code Jam 2020 Round 1A B - Pascal Walk
問題
パスカルの三角形の
段目の総和は
なので、
を2進で表したときにの位が
なら段目を全部取る、みたいな作戦でいけそう。実際は素通りする段ものマスを通らなきゃだめなので、あらかじめから
くらい引いておいて、最後に両端ので帳尻を合わせた。
提出
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
for (int i = 0; i < sz(v); i++) {
os << v[i];
if (i < sz(v) - 1) os << " ";
}
return os;
}
int main() {
int t;
cin >> t;
for (int _ = 1; _ <= t; _++) {
cout << "Case #" << _ << ": " << endl;
int n;
cin >> n;
if (n <= 500) {
for (int i = 1; i <= n; i++) cout << i << " " << 1 << endl;
continue;
}
bool left = 1;
vector<pair<int, int>> ans;
int sum = 0;
int m = n - 32;
for (int i = 0; i <= 30; i++) {
if (m >> i & 1) {
if (left) {
for (int j = 1; j <= i + 1; j++) {
ans.emplace_back(i + 1, j);
}
} else {
for (int j = i + 1; j >= 1; j--) {
ans.emplace_back(i + 1, j);
}
}
left ^= 1;
sum += (1 << i);
} else {
if (left) {
ans.emplace_back(i + 1, 1);
} else {
ans.emplace_back(i + 1, i + 1);
}
sum += 1;
}
}
rep(i, n - sum) {
if (left)
ans.emplace_back(32 + i, 1);
else
ans.emplace_back(32 + i, 32 + i);
}
assert(sz(ans) <= 500);
for (auto p : ans) cout << p.first << " " << p.second << endl;
}
}
JOI2008本選 B - 共通部分文字列
問題
共通部分文字列の長さで二分探索した。
提出
コメント
GCJ2020 Round1A通過🎉
