DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

格子の整列

問題に戻る

解説

奇数行を左から右、偶数行を右から左へ読む長さ K=N2K=N^2K=N2 の蛇行経路を作る。経路で隣り合うマスは格子でも隣接する。

この経路を一次元配列と見て、未確定範囲を一つずつ縮めるバブルソートの比較を出力する。値を読む必要はない。右向きの辺には種類 222、下向きには種類 111、左向きには種類 444 を使う。左向きの場合は左側のマスの座標を指定する。

最初の段階は K(K−1)/2K(K-1)/2K(K−1)/2 回で経路を昇順にする。各行に必要な値はそろっているが偶数行は逆順なので、各偶数行を種類 222 のバブルソートで整列する。

操作数は

X=N2(N2−1)2+⌊N2⌋N(N−1)2≤N42+N34≤N4.X=\frac{N^2(N^2-1)}2+\left\lfloor\frac N2\right\rfloor\frac{N(N-1)}2\leq\frac{N^4}{2}+\frac{N^3}{4}\leq N^4.X=2N2(

出力時間は O(N4)O(N^4)O(N4)、経路保存は O(N2)O(N^2)O(N2)。N=30N=30N= では となる。 で、検査予算の分子は 。すべての演算は符号付き ビット整数に収まる。

サブタスク 1 の単純実装は経路全体へのバブルソートを KKK 周行い、偶数行を修正する。N=2,3,4N=2,3,4N=2,3,4 でそれぞれ 13,75,25213,75,25213,75,252 回となり制限内である。全範囲では確定済みの末尾を省いて最初の段階を K(K−1)/2K(K-1)/2 回に減らす。

チェッカーは操作を O(X)O(X)O(X) 空間に保存し、O(⌊108/N4⌋(N2+X))O(\lfloor10^8/N^4\rfloor(N^2+X))O(⌊108/N4⌋(N 時間で検査する。

Solution written by GPT6

N
2
−
1
)
​
+
⌊2N​⌋2N(N−1)​≤
2N4​+
4N3​≤
N4.
30
X=411 075X=411\,075X=411075
N4≤810 000N^4\leq810\,000N4≤810000
10810^8108
646464
K
(
K
−
1)/2
2
+
X))