2017年夏エンジニア向けインターンシップの事前課題を解説

f:id:opttechnologies2015:20171130214739p:plain

2017年夏エンジニア向けインターンシップの選考に用いた事前課題の解説記事です。

なお、この記事はOpt Technologies Advent Calendar 2017の22日目です。

あいさつ
2017年夏エンジニア向けインターンシップ
課題内容
想定解法
提出されたその他の解法
- 発言表の行の内容が高々2種類となることを利用
- 発言表が対称行列となることを利用
よくあるミス
- 自己矛盾を含むケース
- 嘘つきの人数で矛盾や曖昧となるケース
まとめ

あいさつ

こんにちは。オプトテクノロジーズの潮田です。社内では主にDFO*1ツール Feed Terminalの開発/運用を担当しています。

最近はシニアエンジニアという肩書きを拝命して身が引き締まる思いです。がんばるぞい。

2017年夏エンジニア向けインターンシップ

オプトテクノロジーズは夏期にエンジニア向けインターンシップを開催しました。

その選考の一環として、いわゆる競技プログラミング的な事前課題を出題したのですが、どの方もそれぞれに考えて解答されていてとても興味深かったです。

この記事では、作問担当者である自分の想定していた解法、及び提出された解法をいくつか紹介します。

課題内容

課題内容はこちらをご覧ください。

論理パズルでよくある、正しい事しか言わない正直者と間違った事しか言わない嘘つきを題材にしています。

想定解法

「iさんは『jさんは正直者だ』と言っている」(P_ijが1)というのは以下の2通りの場合があります。

iさんは正直者でありjさんも正直者である
iさんは嘘つきでありjさんも嘘つきである

同様に「iさんは『jさんは嘘つきだ』と言っている」(P_ijが0)というのは以下の2通りの場合があります。

iさんは正直者でありjさんは嘘つきである
iさんは嘘つきでありjさんは正直者である

ここから、発言者iが正直者か嘘つきに関わらず、iとjが同グループの時はP_ijが1となり、別グループの時はP_ijが0となることが分かります。

この考察を用いると、誰か1人のN個の発言を見るだけでグループ分けをすることができます。

どちらのグループが嘘つきかはまだ不明ですが、それが不明であっても「得られたグループ分けのもとで各人はこう発言するはず」というシミュレーションは可能です。上の考察の通り、各発言は相手が同グループか否かだけで決まるからですね。

シミュレーション結果と実際の発言で食い違いがあったら矛盾です。

食い違いが無い場合は各グループの人数を調べます。嘘つきとしてありうるのは人数がLのグループだけ、と絞ることで、嘘つきの特定または矛盾/曖昧判別をすることができるでしょう。

これを実装すると、例えばScalaでは以下のように書けます。

object Main {
  // nLiar人の嘘つきとして矛盾しない組み合わせを全て返す
  def solve(nTotal: Int, nLiar: Int, statements: Array[Array[Int]]): Seq[Seq[Int]] = {
    // 先頭の人の発言(det)に基いてグループ分けし、そのグループ分けで各発言が矛盾していないかチェック
    val det = statements.head
    val consistent =
      (0 until nTotal).forall { i =>
        (0 until nTotal).forall { j =>
          // 同グループなら1、別グループなら0であるはず
          val expected = if (det(i) == det(j)) 1 else 0
          statements(i)(j) == expected
        }
      }

    if (!consistent) {
      Nil
    } else {
      val (group0, group1) = (1 to nTotal).partition(i => det(i - 1) == 0)
      // nLiar人のグループだけ残して返す
      Seq(group0, group1).filter(_.size == nLiar)
    }
  }

  def main(args: Array[String]): Unit = {
    val in = new java.util.Scanner(System.in)
    val nTotal = in.nextInt
    val nLiar = in.nextInt
    val statements = Array.fill(nTotal)(Array.fill(nTotal)(in.nextInt))

    val result = solve(nTotal, nLiar, statements) match {
      case Nil => "Inconsistent"
      case Seq(liars) => liars.mkString(" ")
      case _ => "Ambiguous"
    }
    println(result)
  }
}

提出されたその他の解法

発言表の行の内容が高々2種類となることを利用

正直者達のN個の発言は一致し、嘘つき達のN個の発言も一致することから、発言表の行の内容は高々2種類とならねばなりません。また、正直者の発言と嘘つきの発言は正反対となることから、一方の行の0と1を反転させたものが他方の行となります。

この観点で発言の矛盾を検査した解法は最も多かったですね。

発言表が対称行列となることを利用

iさんがjさんを正直者と言っている時、jさんもiさんを正直者と言っているはずです。嘘つきと言っている場合も同様なので、発言表は対称行列とならねばなりません。

この観点での検査をベースにした解法が次点で多かったです。

よくあるミス

この事前課題は満点でなければ不可というものではありませんが、用意していたテストケースを全て正解したのはわずか1名でした。

大筋は合っているのにコーナーケースで満点を逃した惜しい解答が多かったため、考慮漏れとなりがちだったケースもご紹介します。

自己矛盾を含むケース

「自分は嘘つきだ」と言っている人が存在するケースです。この場合、その人を正直者と仮定しても嘘つきと仮定しても矛盾します。

上述の2つのアイデアだけではこの矛盾を検知できないため、忘れずに検査する必要があります。

// 自己矛盾しており、どのL人を嘘つきと仮定しても矛盾するので Inconsistent
3 2
0 0 1
0 0 1
1 1 0

嘘つきの人数で矛盾や曖昧となるケース

両グループとも人数がLでないケース(矛盾)や両グループとも人数がLのケース(曖昧)もあるため注意が必要です。

「一方のグループで人数がLだったらそれを出力、Lでなかったら他方を出力」とだけしていると漏れてしまいますね。

// 3人と1人のグループに分かれており、2人のグループは無いので Inconsistent
4 2
1 1 1 0
1 1 1 0
1 1 1 0
0 0 0 1

// 2人と2人のグループに分かれており、どちらのグループが嘘つきか特定できないので Ambiguous
4 2
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1