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 ナップサック問題の部分を見ると、分かりやすく正確な解説とほぼ答えのコードが書いてあります。
ですが、このブログのコードのままだと商品の重さしか求められないため、私はもう1つ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問くらい解けてる人がいっぱいいましたし、結構簡単だったのかなと思います。
これを機に競技プログラミングを初めてみてはいかがでしょうか?
KOFに行った話
KOFに行ったので、その様子や感想を(自分用に)まとめる。
目次
そもそもKOFとは?
KOFというのは、11月10日(金)と11日(土)に大阪南港ATCにて開催されたオープンソースやIT関連のコミュニティに焦点を当てたイベントある。正式名称は『関西オープンフォーラム2017』であり、キングオブファイターズとは全くの別物である(よくタグを見て勘違いする人がいる)。来場者数は約1200人と結構多く、企業/学校/コミュニティ/個人などがブース展示をしたり講演やセミナー、ステージ発表などを行なっている。詳しくは公式ホームページを見て欲しい。
私は2日目にあたる11日に一般参加者として参加した。
講演会 / セミナー / ステージ発表
私が参加した2日目には22セミナーと3講演会、13ステージ発表が行われていた。
そのなかでも私が参加した講演会/セミナー/ステージ発表は、
・今さら聞けないガンダム超入門(セミナー)
・Tele-existenceとネットワークの狭間で(ステージ発表)
・最近のコマンドラインツール事情(セミナー)
・Raspberry Piで音楽を楽しもう!(セミナー)
・東海道らぐ 秋のKOF大阪湾ライトニングトーク大会(セミナー)
・日本のインターネットが揺れた日(講演会)
の6つである。このそれぞれの感想等を簡単書く。
今さら聞けないガンダム超入門(セミナー)
朝一発目、11時からのセミナーであった。本学の先生に、これはおっさん向けのセミナーだと思うよと言われたが、学生の私にとっても面白い内容だった。ちなみに私はガンダムについては『ロボットの中に人間が乗ってなんか戦争する』ことくらいしか知らないくらいであった。
発表者はみやはらとおるさん、主催はガンダム勉強会さんで、『ガンダムはIT企業の一般教養である』というスローガン(?)のもと活動しているらしい。まずはガンダムのあらすじの説明。Twitterを見ると結構詳細な説明だったみたいで、確かに途中から理解が追いつかなくなってしまった。その次にガンダム名台詞の紹介。聞いたことある台詞や日常生活に応用できそうな台詞等が紹介された。そして『ガンダムはIT企業の一般教養である』所以ついての話。ガンダムはIT業界の処世術を学ばせてくれる作品であり、IT業界で生き残るためにはガンダムを見るべきだそうだ。しかし、教養だからと行って新入社員に強制的に見せようとするとガンハラ(ガンダムハラスメント。業務上の優越的な地位を利用してガンダムを見せること)になるので注意が必要である。
その後登壇者が変わり『ガンダムから学ぶプログラマの心構え』についてのLTが行われた.ガンダムに登場するエンジニア魂を持った人々や,プログラマ・マネージャーとして見習うべき登場人物、またそのアンチパターンが紹介された。
このセミナーはTwitterでもとても盛り上がっており、私の記憶にも色濃く残っているセミナーである。そしてガンダムを見てみたい、というか見た方がいい気がした。
Tele-existenceとネットワークの狭間で(ステージ発表)
15分のステージ発表。発表者は慶應義塾大学の砂原秀樹さん。 視覚・聴覚・触覚といった複数の感覚を活用したTele-existenceとそれを支えるネットワーク技術の現状についての紹介だった。Tele-presence(遠隔にいるように感じる)を超えたTele-existence(遠隔に存在する)を実現させる研究は昔からなされており、直接感じる場合とズレが生じないように、低遅延同期通信が重要となる。現状まだズレがあるのでズレをなくすことが課題となっている。私にとってはとても難しい話であったが、私の所属する部活が力を入れているVR/ARについての知らなかった技術を知ることができた。
最近のコマンドラインツール事情(セミナー)
発表者はnasa9084さん。これについては、デモを見るか自分で試さないと分からないと思うので、紹介されたものを書いておく。ふわっとしたコマンドの説明を書いておくが,間違ってるかもしれない(ごめんなさい)ので、気になったものはもう一度調べ直した方が良い。
・peco ... ツールの検索ができる
・ghq ... GOPATHと互換性がある
・anyenv ... ~env系のコマンドを管理する
・direnv ... 環境変数管理
・docker ... Linux向け?
色々無知だったので分からないことが多かった。コマンドラインも使いこなせるようになりたい。
Raspberry Piで音楽を楽しもう!(セミナー)
発表者はラズパイオーディオの会の松本壮史さん。ラズパイオーディオの会というのはそういう会があるのではなく、松本さんと宮原さんがKOF等のイベントに出るために付けた名前だそうだ.使う用途があまりないように思えるラズパイだが、簡単に音質の良い音楽オーディオとして使うことができるそうだ。音楽オーディオとして使うのに適したラズパイの種類や出力のDACボードの紹介があった。詳しい種類などはメモしきれなかったので、またTwitterにあげてくださっているはずのスライドを確認した方が良い。
私自身ずっとラズパイには興味があったが自分には扱いきれないような気がしていたが、音楽オーディオを作れるのなら買ってみて作ってみたいと思った。
東海道らぐ 秋のKOF大阪湾ライトニングトーク大会(セミナー)
私の好きなLT大会が行われていたので聞きに行った。主催は東海道らぐさんで、Linux関係のLT大会を多く開催しているらしい。今回のLTはLinuxに関係なくても良いものだった。故にゲームの話とかもあり面白かった。LTの題名でメモれたものを書いておく。内容は想像してほしい。間違っていたらごめんなさい。
・ブルフリ(ゲーム)はいいぞぉ〜という話
・新規の人材を探したい話
・processingでサイコロを振ってみた話
・ガジェットLinuxハッキングの話
・あひる焼きbot
・Minecraftの話
・burn duckさんの話
日本のインターネットが揺れた日(講演会)
登壇者は朝日新聞社の須藤龍也さんである。この方は朝日新聞にエンジニアとして入社したが後に記者となり、サイバーセキュリティーの記事を担当していらっしゃるそうだ。そして、8.25の大規模ネット障害の原因をどこよりも早く記事にした方である。この方のすごいところは、Googleが原因だと気づいてから誰よりも早くGoogleに連絡を取り回答を得たことだ。それによって正しい報道をすることができたのだ。また、その原因についてIT関連の人以外でも分かるような分かりやすい記事まで出し、一般市民が納得するような報道をしたのだ。すごい。他にも、この記事に対するネットの反応等を分析なさっていたのは面白いと感じた。
報道の裏側を知れたと共に、インターネットの危うさを再確認できた講演会であった。私たちは、人類が手で作り上げ世界を変えたインターネットの世界を見ているということを大切にしていきたい。
【KOF2017講演会】日本のインターネットが揺れた日 - YouTube
---------------------------------------------
他にもたくさんの素晴らしい講演会やセミナーがあった。『ネ申エクセルと事務情報化』の話はとてもTwitterが盛り上がっていたし、私の所属大学もAO入試の話をしていたりしたらしいし、聞きに行きたかった発表もたくさんある。KOFのセミナーや講演会の動画はYouTubeに上がっているものもあるし、スライドはslideshareに上がっているものもあるので、聞けなかった発表はまた後日見てみようと思う。
ブース展示
KOFの日、私は友達と来ていたのだが、私の中で決めていた予定と友達の中で決めていた予定が違ったのでブース展示は1人で周った。1人だったがどこの出展者さんも気さくに話してくださったので色々な方からお話を伺うことができた。また、たくさんのステッカーやグッズを頂くことができた。
2日目のブース展示はなんと38展示あったらしい。
私はまずブース展示のツアーに参加し、その後1人で見て周った。
私が覚えている範囲でお話を伺った展示は次の18展示である。
何を展示していたかはパンフレットを見れば分かるので、貰った物等をまとめた。
-AO入試問題の配布
女子大生が過激な衣装 目立つ格好でビラを配っていた
・大阪コンピュータ専門学校ITcreate部
-自作言語で作ったゲームなどの展示
・9VAきゅうべえアニメ研究所
-描いた絵をアニメーションにした
・Netwalker実験所
・アイクラフト(株)
-Webブラウザ上でLibre Office使える
・(株)Joe'sクラウドコンピューティング
-ファイルを貰った
・東海道らぐ
-めっちゃステッカーくれた
・GDG京都
-勉強会の宣伝
・日本MySQLユーザ会(MyNA)
- MySOLのぬいぐるみを貰った
-お菓子のつかみ取り
・cocoa勉強会
-勉強会の宣伝
・ラズパイオーディオの会
-ラズパイオーディオ聴かせてもらった
・日本PostgreSQLユーザ会 関西支部
-水を貰った
・さくらインターネット(株)
-ペンっぽい染み抜きを貰った
・Debian JP Project / 関西Debian勉強会
-勉強会の宣伝,バッチ貰った
・アトラシアン(株)
-Tシャツとシール貰った
・大阪府警察
-女性の技術者は重宝されるらしい
・Gyazo Teams
-飴とたくさんのステッカーを貰った
当たりはマグカップが貰える
他にも素敵な展示がたくさんあったようだが、時間の都合上見れなかった。来年は制覇したい。
まとめ
このようなイベントに参加するのは初めてだったが、とても楽しめた。色々なセミナーや講演会を見れる機会はあまりないし、ガンダム勉強会など普通の勉強会だと行きにくいものにも気軽に行くことができた。また、企業さんのグッズやスッテカーを貰えたり、企業の方と直接話すこともできたのも良い経験だと思った。来年のKOFにも是非参加したい。
スタッフの皆様はお疲れ様でした。そして、ありがとうございました。