この記事は競プロ Advent Calendar 2022 13日目の記事です。
はじめに
はじめまして、海猫飯店です。
今回は入緑の記事を書く予定でしたが、それは叶いません。
なぜかというと入緑しなかったです。さようなら。
ということで、ここ最近は精進せずにポケモンSVばっかりしていたのでポケモン関連のネタでお茶を濁したいと思います。
今回の記事
タイトルにある通り今回はポケモンしりとり（SV限定）の最長を探っていきます。
それにはグラフによるモデル化を行い、DFSを用いることにします。
n番煎じでございますが、ご了承ください。
使用するポケモンの定義
- 使用するのは現時点(2022/12/12)でポケモンSVに出現するポケモンのみ
- 長音の場合は長音直前の文字を使用（ハクリュー -> 「ユ」）
- オス、メスの区別はしない。
- ひがしのうみ、にしのうみ等の区別もしない。
- 小文字の場合は大文字に変換（ウインディ -> 「イ」）
- ロトムについては全て区別
ポケモンについてはこちらのサイトを参照しました。
コード
自分用のコード汚いです。
#include<bits/stdc++.h>
using namespace std;
int main(){
//図鑑(txt)の読み込み
ifstream reading_file;
string filename = "pokemon.txt";
reading_file.open(filename);
string reading_line_buffer;
//vector<string> zukanの作成
vector<string> zukan;
zukan.push_back("スタート");
while(getline(reading_file, reading_line_buffer)){
zukan.push_back(reading_line_buffer);
}
zukan.push_back("ゴール");
int N = zukan.size();
vector<vector<int>> G(N, vector<int>());
for(int i = 1; i < N-1; ++i) G[0].push_back(i);
for(int i = 1; i < N-1; ++i){
int M = zukan[i].size();
string tail = zukan[i].substr(M-3, 3);
if(tail=="ー") tail = zukan[i].substr(M-6, 3);
if(tail=="ッ") tail = "ツ";
if(tail=="ャ") tail = "ヤ";
if(tail=="ュ") tail = "ユ";
if(tail=="ョ") tail = "ヨ";
if(tail=="ァ") tail = "ア";
if(tail=="ィ") tail = "イ";
for(int j = 1; j < N-1; ++j){
if(i==j) continue;
if(tail==zukan[j].substr(0,3)) G[i].push_back(j);
}
G[i].push_back(N-1);
}
int len = 0;
vector<int> prev(N); prev[0] = -1;
vector<int> res(N);
vector<bool> seen(N, false);
int max_len = 0;
auto func = [&](vector<int> prev){
int i = N-1;
vector<string> ans;
while(i!=-1){
ans.push_back(zukan[i]);
i = prev[i];
}
reverse(ans.begin(), ans.end());
cout << "==================" << endl;
for(auto s : ans) cout << s << endl;
cout << "==================" << endl;
};
function<void(int, int, vector<bool>, vector<int>)> dfs = [&](int v, int len, vector<bool> seen, vector<int> prev){
seen[v] = true;
len += 1;
if(v==N-1&&max_len<len){
max_len = len;
cout << "長さ";
cout << len << endl;
func(prev);
}
else{
for(auto nv : G[v]){
if(seen[nv]) continue;
vector<int> prev2 = prev;
prev2[nv] = v;
dfs(nv, len, seen, prev2);
}
}
};
dfs(0, len, seen, prev);
}
結果
長さ158
ニャオハ
ハネッコ
コロボーシ
シャワーズ
ズピカ
カムカメ
メブキジカ
カジリガメ
メェークル
ルリリ
リオル
ルクシオ
オリーニョ
ヨクバリス
スリーパー
パモ
モココ
コロトック
クワッス
ストリンダー
ダイオウドウ
ウェルカモ
モロバレル
ルカリオ
オリーヴァ
アチゲータ
タマランチュラ
ラッキー
キマワリ
リーフィア
アオガラス
スカタンク
クレッフィ
イッカネズミ
ミツハニー
ニャローテ
テブリム
ムクバード
ドオー
オドリドリ
リングマ
マスカーニャ
ヤヤコマ
マメバッタ
タマゲタケ
ケッキング
グレンアルマ
マクノシタ
タツベイ
イワンコ
コフキムシ
シキジカ
カジッチュ
ユキハミ
ミニーブ
ブーピッグ
グライシア
アーマーガア
アメタマ
マケンカニ
ニャース
ストライク
クヌギダマ
マルノーム
ムクホーク
クエスパトラ
ラルトス
スナヘビ
ビリリダマ
マンキー
キルリア
アメモース
スピンロトム
ムウマ
マフィティフ
ファイアロー
ロトム
ムウマージ
ジュペッタ
タイレーツ
ツンベアー
アマカジ
ジヘッド
ドレディア
アママイコ
コフーライ
イキリンコ
ココガラ
ライチュウ
ウソハチ
チュリネ
ネッコアラ
ラランテス
スナバァ
アマージョ
ヨーギラス
スナノケガワ
ワナイダー
ダグトリオ
オノンド
ドジョッチ
チルット
トドロクツキ
キノココ
コダック
クズモー
モトトカゲ
ゲンガー
ガーディ
イーブイ
イダイナキバ
バネブー
ブラッキー
キノガッサ
サボネア
アップリュー
ユキノオー
オラチフ
フワンテ
テツノツツミ
ミミッキュ
ユキワラシ
シシコ
コジオ
オドシシ
シガロコ
コオリッポ
ポポッコ
コマタナ
ナミイルカ
カルボウ
ウソッキー
キリンリキ
キャモメ
メラルバ
バチンウニ
ニンフィア
アノクサ
サダイジャ
ヤトウモリ
リザード
ドヒドイデ
デリバード
ドラメシヤ
ヤバチャ
ヤミラミ
ミガルーサ
サーフゴー
ゴマゾウ
ウデッポウ
ウパー
パルデアウパー
パピモッチ
チヲハウハネ
ネオラント
トロピウス
スリープ
ププリン
となっていますが、実はこれを書いている現在も計算が終わっていません。
こちらのサイトによれば最長は168となるようです。アルゴリズムを考え直してリベンジしたいと思います。
最後に
来年度の上半期には緑になっていたい。そのためにも年始年末は精進に時間をかけたいのだけど、今はもう少しポケモンSVをやっていようかな。
あとtwitterを今年始めたのに人との交流をしてきませんでした。少しずつ交流を始めようと思い、今回の企画に参加しました。企画したryusuke氏に感謝