先に答え：2種類のクエリを順番に処理する
ABC283 Bは、配列の指定位置を更新し、その時点の値を読む問題です。
1 k xは配列Aのk番目をxへ変更し、2 kはその時点のAのk番目を出力します。
クエリを入力順に処理し、Pythonでは問題文のkから1を引いてA[k - 1]へアクセスすれば、読込を含めて全体をO(N+Q)で実装できます。
| 形式 | 値の個数 | 意味 | Pythonでの処理 |
|---|---|---|---|
1 k x |
3個 | Aのk番目をxへ更新 | A[k - 1] = x |
2 k |
2個 | 現在のAのk番目を参照 | print(A[k - 1]) |
クエリの最初の値を種類として使います。
1なら3個の値を受け取って代入し、2なら2個の値を受け取って出力します。
種類と値の個数を逆に対応づけると、2 kに対してxまで取り出そうとして入力を処理できません。
Pythonのlistではkから1を引く
問題文の位置kは1から数えます。
一方、Pythonのlistは最初の要素をインデックス0で表します。
そのため、AtCoderのk番目はPythonではk - 1番目になり、更新と参照の両方で同じ変換を使います。
| 問題文の位置 | Pythonのインデックス | アクセス |
|---|---|---|
| 1 | 0 | A[0] |
| k | k – 1 | A[k - 1] |
| N | N – 1 | A[N - 1] |
listは要素を指定して代入できるので、A[k - 1] = xと書くと、その位置の値だけが置き換わります。
以後のクエリは置き換え後の配列を読むため、更新はその場でAへ反映します。
listのインデックスと要素代入はPython公式チュートリアルのlist型で確認できます。
公式サンプル1で配列の状態を追う
初期配列を(1, 3, 5)として、クエリを1行ずつ処理します。
| クエリ | 操作 | 処理後のA | 出力 |
|---|---|---|---|
| 開始 | 初期状態 | (1, 3, 5) |
なし |
2 2 |
2番目を参照 | (1, 3, 5) |
3 |
2 3 |
3番目を参照 | (1, 3, 5) |
5 |
1 3 0 |
3番目を0へ更新 | (1, 3, 0) |
なし |
2 3 |
更新後の3番目を参照 | (1, 3, 0) |
0 |
1 2 8 |
2番目を8へ更新 | (1, 8, 0) |
なし |
2 2 |
更新後の2番目を参照 | (1, 8, 0) |
8 |
2 1 |
1番目を参照 | (1, 8, 0) |
1 |
参照クエリは配列を変えず、更新クエリは出力せずに配列だけを変えます。
この順番で出力される値は、3、5、0、8、1です。
ABC283 Bの問題と制約
長さNの数列AとQ個のクエリを持ち、各クエリを入力順に処理して、参照クエリの答えを出力します。
- Nは1以上105以下です。
- Qは1以上105以下です。
- 初期値Aiと更新値xは0以上109以下です。
- kはすべてのクエリで1以上N以下です。
- 2 kのクエリは少なくとも1個あります。
入力は、N、初期配列、Q、続くQ個のクエリの順です。
N
A_1 A_2 ... A_N
Q
query_1
...
query_Qquery_iは1 k xまたは2 kのどちらかです。
出力は、2 kの個数と同じ行数で、各参照の答えを入力順に出します。
正確な形式、制約、サンプルはABC283 B 問題、配列を逐次処理する方針はABC283 B 公式解説で確認できます。
Python参考コード
各行をinput()で読み、split()した文字列をmap(int, ...)で整数へ変換します。
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
query = list(map(int, input().split()))
if query[0] == 1:
_, k, x = query
A[k - 1] = x
else:
_, k = query
print(A[k - 1])query[0]が1のときだけ3個の値へ分解し、query[0]が2のときは2個の値へ分解しています。
更新ではA[k - 1] = x、参照ではprint(A[k - 1])と、同じ位置変換を使いながら処理が分かれます。
input()、map()、int()の働きはPython公式のinput()、map()、int()で確認できます。
正しさを不変条件で確認する
このコードは、各クエリを処理する直前のAが問題の現在の数列と一致している、という不変条件で説明できます。
最初は入力されたAをそのまま使うため、不変条件が成り立ちます。
type 1では、問題文が指定したk番目に対応するA[k - 1]だけをxへ置き換えるので、更新後もAは現在の数列と一致します。
type 2では、その時点のA[k - 1]を出力するため、問題が求める値と一致します。
どちらのクエリの後も不変条件が保たれるので、Q個すべてを順番に処理したとき、各参照の出力が正しくなります。
境界と計算量
k = 1ならA[0]、k = NならA[N - 1]を使います。N = 1なら、更新も参照も唯一の位置A[0]を対象にします。x = 0やx = 109も制約内の更新値です。- 同じ位置を何度も更新した場合、参照が読むのは最後の更新後の値です。
- 参照クエリはAを書き換えないため、続くクエリは同じ配列状態から処理します。
初期配列を読む処理にO(N)、各クエリにO(1)かかるため、全体の計算量はO(N+Q)です。
配列Aを保持するためのメモリはO(N)です。
1クエリの入力は最大3個の整数だけなので、クエリ処理で使う追加メモリはO(1)です。
この記事で扱う範囲
この解説で扱うのは、配列の一点更新と一点参照です。
クエリが指定する1か所を直接読むため、毎回配列全体を調べる必要はありません。
区間全体を集約する問題の設計やデータ構造は、このコードの範囲に含めません。
練習するときは、各クエリについて処理前のA、クエリの種類、処理後のAまたは出力を書き出すと、更新と参照、そしてk - 1の対応を確認できます。
