色塗り(Grid Coloring)

K 理事長は縦N 行,横N 列のマス目で表される模様を作ろうとしている.そのために,各マスに整数の
番号で表される色を塗ることにした.以降,上からi 行目(1 ≦i ≦N),左からj 列目(1 ≦j ≦N) のマスを
マス(i, j) と呼ぶことにする.
現時点で,1 列目と1 行目のマスには既に色が塗られている.具体的には,マス(i, 1) (1 ≦i ≦N) は色Ai
で,マス(1, j) (1 ≦j ≦N) は色Bj で塗られている.ここでA1 = B1 である.
残りのマスについて,K 理事長は以下の手順で色を塗っていく.
• i = 2, 3, . . . , N の順に,以下の手順でi 行目のマスに色を塗る.
◦j = 2, 3, . . . , N の順に,マス(i, j) を
* マス(i −1, j) に塗られている色
* マス(i, j −1) に塗られている色
のうち番号が大きい方の色で塗る.番号が同じ場合は,その色で塗る.
K 理事長は,最終的にN2 個のマスすべてに色が塗られたとき,最も多くのマスに塗られた色の番号,お
よびその色が塗られているマスの個数を求めたい.
マス目の大きさおよび1 列目と1 行目のマスの情報が与えられたとき,最も多くのマスに塗られた色の
番号とその色が塗られているマスの個数を求めるプログラムを作成せよ.最も多くのマスに塗られた色の番
号が複数存在する場合,そのうち最も番号の大きいものを求め出力すること.

• 2 ≦N ≦200 000.
• 1 ≦Ai ≦109 (1 ≦i ≦N).
• 1 ≦Bj ≦109 (1 ≦j ≦N).
• A1 = B1.
• 入力される値はすべて整数である.

1. (15 点) N ≦500,Ai ≦100 000 (1 ≦i ≦N),Bj ≦100 000 (1 ≦j ≦N).
2. (10 点) N ≦500.
3. (20 点) Ai ≦2 (1 ≦i ≦N),Bj ≦2 (1 ≦j ≦N).
4. (25 点) Ai < Ai+1 (1 ≦i ≦N −1),Bj < Bj+1 (1 ≦j ≦N −1).
5. (30 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
N
A1 A2 · · · AN
B1 B2 · · · BN

標準出力に,最も多くのマスに塗られた色の番号と,その色が塗られているマスの個数を空白区切りで1
行に出力せよ.最も多くのマスに塗られた色の番号が複数存在する場合,そのうち最も番号の大きいものを
出力すること.

第24 回日本情報オリンピック(JOI 2024/2025) 本選
2025 年2 月2 日(オンライン開催)

생성자가 기록되지 않았습니다.

출처 JOI 2025 Final