No.335 門松宝くじ
nmnmnmnmnmnmnm問題文
門松列とは3つの整数が左からA、B、Cと並んでいる時に、
全ての値が異なりA、B、Cのうち2番目に大きな整数がAかCである場合をいう。
「門松宝くじ」は当たりの判定に門松列を利用した宝くじだ。
まず、1枚の宝くじ券にはN個の数が左から横に1列に書かれている。
数は範囲が1からNまでの正の整数で同じ数の重複は無い。
宝くじの当選の確認は異なる3つの数を用いて行う。
3つのうち2つの異なる当選番号は当選番号発表時に公表される。
この2つの異なる当選番号は1からNの数の中から偏りなく2つ選ばれる。
最後の1つの当選番号は2つの数字を見た後で自分で自由に1つ選ぶことができる。
3つの当選番号を宝くじ券の中から探し左からの順番を変えずに取り出す。
このとき3つの数が門松列になっていたら3つの数の最大値が当選金額となる。
どうやっても門松列が作れない場合は当選金額は0である。
D君は当選番号が発表される前に門松宝くじ券の購入を考えている。
いまM枚の宝くじ券のうち書かれた数を見てそのうちどれか1枚を購入できる。
D君は当選番号発表後に最も高い当選金額を得る選択をする。
当選金額の期待値が最も高い宝くじ券を購入したいのでどれかを判定せよ。
入力
$N\ M$
$E_{0,0}\ E_{0,1}\ \dots\ E_{0,N-1}$
$E_{1,0}\ E_{1,1}\ \dots\ E_{1,N-1}$
$\vdots$
$E_{M-1,0}\ E_{M-1,1}\ \dots\ E_{M-1,N-1}$
Nは門松宝くじ券に書かれた数の個数であり使用される数は1からNまでである。$3\le N \le 800$。
Mは選ぶことのできる門松宝くじの枚数。$2\le M \le 3$。
$E_{i,j}$はi番目の宝くじ券の左からj番目に書かれた正の整数を表す。$1\le E_{i,j} \le N$。
i番目の宝くじ券に書かれる数には重複するものは無い。
出力
入力で得られた何番目の宝くじ券を購入すべきか？
答えを0-indexの順番で答えよ。
複数答えがある場合は順番の小さいものを答えとする。
なお、最後に改行を忘れずに。
サンプル
サンプル1
入力
4 2 4 3 1 2 1 2 3 4
出力
0
0番目の門松宝くじ券には「4 3 1 2」と左から4つの整数が書かれている。
異なる2つの数字に「1と2」が選ばれた場合、最後に「4」を選ぶと当選金額は4である。
異なる2つの数字に「1と3」が選ばれた場合、最後に「2」を選ぶと当選金額は3である。
異なる2つの数字に「1と4」が選ばれた場合、最後に「2」を選ぶと当選金額は4である。
異なる2つの数字に「2と3」が選ばれた場合、最後に「1」を選ぶと当選金額は3である。
異なる2つの数字に「2と4」が選ばれた場合、最後に「1」を選ぶと当選金額は4である。
異なる2つの数字に「3と4」が選ばれた場合、門松列はできません。当選金額は0である。
よって、当選金額の期待値は4$\times$3/6+3$\times$2/6で3である。
1番目の門松宝くじ券には「1 2 3 4」と左から4つの整数が書かれている。
1番目の宝くじ券はどのような当選番号でも門松列を作れない。
よって、当選金額の期待値は0である。
したがって、0番目の門松宝くじ券を購入するべきだとわかる。
サンプル2
入力
3 3 1 2 3 1 2 3 3 2 1
出力
0
どの門松宝くじ券を買っても絶対に当たらないことは買う前からわかる。
ただ、当選金額の期待値はどれも0としてもっとも小さい順番の0番目を答えとする。
サンプル3
入力
5 3 2 1 3 4 5 3 2 1 5 4 5 2 4 1 3
出力
1
サンプル4
入力
6 3 1 3 2 4 5 6 1 2 4 5 3 6 1 4 3 5 6 2
出力
2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。