オンサイトの競技プログラミング。会場の空気はほどよく張りつめていて、キーボードの打鍵音だけが一定のリズムで流れている。そんな中で、運営が出してきた問題数はまさかの26問。多い。多すぎる。
競技が終わって、いよいよ順位表が表示される。ところが、これがまた横に長い。Aから始まって、B、C……と続いて、画面の右端が見えない。スクロールしてもしても終わらない。隣のチームが「まだ右あるのか」と言いながら指を左右に動かしている。観戦している人も、順位は気になるのに、表が横に伸びすぎていて視線が迷子になる。
ここで運営側の事情が出てくる。画面に「Yes / No」の投票や案内を出すスペースがほしい。でも、この横に長い順位表が鎮座しているせいで、邪魔になる。だったら問題を1問減らして、表示を少しでもスッキリさせたい。そういう話になるのは自然だった。
ただし、当然ながら簡単には削れない。削ったせいで順位が動いたら、競技そのものの意味が変わってしまう。会場にいる全員が、あの26問を前提に走り切った。削除で順位が変わった瞬間に、納得感が崩れる。運営としてもそれは避けたい。削るなら、今の順位と変わらないことが条件になる。
候補として浮上するのが「一番後ろの問題」。つまり26問目、右端の端っこにあるあの問題を削る。見た目の改善にも効くし、端っこだから影響も小さそうに見える。だが、見た目で決めていい話ではない。大事なのは、その問題を消したときに最終順位が変わらないかどうかだ。
順位はICPCルール。評価は単純なようで厳密だ。まず、解いた問題数が多いチームが上。ここで並んだら、次はペナルティ、つまり「解いた各問題にかかった時間の総和」が小さいチームが上になる。だから、最後の問題を削ると何が起きるかは二段階で効いてくる。
まず第一に、あるチームがその問題を解いていたなら、その1問が消えることで解いた問題数が1つ減る。すると、同じ問題数だった相手に追い抜かれたり、1問差で勝っていた相手に追いつかれたりする可能性が出る。これは一発で順位が動く危険信号だ。
第二に、解いた問題数が変わらないケースでも安心できない。たとえば、その問題を解いていなかったチーム同士なら問題数は維持されるが、解いた問題の集合が変わるチームが混ざると、総時間が変わる。あの問題を解いたチームは、総和からその問題の時間が消える……のではなく、そもそも「解いた問題として数えない」扱いになるので、比較対象自体が変わる。結果として、同じ解いた問題数に集まったチーム同士のタイブレークで、総時間の大小が入れ替わりうる。
つまり、「最後の問題を削っても順位が変わらないか？」は、単にその問題を解いたチームが少ないかどうかでは決まらない。順位表の中で、どのチームが何問解いていて、どのチーム同士が問題数で並んでいて、さらにその並びの中で総時間がどれくらい拮抗しているか――そこまで見ないと確実な答えは出ない。
そこでやるべきことは明確になる。26問目を消した“仮想のコンテスト結果”を作る。そしてICPCルールで順位をもう一度作り直す。最後に、元の順位表と突き合わせて、1位から最下位まで完全に一致しているかを判定する。完全一致なら削除しても安全。一人でも位置がずれたら、その問題は削れない。
横に長すぎる順位表をスッキリさせたいという、表示上のちょっとした事情。けれど、その裏では「順位を1ミリも動かさない」という、競技としての公平性を守るための厳密な確認が必要になる。右端の問題を消すだけの話に見えて、実際には“別コンテストを再計算して同一性を証明する”という、地味に重たい判定問題になる――オンサイトの終わりにふさわしい、最後の一問がそこにある。
(このストーリーは ChatGPT によって生成されたものです。なお、コンテスト中の生成AIの使用は原則禁止されています)
あるオンサイトコンテストには、 チーム $1,2,\ldots,N$ の $N$ チームが参加し、問題 $1,2,\ldots,26$ の $26$ 問が出題されました。 コンテスト終了までに、すべてのチームが問題 $26$ を正解しました。
最終結果では、チーム $i$ は単独で $i$ 位でした (同順位のチームが存在しないことが保証されます)。 また、チーム $i$ は全体で $C_i$ 問を正解し、合計所要時間は $S_i$、問題 $26$ を正解するまでに要した時間は $Z_i$ であることがわかっています。
あなたのタスクは、すべてのチームの成績から問題 $26$ を除外して再集計したとき、順位が元の結果から変化しないかを判定することです。
より厳密には、問題 $26$ を除外したあとのチーム $i$ の正解数を $X_i(=C_i-1)$、合計所要時間を $Y_i(=S_i-Z_i)$ としたとき、任意の $1\leq i < N$ について、以下のいずれかが成り立つかを判定してください。
すべての $i$ について上記の条件が成り立つ場合は Yes、そうでない場合は No を出力してください。
入力は以下の形式で標準入力から与えられます。
$N$ $C_1$ $S_1$ $Z_1$ $C_2$ $S_2$ $Z_2$ $\vdots$ $C_N$ $S_N$ $Z_N$
答えを $1$ 行に出力してください。
4 25 80 2 25 82 1 24 90 11 23 50 5
Yes
最後の問題を除外したときに、各チームの (解いた問題数, かかった時間) は以下のようになります。
順位が変わらないため Yes を出力してください。
4 25 80 2 25 82 10 24 90 11 23 50 5
No
最後の問題を除外したとき、各チームの (解いた問題数, かかった時間) は以下のようになります。
チーム $1$ とチーム $2$ について、解いた問題数が同じであり、さらにチーム $1$ のほうがチーム $2$ よりも所要時間が長くなっています。そのため、順位が入れ替わります。
したがって、No を出力してください。