Google Code Jamに今年もチャレンジ。
(昨年の: Google Code Jam 2018: Qualification Round - すぎゃーんメモ)
最近少しずつ AtCoder や LeetCode をC++で解く練習をしているので今回のQualification RoundもC++でチャレンジ
Foregone Solution
4 を無くせばいいだけなので 基本的に元の入力を残し 単純に 4 が出てきたときだけ 3 と 1 に分割すればいいかな、と。
0 が先頭に来るときだけ注意して後処理で消すなど
#include <bits/stdc++.h>
using namespace std;
pair<string, string> solve(string n) {
pair<string, string> answer("", "");
for (int i = n.length() - 1; i >= 0; --i) {
if (n[i] != '4') {
answer.first = n[i] + answer.first;
answer.second = '0' + answer.second;
} else {
answer.first = '3' + answer.first;
answer.second = '1' + answer.second;
}
}
while (answer.second[0] == '0') {
answer.second.erase(answer.second.begin());
}
return answer;
}
int main() {
int t;
string n;
cin >> t;
for (int i = 0; i < t; ++i) {
cin >> n;
auto answer = solve(n);
cout << "Case #" << i + 1 << ": ";
cout << answer.first << " " << answer.second << endl;
}
}
You Can Go Your Own Way
問題読んでしばらく考えて、、これはスタートとゴールを結ぶ対角線で対称に動けばいいだけでは…ということに気付いた。
単純に S と E を入れ替えたものを作ればいいだけだった。
#include <bits/stdc++.h>
using namespace std;
string solve(int n, string p) {
string answer;
for (int i = 0, l = p.length(); i < l; ++i) {
answer += p[i] == 'S' ? 'E' : 'S';
}
return answer;
}
int main() {
int t, n;
string p;
cin >> t;
for (int i = 0; i < t; ++i) {
cin >> n >> p;
cout << "Case #" << i + 1 << ": " << solve(n, p) << endl;
}
}
ここまで解いて予選通過ラインは超えたので満足してしまった。
Cryptopangrams
時間あれば解こう、と思って結局間に合わなかった。
素因数分解を正直にやると非常に厄介そうだけど、必ずすべての文字に対応する素数を因数にもつものが存在しているわけだし 作り方から考えると隣接する数値どうしの最大公約数をとれば因数は取れる、ということに気付いた。ユークリッド互除法は知っているのでそれは書ける。
そうして取れる素数たちを並べて対応する文字に置き換えていけばいけそう。
しかし最初が ABABC みたいな感じで 同じ数字が並ぶパターンを考慮していなくてハマった。そこは注意しないといけない。
そして大きな値にも対応できるよう多倍長整数で、と思って以下のようなのを書いた
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
namespace np = boost::multiprecision;
np::cpp_int gcd(np::cpp_int x, np::cpp_int y) {
return y == 0 ? x : gcd(y, x % y);
}
string solve(np::cpp_int a[], int l) {
np::cpp_int d, d0;
for (int i = 0; i < l - 1; ++i) {
if (a[i] == a[i + 1]) {
continue;
}
d0 = gcd(a[i], a[i + 1]);
while (i > 0) {
d0 = a[i--] / d0;
}
break;
}
d = d0 = a[0] / d0;
set<np::cpp_int> s { d };
for (int i = 0; i < l; ++i) {
d = a[i] / d;
s.insert(d);
}
vector<np::cpp_int> v(s.begin(), s.end());
string answer = "";
d = d0;
for (int i = 0; i < l + 1; ++i) {
for (int j = 0, ll = v.size(); j < ll; ++j) {
if (v[j] == d) {
answer += 'A' + j;
if (i < l) {
d = a[i] / d;
}
break;
}
}
}
return answer;
}
int main() {
int t, n, l;
cin >> t;
for (int i = 0; i < t; ++i) {
cin >> n >> l;
np::cpp_int a[l];
for (int j = 0; j < l; ++j) {
string s;
cin >> s;
a[j] = np::cpp_int(s);
}
cout << "Case #" << i + 1 << ": " << solve(a, l) << endl;
}
}
が、
Solution.cpp:2:44: fatal error: boost/multiprecision/cpp_int.hpp: No such file or directory
#include <boost/multiprecision/cpp_int.hpp>
^
compilation terminated.
がびーん。ダメなのか。
ということでそのまま Python3で書き直し。
def gcd(x, y):
return x if y == 0 else gcd(y, x % y)
def solve(a):
d0 = 0
for i in range(len(a) - 1):
if a[i] != a[i + 1]:
d0 = gcd(a[i], a[i + 1])
for j in range(i):
d0 = a[i - j] // d0
break
d = d0 = a[0] // d0
s = set([d])
for e in a:
d = e // d
s.add(d)
v = sorted(s)
d = d0
answer = ''
for i in range(len(a) + 1):
idx = v.index(d)
answer += chr(idx + ord('A'))
if i < len(a):
d = a[i] // d
return answer
t = int(input())
for i in range(t):
_, l = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ', l)]
print('Case #{}: {}'.format(i + 1, solve(a)))
以上
4問目はまだ開いてすらいない。余裕あったら挑戦してみよう。。。
Repository
github.com
