paizaラーニングレベルアップ問題集の「みんなでしりとり」をオブジェクト指向でやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[みんなでしりとり](https://paiza.jp/works/mondai/b_rank_skillcheck_archive/word_chain)をオブジェクト指向でやってみました。対象は[コードモンスター大図鑑](https://paiza.jp/code_monster)で対応している9言語です。

2024/08/25更新
Javascriptのコードを修正いたしました。
- - -
###### 方針
- しりとりクラスを定義します。
- しりとりをする人数を表す整数$N$と単語リストに載っている単語を表す文字列$d_i$（$1\le i\le K$）をコンストラクタに渡します。
- しりとりで行われた発言を表す文字列$s_j$（$1\le j\le M$）をメソッドに渡します。
- メソッドは、以下の問題文を実装します。
> 1. 発言は、単語リストにある K 個の単語のうちのいずれかの単語でなければならない。
> 1. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
> 1. 今までに発言された単語を発言してはならない。
> 1. zで終わる単語を発言してはならない。
>
> ここで、発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
> そして、その人を抜いて引き続きしりとりを続けていきます。このとき、後続の人は、ルール2を守る必要はありません。
- - -
###### PHP
```php
<?php
	class WordChain {
		// しりとりをする人数
		private $nPlayers;

		// 発言する人
		private $player;

		// 残っている人数
		private $nAlives;

		// 残っている人のリスト
		private $alive;

		// 単語リスト
		private $words;

		// 直前の人の発言
		private $before;

		// 今までに発言された単語
		private $usedWords;

		private function isValid($s) {
			// 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
			if (!in_array($s, $this->words)) {
				return false;
			}

			// 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
			if ($this->before != "" && $this->before[-1] != $s[0]) {
				return false;
			}

			// 3. 今までに発言された単語を発言してはならない。
			if (in_array($s, $this->usedWords)) {
				return false;
			}

			// 4. zで終わる単語を発言してはならない。
			if ($s[-1] == 'z') {
				return false;
			}

			return true;
		}

		// 残っている人の人数
		public function getNAlives() {
			return $this->nAlives;
		}

		// 残っているかどうか
		public function isAlive($i) {
			return $this->alive[$i];
		}

		// コンストラクタ
		public function __construct($n, $d) {
			// しりとりをする人数
			$this->nPlayers = $n;

			// 発言する人
			$this->player = 0;

			// 残っている人数
			$this->nAlives = $n;

			// 残っている人のリスト
			$this->alive = array_fill(0, $n, true);

			// 単語リスト
			$this->words = $d;

			// 直前の人の発言
			$this->before = "";

			// 今までに発言された単語
			$this->usedWords = [];
		}

		public function say($s) {
			if ($this->isValid($s)) {
				$this->usedWords[] = $s;
				$this->before = $s;
			} else {
				// 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
				$this->alive[$this->player] = false;
				$this->nAlives--;

				// このとき、後続の人は、ルール2を守る必要はありません。
				$this->before = "";
			}

			//脱落した人を抜いて引き続きしりとりを続けていきます。
			do {
				$this->player = ($this->player + 1) % $this->nPlayers;
			} while (!$this->alive[$this->player]);
		}
	}

	// 1行目にしりとりをする人数を表す整数N、
	// 単語リストに乗っている単語の数を表す整数K、
	// しりとりで行われた発言の数を表す整数Mが
	// この順にスペース区切りで与えられます。
	[$n, $k, $m] = explode(" ", fgets(STDIN));

	// 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
	$d = [];
	for ($i = 0; $i < $k; $i++) {
		$d[] = trim(fgets(STDIN));
	}

	// しりとりクラスをインスタンス化します。
	$wordChain = new WordChain($n, $d);

	// 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
	for ($i = 0; $i < $m; $i++) {
		$wordChain->say(trim(fgets(STDIN)));
	}

	// 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
	echo $wordChain->getNAlives() . "\n";

	// 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
	for ($i = 0; $i < $n; $i++) {
		if ($wordChain->isAlive($i))
			echo ($i + 1) . "\n";
	}
?>
```
- - -
###### Ruby
```rb
require 'set'

class WordChain
	def isValid(s)
		# 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
		if (!@words.include?(s)) 
			return false
		end

		# 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
		if (@before != "" && @before[-1] != s[0]) 
			return false
		end

		# 3. 今までに発言された単語を発言してはならない。
		if (@used_words.include?(s)) 
			return false
		end

		# 4. zで終わる単語を発言してはならない。
		if (s[-1] == 'z') 
			return false
		end

		return true
	end

	# 残っている人の人数
	def getNAlives()
		return @nAlives
	end

	# 残っているかどうか
	def isAlive(i)
		return @alive[i]
	end

	# コンストラクタ
	def initialize(n, d)
		# しりとりをする人数
		@nPlayers = n

		# 発言する人
		@player = 0

		# 残っている人数
		@nAlives = n

		# 残っている人のリスト
		@alive = Array.new(n, true)

		# 単語リスト
		@words = d

		# 直前の人の発言
		@before = ""

		# 今までに発言された単語
		@used_words = Set.new()
	end

	def say(s)
		if isValid(s)
			@used_words.add(s)
			@before = s
		else 
			# 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
			@alive[@player] = false
			@nAlives -= 1

			# このとき、後続の人は、ルール2を守る必要はありません。
			@before = ""
		end

		#脱落した人を抜いて引き続きしりとりを続けていきます。
		begin
			@player = (@player + 1) % @nPlayers
		end while !@alive[@player]
	end
end

# 1行目にしりとりをする人数を表す整数N、
# 単語リストに乗っている単語の数を表す整数K、
# しりとりで行われた発言の数を表す整数Mが
# この順にスペース区切りで与えられます。
n, k, m = gets.split.map(&:to_i)

# 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
# しりとりクラスをインスタンス化します。
word_chain = WordChain.new(n, Set.new(k.times.map { gets.chomp }))

# 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
m.times do 
	word_chain.say(gets.chomp)
end

# 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
p word_chain.getNAlives()

# 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
n.times do |i|
	if word_chain.isAlive(i)
		p i + 1
	end
end
```
- - -
###### Java	
```java
import java.util.*;

class WordChain {
	// しりとりをする人数
	private int nPlayers;

	// 発言する人
	private int player;

	// 残っている人数
	private int nAlives;

	// 残っている人のリスト
	private boolean[] alive;

	// 単語リスト
	private Set<String> words;

	// 直前の人の発言
	private String before;

	// 今までに発言された単語
	private Set<String> usedWords;

	private boolean isValid(String s) {
		// 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
		if (!words.contains(s)) {
			return false;
		}

		// 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
		if (!"".equals(before) && before.charAt(before.length() - 1) != s.charAt(0)) {
			return false;
		}

		// 3. 今までに発言された単語を発言してはならない。
		if (usedWords.contains(s)) {
			return false;
		}

		// 4. zで終わる単語を発言してはならない。
		if (s.charAt(s.length() - 1) == 'z') {
			return false;
		}

		return true;
	}

	// 残っている人の人数
	public int getNAlives() {
		return nAlives;
	}

	// 残っているかどうか
	public boolean isAlive(int i) {
		return alive[i];
	}

	// コンストラクタ
	public WordChain(int n, Set<String> d) {
		// しりとりをする人数
		nPlayers = n;

		// 発言する人
		player = 0;

		// 残っている人数
		nAlives = n;

		// 残っている人のリスト
		alive = new boolean[n];
		Arrays.fill(alive, true);

		// 単語リスト
		words = d;

		// 直前の人の発言
		before = "";

		// 今までに発言された単語
		usedWords = new HashSet<String>();
	}

	public void say(String s) {
		if (isValid(s)) {
			usedWords.add(s);
			before = s;
		} else {
			// 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
			alive[player] = false;
			nAlives--;

			// このとき、後続の人は、ルール2を守る必要はありません。
			before = "";
		}

		// 脱落した人を抜いて引き続きしりとりを続けていきます。
		do {
			player = (player + 1) % nPlayers;
		} while (!alive[player]);
	}
}

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		// 1行目にしりとりをする人数を表す整数N、
		// 単語リストに乗っている単語の数を表す整数K、
		// しりとりで行われた発言の数を表す整数Mが
		// この順にスペース区切りで与えられます。
		int n = sc.nextInt();
		int k = sc.nextInt();
		int m = sc.nextInt();

		// 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
		Set<String> d = new HashSet<>();
		for (int i = 0; i < k; i++) {
			d.add(sc.next());
		}

		// しりとりクラスをインスタンス化します。
		WordChain wordChain = new WordChain(n, d);

		// 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
		for (int i = 0; i < m; i++) {
			wordChain.say(sc.next());
		}
		sc.close();

		// 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
		System.out.println(wordChain.getNAlives());

		// 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
		for (int i = 0; i < n; i++) {
			if (wordChain.isAlive(i))
				System.out.println(i + 1);
		}
	}
}
```
- - -
###### Python
```py
class WordChain:
	def isValid(self, s):
		# 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
		if s not in self.words:
			return False

		# 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
		if self.before and self.before[-1] != s[0]:
			return False

		# 3. 今までに発言された単語を発言してはならない。
		if s in self.used_words:
			return False

		# 4. zで終わる単語を発言してはならない。
		if s[-1] == 'z':
			return False

		return True

	# 残っている人の人数
	def getNAlives(self):
		return self.nAlives

	# 残っているかどうか
	def isAlive(self, i):
		return self.alive[i]

	# コンストラクタ
	def __init__(self, n, d):
		# しりとりをする人数
		self.nPlayers = n

		# 発言する人
		self.player = 0

		# 残っている人数
		self.nAlives = n

		# 残っている人のリスト
		self.alive = [True for _ in range(n)]

		# 単語リスト
		self.words = d

		# 直前の人の発言
		self.before = ""

		# 今までに発言された単語
		self.used_words = set()

	def say(self, s):
		if self.isValid(s):
			self.used_words.add(s)
			self.before = s
		else:
			# 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
			self.alive[self.player] = False
			self.nAlives -= 1

			# このとき、後続の人は、ルール2を守る必要はありません。
			self.before = ""

		# 脱落した人を抜いて引き続きしりとりを続けていきます。
		self.player = (self.player + 1) % self.nPlayers
		while not self.alive[self.player]:
			self.player = (self.player + 1) % self.nPlayers


# 1行目にしりとりをする人数を表す整数N、
# 単語リストに乗っている単語の数を表す整数K、
# しりとりで行われた発言の数を表す整数Mが
# この順にスペース区切りで与えられます。
n, k, m = map(int, input().split())

# 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
# しりとりクラスをインスタンス化します。
word_chain = WordChain(n, {input() for _ in range(k)})

# 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
for _ in range(m):
	word_chain.say(input())

# 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
print(word_chain.getNAlives())

# 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
for i in range(n):
	if word_chain.isAlive(i):
		print(i + 1)
```
- - -
###### C言語
```c
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool search(const char **words, const char *s) {
	for (const char **word = words; *word; word++) {
		if (!strcmp(*word, s)) {
			return true;
		}
	}
	return false;
}

void add(const char **words, const char *s) {
	const char **word = words;
	while (*word) {
		if (!strcmp(*word, s)) {
			return;
		}
		word++;
	}
	*word = s;
}

typedef struct WordChain {
	// しりとりをする人数
	int n_players;

	// 発言する人
	int player;

	// 残っている人数
	int n_alives;

	// 残っている人のリスト
	bool *alive;

	// 単語リスト
	const char **words;

	// 直前の人の発言
	const char *before;

	// 今までに発言された単語
	const char **used_words;
} WordChain;

bool isValid(const WordChain *word_chain, const char *s) {
	// 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
	if (!search(word_chain->words, s)) {
		return false;
	}

	// 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
	if (strcmp(word_chain->before, "")
			&& word_chain->before[strlen(word_chain->before) - 1] != s[0]) {
		return false;
	}

	// 3. 今までに発言された単語を発言してはならない。
	if (search(word_chain->used_words, s)) {
		return false;
	}

	// 4. zで終わる単語を発言してはならない。
	if (s[strlen(s) - 1] == 'z') {
		return false;
	}

	return true;
}

void say(WordChain *word_chain, const char *s) {
	if (isValid(word_chain, s)) {
		add(word_chain->used_words, s);
		word_chain->before = s;
	} else {
		// 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
		word_chain->alive[word_chain->player] = false;
		word_chain->n_alives--;

		// このとき、後続の人は、ルール2を守る必要はありません。
		word_chain->before = "";
	}

	//脱落した人を抜いて引き続きしりとりを続けていきます。
	do {
		word_chain->player = (word_chain->player + 1) % word_chain->n_players;
	} while (!word_chain->alive[word_chain->player]);
}

int main() {
	// 1行目にしりとりをする人数を表す整数N、
	// 単語リストに乗っている単語の数を表す整数K、
	// しりとりで行われた発言の数を表す整数Mが
	// この順にスペース区切りで与えられます。
	int n, k, m;
	scanf("%d %d %d", &n, &k, &m);

	// 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
	char d[k][11];
	const char *words[k + 1];
	for (int i = 0; i < k; i++) {
		scanf("%s", d[i]);
		words[i] = d[i];
	}
	words[k] = NULL;

	// しりとりクラスをインスタンス化します。
	bool alive[n];
	memset(alive, true, sizeof(alive));
	const char *usedWords[k + 1];
	memset(usedWords, 0, sizeof(usedWords));
	WordChain word_chain = { n, 0, n, alive, words, "", usedWords };

	// 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
	char s[m][11];
	for (int i = 0; i < m; i++) {
		scanf("%s", s[i]);
		say(&word_chain, s[i]);
	}

	// 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
	printf("%d\n", word_chain.n_alives);

	// 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
	for (int i = 0; i < n; i++) {
		if (alive[i])
			printf("%d\n", i + 1);
	}

	return 0;
}
```
- - -
###### C#
```cs
using System;
using System.Collections.Generic;

class WordChain
{
	// しりとりをする人数
	private int nPlayers;

	// 発言する人
	private int player;

	// 残っている人数
	private int nAlives;

	// 残っている人のリスト
	private bool[] alive;

	// 単語リスト
	private HashSet<string> words;

	// 直前の人の発言
	private string before;

	// 今までに発言された単語
	private HashSet<string> usedWords;

	private bool IsValid(string s)
	{
		// 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
		if (!words.Contains(s))
		{
			return false;
		}

		// 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
		if (!"".Equals(before) && before[before.Length - 1] != s[0])
		{
			return false;
		}

		// 3. 今までに発言された単語を発言してはならない。
		if (usedWords.Contains(s))
		{
			return false;
		}

		// 4. zで終わる単語を発言してはならない。
		if (s[s.Length - 1] == 'z')
		{
			return false;
		}

		return true;
	}

	// 残っている人の人数
	public int NAlives
	{
		get { return nAlives; }
	}

	// 残っているかどうか
	public bool IsAlive(int i)
	{
		return alive[i];
	}

	// コンストラクタ
	public WordChain(int n, HashSet<String> d)
	{
		// しりとりをする人数
		nPlayers = n;

		// 発言する人
		player = 0;

		// 残っている人数
		nAlives = n;

		// 残っている人のリスト
		alive = new bool[n];
		for (int i = 0; i < n; i++) alive[i] = true;

		// 単語リスト
		words = d;

		// 直前の人の発言
		before = "";

		// 今までに発言された単語
		usedWords = new HashSet<string>();
	}

	public void Say(string s)
	{
		if (IsValid(s))
		{
			usedWords.Add(s);
			before = s;
		}
		else
		{
			// 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
			alive[player] = false;
			nAlives--;

			// このとき、後続の人は、ルール2を守る必要はありません。
			before = "";
		}

		// 脱落した人を抜いて引き続きしりとりを続けていきます。
		do
		{
			player = (player + 1) % nPlayers;
		} while (!alive[player]);
	}
}

class Program
{
	static void Main()
	{
		// 1行目にしりとりをする人数を表す整数N、
		// 単語リストに乗っている単語の数を表す整数K、
		// しりとりで行われた発言の数を表す整数Mが
		// この順にスペース区切りで与えられます。
		int[] nkm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
		int n = nkm[0];
		int k = nkm[1];
		int m = nkm[2];

		// 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
		HashSet<string> d = new HashSet<string>();
		for (int i = 0; i < k; i++)
		{
			d.Add(Console.ReadLine());
		}

		// しりとりクラスをインスタンス化します。
		WordChain wordChain = new WordChain(n, d);

		// 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
		for (int i = 0; i < m; i++)
		{
			wordChain.Say(Console.ReadLine());
		}

		// 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
		Console.WriteLine(wordChain.NAlives);

		// 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
		for (int i = 0; i < n; i++)
		{
			if (wordChain.IsAlive(i))
				Console.WriteLine(i + 1);
		}
	}
}
```
- - -
###### Javascript
```js
class WordChain {
	// しりとりをする人数
	nPlayers = 0;

	// 発言する人
	player = 0;

	// 残っている人数
	nAlives = 0;

	// 残っている人のリスト
	alive = null;

	// 単語リスト
	words = null;

	// 直前の人の発言
	before = "";

	// 今までに発言された単語
	usedWords = new Set();

	isValid(s) {
		// 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
		if (!this.words.has(s)) {
			return false;
		}

		// 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
		if (this.before !== "" && this.before[this.before.length - 1] !== s[0]) {
			return false;
		}

		// 3. 今までに発言された単語を発言してはならない。
		if (this.usedWords.has(s)) {
			return false;
		}

		// 4. zで終わる単語を発言してはならない。
		if (s[s.length - 1] === 'z') {
			return false;
		}

		return true;
	}

	// 残っている人の人数
	getNAlives() {
		return this.nAlives;
	}

	// 残っているかどうか
	isAlive(i) {
		return this.alive[i];
	}

	// コンストラクタ
	constructor(n, d) {
		// しりとりをする人数
		this.nPlayers = n;

		// 残っている人数
		this.nAlives = n;

		// 残っている人のリスト
		this.alive = new Array(n).fill(true);

		// 単語リスト
		this.words = d;
	}

	say(s) {
		if (this.isValid(s)) {
			this.usedWords.add(s);
			this.before = s;
		} else {
			// 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
			this.alive[this.player] = false;
			this.nAlives--;

			// このとき、後続の人は、ルール2を守る必要はありません。
			this.before = "";
		}

		// 脱落した人を抜いて引き続きしりとりを続けていきます。
		do {
			this.player = (this.player + 1) % this.nPlayers;
		} while (!this.alive[this.player]);
	}
}


const lines = require("fs").readFileSync("/dev/stdin", "utf8").split("\n");

// 1行目にしりとりをする人数を表す整数N、
// 単語リストに乗っている単語の数を表す整数K、
// しりとりで行われた発言の数を表す整数Mが
// この順にスペース区切りで与えられます。
// 2024-08-25 parseIntからNumberに修正
// const [n, k, m] = lines[0].split(" ").map(x => parseInt(x, 10));
const [n, k, m] = lines[0].split(" ").map(Number);

// 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
const d = new Set();
for (var i = 1; i <= k; i++) {
	d.add(lines[i]);
}

// しりとりクラスをインスタンス化します。
const wordChain = new WordChain(n, d);

// 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
for (var i = 1; i <= m; i++) {
	wordChain.say(lines[k + i]);
}

// 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
console.log(wordChain.getNAlives());

// 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
for (var i = 0; i < n; i++) {
	if (wordChain.isAlive(i))
		console.log(i + 1);
}
```
- - -
###### C++
```cpp
#include <iostream>
#include <vector>
#include <set>
using namespace std;

class WordChain {
	// しりとりをする人数
	int n_players;

	// 発言する人
	int player;

	// 残っている人数
	int n_alives;

	// 残っている人のリスト
	vector<bool> alive;

	// 単語リスト
	set<string> words;

	// 直前の人の発言
	string before;

	// 今までに発言された単語
	set<string> used_words;

	bool isValid(const string &s) {
		// 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
		if (!words.count(s)) {
			return false;
		}

		// 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
		if (before.length() && before[before.length() - 1] != s[0]) {
			return false;
		}

		// 3. 今までに発言された単語を発言してはならない。
		if (used_words.count(s)) {
			return false;
		}

		// 4. zで終わる単語を発言してはならない。
		if (s[s.length() - 1] == 'z') {
			return false;
		}

		return true;
	}

public:
	// 残っている人の人数
	int getNAlives() {
		return n_alives;
	}

	// 残っているかどうか
	bool isAlive(int i) {
		return alive[i];
	}

	// コンストラクタ
	WordChain(int n, const set<string> &d) {
		// しりとりをする人数
		n_players = n;

		// 発言する人
		player = 0;

		// 残っている人数
		n_alives = n;

		// 残っている人のリスト
		alive.resize(n, true);

		// 単語リスト
		words = d;

		// 直前の人の発言
		before = "";
	}

	void say(const string &s) {
		if (isValid(s)) {
			used_words.insert(s);
			before = s;
		} else {
			// 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
			alive[player] = false;
			n_alives--;

			// このとき、後続の人は、ルール2を守る必要はありません。
			before = "";
		}

		// 脱落した人を抜いて引き続きしりとりを続けていきます。
		do {
			player = (player + 1) % n_players;
		} while (!alive[player]);
	}
};

int main() {
	// 1行目にしりとりをする人数を表す整数N、
	// 単語リストに乗っている単語の数を表す整数K、
	// しりとりで行われた発言の数を表す整数Mが
	// この順にスペース区切りで与えられます。
	int n, k, m;
	cin >> n >> k >> m;

	// 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
	set<string> d;
	for (int i = 0; i < k; i++) {
		string s;
		cin >> s;
		d.insert(s);
	}

	// しりとりクラスをインスタンス化します。
	WordChain word_chain(n, d);

	// 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
	for (int i = 0; i < m; i++) {
		string s;
		cin >> s;
		word_chain.say(s);
	}

	// 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
	cout << word_chain.getNAlives() << endl;

	// 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
	for (int i = 0; i < n; i++) {
		if (word_chain.isAlive(i))
			cout << i + 1 << endl;
	}
}
```
- - -
###### Kotlin
```kotlin
import java.util.*

class WordChain {
	// しりとりをする人数
	var nPlayers: Int

	// 発言する人
	var player = 0

	// 残っている人数
	var nAlives: Int
		get() {
			return field
		}

	// 残っている人のリスト
	var alive: Array<Boolean>

	// 単語リスト
	var words: Set<String>

	// 直前の人の発言
	var before = ""

	// 今までに発言された単語
	val usedWords = mutableSetOf<String>()

	fun isValid(s: String): Boolean {
		// 1. 発言は、単語リストにあるK個の単語のうちのいずれかの単語でなければならない。
		if (!words.contains(s)) {
			return false
		}

		// 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
		if (!"".equals(before) && before[before.length - 1] != s[0]) {
			return false
		}

		// 3. 今までに発言された単語を発言してはならない。
		if (usedWords.contains(s)) {
			return false
		}

		// 4. zで終わる単語を発言してはならない。
		if (s[s.length - 1] == 'z') {
			return false
		}

		return true
	}

	// 残っているかどうか
	fun isAlive(i: Int): Boolean {
		return alive[i]
	}

	// コンストラクタ
	constructor(n: Int, d: Set<String>) {
		// しりとりをする人数
		nPlayers = n

		// 残っている人数
		nAlives = n

		// 残っている人のリスト
		alive = Array(n){ true }

		// 単語リスト
		words = d
	}

	fun say(s: String) {
		if (isValid(s)) {
			usedWords.add(s)
			before = s
		} else {
			// 発言の途中で上のルールを破った場合、ルールを破った人はしりとりから外れます。
			alive[player] = false
			nAlives--

			// このとき、後続の人は、ルール2を守る必要はありません。
			before = ""
		}

		// 脱落した人を抜いて引き続きしりとりを続けていきます。
		do {
			player = (player + 1) % nPlayers
		} while (!alive[player])
	}
}

fun main() {
	val sc = Scanner(System.`in`)
	// 1行目にしりとりをする人数を表す整数N、
	// 単語リストに乗っている単語の数を表す整数K、
	// しりとりで行われた発言の数を表す整数Mが
	// この順にスペース区切りで与えられます。
	val n = sc.nextInt()
	val k = sc.nextInt()
	val m = sc.nextInt()

	// 続くK行には、単語リストに乗っている単語を表す文字列が与えられます。
	val d = mutableSetOf<String>()
	for (i in 1..k)
		d.add(sc.next())

	// しりとりクラスをインスタンス化します。
	val wordChain = WordChain(n, d)

	// 続くM行には、しりとりで行われた発言を表す文字列が与えられます。
	for (i in 1..m)
		wordChain.say(sc.next())
	sc.close()

	// 最終的にしりとりから脱落せずに残っている人の人数を表す整数を出力します。
	println(wordChain.nAlives)

	// 最終的にしりとりから脱落せずに残っている人の番号を小さい方から出力します。
	for (i in 0 until n) {
		if (wordChain.isAlive(i))
			println(i + 1)
	}
}
```