問題一覧 > 通常問題

No.335 Kadomatsu Lottery

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 62
作問者 : nmnmnmnmnmnmnm
お気に入りにしたユーザー ProblemId : 936 / 自分の提出
問題文最終更新日: 2026-06-25 06:28:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 129 (順位表) の他の問題:

Problem Statement

A kadomatsu sequence is defined as follows: when 3 integers are arranged as A, B, C from the left,
all the values are distinct and the second largest integer among A, B, C is either A or C.

The "Kadomatsu Lottery" is a lottery that uses kadomatsu sequences to determine winners.
First, each lottery ticket has N numbers written in a single horizontal row from the left.
The numbers are positive integers in the range from 1 to N, with no duplicates.

Winning is checked using 3 distinct numbers.
2 distinct winning numbers out of the 3 are made public at the time of the winning number announcement.
These 2 distinct winning numbers are chosen uniformly from the numbers 1 to N.

The last winning number can be freely chosen by yourself after seeing the 2 numbers.
The 3 winning numbers are located on the lottery ticket and extracted without changing their order from the left.
If the 3 numbers then form a kadomatsu sequence, the maximum of the 3 numbers is the prize amount.
If no kadomatsu sequence can be formed in any way, the prize amount is 0.

D-kun is considering buying a Kadomatsu Lottery ticket before the winning numbers are announced.
Right now, he can look at the numbers written on M lottery tickets and buy one of them.
After the winning numbers are announced, D-kun makes the choice that gives the highest prize amount.
He wants to buy the lottery ticket with the highest expected prize amount, so determine which one it is.

Input

$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 is the count of numbers written on a Kadomatsu Lottery ticket, and the numbers used are from 1 to N. $3\le N \le 800$.
M is the number of Kadomatsu Lottery tickets to choose from. $2\le M \le 3$.
$E_{i,j}$ represents the positive integer written j-th from the left on the i-th lottery ticket. $1\le E_{i,j} \le N$.
The numbers written on the i-th lottery ticket contain no duplicates.

Output

Which lottery ticket in the input should be bought?
Output the answer as a 0-indexed position.
If there are multiple answers, the smallest position is the answer.
Do not forget the newline at the end.

Sample

Sample 1
Input
4 2
4 3 1 2
1 2 3 4
Output
0

The 0-th Kadomatsu Lottery ticket has the 4 integers "4 3 1 2" written from the left.
If the 2 distinct numbers chosen are "1 and 2", choosing "4" last gives a prize amount of 4.
If the 2 distinct numbers chosen are "1 and 3", choosing "2" last gives a prize amount of 3.
If the 2 distinct numbers chosen are "1 and 4", choosing "2" last gives a prize amount of 4.
If the 2 distinct numbers chosen are "2 and 3", choosing "1" last gives a prize amount of 3.
If the 2 distinct numbers chosen are "2 and 4", choosing "1" last gives a prize amount of 4.
If the 2 distinct numbers chosen are "3 and 4", no kadomatsu sequence can be formed. The prize amount is 0.
Therefore, the expected prize amount is 4$\times$3/6+3$\times$2/6, which is 3.
The 1-st Kadomatsu Lottery ticket has the 4 integers "1 2 3 4" written from the left.
The 1-st lottery ticket cannot form a kadomatsu sequence for any winning numbers.
Therefore, the expected prize amount is 0.
Hence, we can see that the 0-th Kadomatsu Lottery ticket should be bought.

Sample 2
Input
3 3
1 2 3
1 2 3
3 2 1
Output
0

It is clear before buying that no Kadomatsu Lottery ticket can ever win, whichever one is bought.
However, the expected prize amount is 0 for all of them, so the answer is the smallest position, 0.

Sample 3
Input
5 3
2 1 3 4 5
3 2 1 5 4
5 2 4 1 3
Output
1

Sample 4
Input
6 3
1 3 2 4 5 6
1 2 4 5 3 6
1 4 3 5 6 2
Output
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。