ARC211(Div. 2) A - Banned X 2 考察メモ
(コンテスト中に考えたことの走り書き的なメモです)
まず、隣り合う要素が10にならないことを考えると、「(1,9),(2,8),(3,7),(4,6)の4ペア」と「5単体」の2つのケースについて考える必要があるとわかった。
そのため、1111...2222..33...888...999と雑に隣り合わせたいところだが、55555は隣同士が10になってアウトなので、そこまで単純ではない。
でも、1111...2222..33...888...999みたいに並べられたら、5をその並べた要素に挟み込んで(1515151...252525...みたいに)あげればいいので、とりあえず「5以外の要素」をどう並べるかを考えた。
まず、(1,9)について、つまり「1と9がどうしても隣り合わなければいけないパターン」はどのような時か」を考えた。それは、要素として1と9しか存在しない時、11111...111999...9999となるときのことで、その時答えは1となる。
次に(2,8)について、「2と8がどうしても隣り合わなければいけないパターン」は?と考えると、それは、要素として2と8しか存在しない時だとわかった。なぜなら、以下が言えるから。
・まず3~7に要素がある時→普通に間に挟めば222...22x888..888みたいになるからOK
・1~9に要素がある時→111...1222....999...8888みたいな感じで、並び替えてあげればいい。
イメージとしては、上みたいな感じ。
だから、(t, 10-t)のペア(t=1,2,3,4)について、まず、「tと10-tしか要素がないか」をチェックして、そうであるならば1を出力する。以下はそうでない場合。
そうでない時、あとは5が隣り合わずに済むかだけ考えればよくて、5を抜いた状態の数列は隣り合う要素が10でないものを構成できることが上の考察から示せているわけだから、単純に5以外の要素と5の要素数を比較して足りない分が答え。(具体的には、max((5以外の要素の合計数) - 1 - (5の要素数), 0)だけ必要)
以下が全体のアルゴリズム。
Discussion