ライブラリ
インターンシップ・ワークショップ 2021&22Winter エンジニア編オンラインテスト解説
こんにちは。新卒採用担当です!
今回は夏に引き続きインターンシップ・ワークショップ 2021&22 Winter エンジニア編 オンライン勉強会「ゲームでデータを扱う方法 入門編」の弊社エンジニアによるプログラムテスト解説を掲載させていただきます。
※参加抽選の結果につきましては、12月3日(金)にマイページ宛に配信させて頂いております。
模範解答
{
int score = 0;
const char* p = word;
while (*p != ‘\0’)
{
if (‘A’ <= *p && *p <= ‘Z’) score += s_scores[*p – ‘A’];
++p;
}
return score;
}
void Sort(std::vector<const char*>& words)
{
std::stable_sort(words.begin(), words.end(),
[](auto& a, auto& b)
{ return CalcScore(a) > CalcScore(b); }
);
}
CalcScore
CalcScore の解説
ポイントは以下の2つ
1.文字列から、文字を1つづつ取り出す処理
・ダブルクォーテーション(”)で括った文字列は、末尾に終端コード(\0)が必ず付くのを利用して、文字列の最初の文字から、終端コードが来るまでを捜査している。
・このようなやり方以外にも、strlen関数のようなものを使って文字数を求めてから、for 文で文字数分を捜査するのも良いだろう。
処理速度の観点では、strlen等を利用するよりも、模範解答の方が有利である。
なぜなら、文字数を調べる過程でも文字列全体を捜査するので、捜査処理が2回走ってしまうから。
2.文字に対応する点数を求める
・s_scores[] に各文字の点数がアルファベット順に定義されていることに注目する。
・問題文に特に明記していなかったが、素直に受け取ってくれた人が大多数だったようで一安心。
・あとは文字Aを0、Bを1、…Zを25に変換できれば、s_scores[]から点数を求められる。
・文字Aから文字Zの文字コードは連続していることを利用すれば、文字に対するインデクスは文字(の文字コード) – Aの文字コード(つまり ‘A’) で求められる。
・A~Z以外の文字には点数が無いことにも注意!
CalcScore の補足説明
C/C++の文字列
・C/C++には、文字列型という便利なモノは存在しない。
・文字列は char 型などの配列(あるいはポインタ)で表現される。
・文字列には、必ず末尾に終端コード(\0)が必ず付くことになっている。
*p は「掛ける p」ではない(乗算も * を使うのでややこしい・・・)
・模範コード中に頻繁に表れる *p という記述。これはポインタ p が指すメモリの中身という意味。
・char moji = *p; のように事前に中身を取り出しておいた方が読みやすいかも。
全角文字とエンコード方式
・今回は関係ないが、いわゆる全角文字の場合は、エンコード方式によって文字の順番が変わるので注意。
例えばShiftJISでは「哀」の次は「愛」だけど、Unicodeだと「哀」の次は「品」。
Sort
Sort の解説
標準ライブラリを知っていれば、ソート処理は1行で書けてしまう!
安定ソートと非安定ソート
安定(stable)とは?
・同じ順位だった時でも、並びが変動しないこと(先に登場したモノが常に先に並ぶ)
・非安定だと、同じ順位の時の並びが必ず同じになるとは限らない!
なので、今回のテストでは標準ライブラリを利用する場合は stable_sort を使わないと正しく動作しないかもしれない。
ソート関数に渡す比較用の関数(関数オブジェクト)
・単純に比較できるモノ(例えば数値)以外は、どうやって比較するのかを示す必要がある。
・模範解答では、比較処理を無名関数オブジェクト(ラムダ式)で定義している。
ラムダ式はとても便利だが、多用する場合はデメリットについても理解して使うべき
・比較処理を「operator <」で実装するのも良い。
標準ライブラリにどのような便利クラスがあるかを知ろう!
・僕らの味方 cpprefjp – C++日本語リファレンス https://cpprefjp.github.io/(*1)
・スマートポインタ、コンテナ、イテレータ、文字列ライブラリは押さえておこう。
標準関数を使わない場合はシンプルにバブルソートを実装すればOK!
・入れ替え処理を気を付けないと、安定ソートが実現しないことがあるので注意!
実際、そこでミスをし不合格になる例がいくつかありました。
バブルソートの実装例
・右隣の値の方が大きかったら交換する。
・交換が行われなくなるまで、上記の処理を繰り返す。
isSwapped が false になったら、交換が行われなくなった証拠。
もっと改善できる!
・for文のループを終えると、末尾の値が最小であることが確定しているので、以降は末尾との比較処理は省ける。
void Sort(std::vector<const char*>& words){
bool isSwapped = true;
while (isSwapped)
{
isSwapped = false;
for (int i = 0; i < (int)words.size() – 1; ++i)
{
if (CalcScore(words[i]) < CalcScore(words[i + 1]))
{
auto tmp = words[i];
words[i] = words[i + 1];
words[i + 1] = tmp;
isSwapped = true;
}
}
}
}
その他、コードを確認して気になったこと
using namespace std; が多かった
・実戦で使用すると、先輩方に嫌がられると思うので避けよう!
ASCIIコードを直接書いているコードが多かった
・s_scores[] のインデクスを求める時に moji – 65 のようなコードが多かった。
・終端コードを ‘\0’ と表現してるのに、 ‘A’ という表現をしていなかった。
アルゴリズムが洗練されていないコードが多かった
・余計なコードがかなり多かったです。
プログラムを書きまくって、洗練されたコードを書けるようになりましょう!
・テストコードの網羅が甘かったせいで、たまたま合格になっているコードがそこそこありました・・・。どんなデータでも正しく動作するコードを書きましょう!
最後に
今回は想定を大幅に上回るエントリーをいただきました!
みなさんとお会いしたいところなのですが、断腸の思いで参加者を抽選させていただきました。
テスト問題はいかがでしたか?
プログラミング界隈では、Python がとても流行っていますが、ゲーム業界(主に家庭用ゲームエンジニア)はいまだに C++ が主流のため、C++にて出題させていただきました。
C++は非常に難しいプログラミング言語です。
不合格になってしまった方も、抽選に漏れてしまった方もゲーム業界を目指すのであれば、引き続き C++ の学習を頑張って欲しいです!
またいつか、どこかでお会いしましょう!
-ゲームエンジニアより
引用元
(*1)cpprefjp – C++日本語リファレンス
プログラミングコンテスト「ゲームAIコンテスト~AI・覚えてますか~」開催!
https://bandainamcostudios.snar.jp/jobboard/detail.aspx?id=q3uAdWrXytdQ_5TZrAM2TQ
▼チュートリアル/実践 2022年1月11日(火)0:00まで
▼トーナメント 2022年1月12日(水)17:00~
▼表彰式・懇親会 2022年1月14日(金)17:00~
【トーナメント】(オンライン開催)
・チュートリアル:CPUと対戦して1位になればクリアです
・実戦:他のプレイヤーとランダムにマッチングして戦えます
※他のプレイヤーが少ない場合、CPUとマッチングします
【表彰式・懇親会】(オンライン開催)
トーナメント上位者を対象に表彰式・懇親会を行います。
表彰式では上位入賞者の表彰に加え、今回の課題の解説も行います!
上位入賞者の方は、表彰式後に懇親会もご案内させていただきます。
※表彰式:エントリーされた方全員視聴可能/懇親会:上位入賞者のみ参加可能
★トーナメント配信、表彰式・懇親会はコンテスト参加人数により開始時間を変更させていただく場合ががございます。確定時間はあらためてご連絡させていただきます。