TeraCoder2019 反省
2019/11/30に開催されたTeraCoder 2019参加したのですが散々だったので反省(と軽く解説)を書きます。
気づいたら1ヶ月近く経ってました。びっくり
TeraCoder とは？
京都産業大学コンピュータ理工学部/情報理工学部で行われているプログラミングコンテストです。今年で7回目です。
研究室がいっぱい協賛してくれていて、上位入賞するとamazonギフト券が貰えます。
弊学、競プロ団体はないし(たぶん)(知らんだけかも)競プロer人口は少ないのですが、ICPC予選に25チームも参加してたり学内プロコンが行われたりしています。競プロに力入れてるのか入れてないのか分からないですね。
私の結果
10問中7問しか解けず、7位と言う悲しい結果になってしまいました。
悲しかったので次の日に落ち着いて解いてみたら全部解けてさらに悲しかったです。
ですが、今回7回目ということでラッキーセブン賞という賞があり、その上総合3位以下の3回生で一番早く問題を解いたので3回生部門1位もとれ、W受賞できちゃいました。
反省と感想
私は去年参加できなかったのでわかりませんが、一昨年よりかは簡単な気がしました。
しかし、簡単だったのにも関わらず3回生にもなって7問しか解けなかったのは結構悔しかったです…。
ちなみに私は速さで勝ちに行きました。
後で落ち着いて考えたら解けた問題や気づけた典型があって、これは最近全くコンテストに出ていないツケが回ってしまったなぁと感じました。
以下、1問1問反省と感想とちょっと解説を書いていきます。
コードの前提
- 参考にならないと思いますが、何となく貼ります。
- 言語はC++です。
- 私の解法なので、最適解でも想定解でもありません。
- 基本コメントはないです。
- メインは解説ではなく反省です。
- 基本的に全てのコードが汚いしコメントもないです。ごめんなさい。
- ヘッダー部分は以下のような感じです。
コード
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
A問題：ミニギャラリー
「if文って知ってますか？」という問題。もちろん知っているので書いて通します。
コード
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int L,R;
cin >> L >> R;
if(L == R){
cout << "EQUAL" << "\n";
}
else if(L > R){
cout << "LEFT" << "\n";
}
else if(R > L){
cout << "RIGHT" << "\n";
}
}
return 0;
}
B問題：京産デリバリー
おそらく「for文って知ってますか？」という問題ですがfor文知らなかったらA問題解くの難し過ぎませんか？
もちろん知っているので書いて通します。
コード
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int N;
cin >> N;
vector<int> P(N);
int ans = 200;
for(int i=0; i < N; i++){
int P;
cin >> P;
ans += P;
}
cout << ans << "\n";
}
return 0;
}
ちなみに、A問題やB問題のような全く考えなくてもいいような問題を競技プログラミング的には「やるだけ」と言います。どうでもいいですが。
C問題：カウンタ
なぜかこれは計算で解けるのでは？をしてしまいました。
愚直に2重for文問題でした。
嘘解法を考えたうえサンプルケースが間違っていることに気づけず無限に時間を溶かしました。
コード
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int N,P;
cin >> N >> P;
for(int i=0; i<N; i++){
int a;
cin >> a;
int ans = 0;
for(int j=0; j<P; i++){
if(ans == a) ans = 0;
else ans++;
}
cout << ans << "\n";
}
}
return 0;
}
D問題：おしゃべりロボット
この問題は文字 - 文字の計算ができる、つまり'C' - 'A' = 2になるということを覚えていると簡単に解くことができます。
Sで文字列を受け取り、S[i] - 'a' + 1 を足していけばいいのです。
ですが、大文字と小文字で分けて考えなければ正しい結果が出ないので、分けて考えます。
小文字は if((S[i]>= 'a') && (S[i]<='z')) で、大文字は if((S[i]>= 'A') && (S[i]<='Z')) で判別できます。
コード
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
string S;
cin >> S;
int ans = 0;
for(int i=0; i < S.size(); i++){
if((S[i]>= 'a') && (S[i]<='z')){
ans += S[i] -'a' + 1;
}
else if((S[i]>= 'A') && (S[i]<='Z')){
ans += 26 + S[i] - 'A' + 1;
}
}
cout << ans << "\n";
}
return 0;
}
E問題：ゾロ目
これは愚直にその時の数字が何かとその時の長さがどれくらいかをfor文で数えていって、長さ分の数字を出力すれば問題ないです。
コード
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int N;
cin >> N;
int len = 2;
int num = 0;
for(int i=0; i < N; i++){
if(num == 9){
num = 1;
len++;
}
else {
num++;
}
}
for(int i=0; i < len; i++){
cout << num;
}
cout << "\n";
}
return 0;
}
F問題：スーパー素数
素数といえばみんな大好きエラトステネスの篩ですよね。知らない人はエラトステネスの篩でググってください。1
この問題では素数配列を作らなくてはいけないのですが、一般的なエラトステネスの篩関数は配列の素数番目の数にtrueなどを代入するものがほとんどなので、私はエラトステネスの篩の実装方法について書いてあるサイトを参考に、以下のようなエラトステネスの篩関数を作り素数配列を作成しました。
コード(エラトステネスの篩)
//エラトステネスの篩
bool is_prime[1000 + 1]; // 素数かどうかを判定
vector<int> prime; // 素数配列
void Eratosthenes(const int N)
{
for(int i = 0; i <= N; i++)
{
is_prime[i] = true; //初期化
}
for(int i=2; i <= N; i++)
{
if(is_prime[i])
{
for( int j=2 i; j <= N; j += i )
{
is_prime[j] = false;
}
prime.push_back(i);
}
}
}
これで素数配列が求められたので、素数配列の素数配列目の数を出力すれば解けます。
以下、main関数です。
コード(main関数)
int main(){
int T;
cin >> T;
Eratosthenes(1000); // 先に制約の最大分の素数配列を作成しておくと良い
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int N;
cin >> N;
for(int i=0; i <= prime.size(); i++){
if(prime[prime[i]-1] > 0 && prime[prime[i]-1] <= N){
cout << prime[prime[i]-1] << "\n";
}
}
}
return 0;
}
G問題：ボルダリング
これは入力がめんどくさくて、グラフ系の問題だったら嫌だな～と思って解かなかったのですが、普通に全探索で解ける問題でした。
再帰関数を使って全探索し、ゴールにたどり着ける全ての行き方のマス数を求め、その中の最小値を出力すれば良いです。
絶対参考にならないと思いますが一応載せておきます。
コード
vector<int> A;
void solve(vector<vector<int> > N, int i, int j, int count){
if(N[i][j] == 0){
count++;
N[i][j] = 3;
solve(N, i+1, j, count);
solve(N, i-1, j, count);
solve(N, i, j+1, count);
solve(N, i, j-1, count);
}
else if(N[i][j] == 2){
A.pb(count+1);
return;
}
else return;
}
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int W,H;
cin >> W >> H;
int si,sj;
vector<vector<int> > N(H+2, vector<int>(W+2, 3));
for(int i=0; i < H; i++){
for(int j=0; i < W; i++){
cin >> N[i+1][j+1];
if(N[i+1][j+1] == 1){
si = i+1;
sj = j+1;
}
}
}
A.clear();
solve(N,si+1,sj,0);
solve(N,si-1,sj,0);
solve(N,si,sj+1,0);
solve(N,si,sj-1,0);
if(A.empty()) cout << 0 << "\n";
else cout << *min_element(A.begin(), A.end()) << "\n";
}
return 0;
}
こういう問題を本番で解きたかったところ。
H問題：カプレカ数の不思議
この問題、初めは数字を文字列として受け取ってintでキャストしつつ配列に入れればできると思っていたのですが、C++ではそういうゴリ押しはできないみたいで…
諦めて数字で受け取り計算で1桁ずつ分けて考えるとできました。
4桁の数字を1桁ずつ分ける方法ですが、元の数字を取り出したい桁数で割るとその桁の数字が出ます。例えば、3456の千の位は3456 / 1000で求めることができます。そして、千の位の数以外の数は3456 % 1000をすれば求めることができます。
後は問題通りに解けば解けるはずです。
この問題はあんまり自信がないので、このコードはあんまり参考にならないんじゃないかなと思います。
コード
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int N;
cin >> N;
vector<int> A(4);
int count = 0;
int a = N;
A[0] = (ll(N/1000));
N %= 1000;
A[1] = (ll(N / 100));
N %= 100;
A[2] = (ll(N / 10));
A[3] = (N % 10);
while(true){
vector<int> lA = A;
vector<int> sA = A;
sort(lA.begin(), lA.end(), greater<ll>());
sort(sA.begin(), sA.end());
int tmp = (lA[0]*1000 + lA[1]*100 + lA[2]*10 + lA[3]) - (sA[0]*1000 + sA[1]*100 + sA[2]*10 + sA[3]);
if(a == tmp){
cout << count << "\n";
break;
}
else{
count++;
a = tmp;
N = a;
A[0] = (int(N/1000));
N %= 1000;
A[1] = (int(N / 100));
N %= 100;
A[2] = (int(N / 10));
A[3] = (N % 10);
}
}
}
return 0;
}
この問題にめちゃくちゃ時間をかけてしまったので後悔しています…Pythonで解いた方が良かったかもしれない
I問題, J問題：質より量(small, large)
これ全探索だと思っちゃったんですよね。後で落ち着いて見ると単純なナップサック問題でした。
ナップサック問題とは動的計画法(DP)で有名な問題です。
まあもちろんそんなものは知らないのでけんちょんさん2のナップサック問題についてのブログを見ます。(ということでこのブログでの動的計画法及びナップサック問題の解説は省きます。)
このブログの2 ナップサック問題の部分を見ると、分かりやすく正確な解説とほぼ答えのコードが書いてあります。
ですが、このブログのコードのままだと商品の重さしか求められないため、私はもう１つDPテーブルを作成して商品の値段も求められるように変更しました。
J問題はI問題と一緒です。制約が違いますが、大は小をかねるので。
コード
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int N,B;
cin >> N >> B;
vector<int> P(N), V(N);
int dp[110][5010];
int pdp[110][5010];
for(int i=0; i < N; i++){
cin >> P[i] >> V[i];
}
for (int p = 0; p <= B; ++p) dp[0][p] = 0;
for (int i = 0; i < N; ++i) {
for (int p = 0; p <= B; ++p) {
if (p >= P[i] && (dp[i][p-P[i]] + V[i] >= dp[i][p])){
dp[i+1][p] = dp[i][p-P[i]] + V[i];
pdp[i+1][p] = pdp[i][p-P[i]] + P[i];
}
else{
dp[i+1][p] = dp[i][p];
pdp[i+1][p] = pdp[i][p];
}
}
}
cout << pdp[N][B] << " " << dp[N][B] << endl;
}
return 0;
}
K問題：ワードサークル
サンプルケースを見て、先頭文字配列と末尾文字配列を作ってそれが一致してたらいいやんと思ったのですが、よくよく考えるとそれでは全ての入力の先頭と末尾が一致している場合に対応できないことに気づきました。
なので、いい感じに例外処理します。私は、先頭文字と末尾文字が同じだった場合の回数を数えてその回数が入力文字数と同じだった場合をはじく処理を書きました。
まあ想定解ではない感じがします。
コード
int main(){
int T;
cin >> T;
for(int t=1; t <=T; t++){
cout << "Case #" << t << ":" << "\n";
int N;
cin >> N;
vector<int> Ws, Wl;
for(int i=0; i < N; i++){
string w;
cin >> w;
Ws.push_back(w[0] - 'a');
Wl.push_back(w[sz(w)-1] - 'a');
}
vector<int> sWs = Ws;
vector<int> sWl = Wl;
sort(sWs.begin(), sWs.end());
sort(sWl.begin(), sWl.end());
bool flag = true;
ll same[27] = {};
for(int i=0; i < N; i++){
if(sWs[i] != sWl[i]){
flag = false;
break;
}
if(Ws[i] == Wl[i]){
same[Ws[i]]++;
}
}
ll count = 0;
for(int i=0; i < 26; i++){
if(N == 1)break;
if(same[i] > 0){
count++;
}
}
if(flag && count != N) cout << "OK" << "\n";
else cout << "NG" << "\n";
}
return 0;
}
まとめ
いかがだったでしょうか？
今年は7問くらい解けてる人がいっぱいいましたし、結構簡単だったのかなと思います。
これを機に競技プログラミングを初めてみてはいかがでしょうか？
