ABC461参加記

はじめに

こんにちは。Caffeineholicです。

かろうじて4完を達成しレートも上昇してはいるものの、今回は問題設定が原因で不満の残るコンテストとなってしまいました。

…

計算量を！！インタープリタ言語のオーバーヘッドを！！考えろ！！こちとらPython使いだぞ！！！難しい問題つくるクセに掛け算できないのか！？

……

… などと叫ぶのは心の中だけに留めておきましょう。たとえ公式解説に $500$ の $3$ 乗オーダーしか書かれていなくとも、たとえ低速な言語にしか精通していなくとも、それを理由に土曜日の深夜に自宅で大声を上げる行為は、多様性が謳われるこの時代にもさすがに尊重されません。

結果サマリ

ABC461
WCPC参加人数: 4人
各問題の最速解答者(ペナルティ無し):

問題	参加者名	タイム	言語
A	ShoboiNamae	0:53	C++
B	kotomiko	3:11	C++
C	ShoboiNamae	13:15	C++
D	ShoboiNamae	55:21	C++
E	-	-	-
F	-	-	-
G	-	-	-

今週の出題

ABC461-A

問題文を表示

問題文

高橋君は鎧を着ています。

この鎧は威力（整数で表される攻撃の強さ）が $D$ 以下の攻撃をすべて防ぎますが、威力が $D$ より大きい攻撃は防ぎません。

この鎧は威力が $A$ の攻撃を防ぎますか。

制約

$1 \le A \le 100$
$1 \le D \le 100$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$A$

$D$

出力

鎧が攻撃を防ぐなら Yes、防がないなら No と出力せよ。

A問題の解説は割愛します。簡単に解けると思います。

ABC461-B

問題文を表示

問題文

$N$ 人の木こり $1, 2, \dots, N$ が斧を $1$ 個ずつ持っています。全員が斧を池に落としてしまいました。

池に $N$ 個の斧 $1, 2, \dots, N$ が沈んでいました。

各木こり $i$ は「自分が持っていた斧は斧 $A_i$ である」と主張しています。

一方、この池の女神は、各斧 $i$ を持っていたのは木こり $B_i$ であることを知っています。

$N$ 人の木こり全員が本当のことを言っているかどうかを判定してください。

制約

$1 \le N \le 100$
$1 \le A_i \le N$
$1 \le B_i \le N$
$A_i \neq A_j \ (i \neq j)$
$B_i \neq B_j \ (i \neq j)$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$A_1 \ A_2 \ \dots \ A_N$

$B_1 \ B_2 \ \dots \ B_N$

出力

$N$ 人の木こり全員が本当のことを言っているならば Yes を、そうでないならば No を出力せよ。

配列操作がややこしいです。私は0-indexedに揃えるのを忘れて時間を取られました。

冷静にコーディングすることはもちろんですが、できる工夫もあります。

競プロプレイヤーには少ないかもしれませんが、わかりにくくなるだろうなと思った問題では変数に必ず英単語を使用するようにしています。

ABC461-C

問題文を表示

問題文

$N$ 個の宝石があります。

$i$ 番目の宝石の色（整数で表されます）は $C_i$ で価値は $V_i$ です。

この $N$ 個の宝石の中から $K$ 個を選びます。ただし、選んだ宝石の色が $M$ 種類以上なければなりません。

このとき、選んだ宝石の価値の総和としてありうる最大値を求めてください。（与えられる入力では、このような選択が必ず可能です。）

制約

$1 \le M \le K \le N \le 2 \times 10^5$
$1 \le C_i \le N$
$1 \le V_i \le 10^9$
$M$ 種類以上の色の宝石が存在する
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N \ K \ M$

$C_1 \ V_1$

$C_2 \ V_2$

$\vdots$

$C_N \ V_N$

出力

選んだ宝石の価値の総和としてありうる最大値を整数として出力せよ。

C問題全体でみると、かなり簡単に見える難易度でした。この問題に求められているのは「色ごとに大きい順に宝石を保持できるデータ構造」ですから、連想配列の出番です。

汚い実装ですが、私は連想配列にソートした配列を格納し、条件の種類数をひとつずつ取り出したあとにもう一度配列に入れなおすという処理を書きました。もっといいやり方があったような気もしますが、C問題まではそこそこのタイムでACできました。

ABC461-D

問題文を表示

問題文

$H \times W$ のグリッドがあり、各マスには $0$ または $1$ の整数が書き込まれています。

各マスに書き込まれた整数の情報は $H$ 個の長さ $W$ の文字列 $S_1, S_2, \dots, S_H$ として与えられます。 $S_i$ の $j$ 文字目が 0 である時はグリッドの上から $i$ 行目、左から $j$ 列目に $0$ が書き込まれており、 $S_i$ の $j$ 文字目が 1 である時はグリッドの上から $i$ 行目、左から $j$ 列目に $1$ が書き込まれています。

書き込まれた整数の総和が $K$ となる長方形領域がいくつあるか求めてください。

厳密には、以下の条件を全て満たす整数の四つ組 $(r_1, c_1, r_2, c_2)$ がいくつあるか求めてください。

$1 \le r_1 \le r_2 \le H$
$1 \le c_1 \le c_2 \le W$
グリッドの上から $i$ 行目、左から $j$ 列目に書き込まれた整数を、 $r_1 \le i \le r_2, c_1 \le j \le c_2$ を満たす全ての整数組 $(i,j)$ について足し合わせた値が $K$ である。

制約

$1 \le H, W \le 500$
$0 \le K \le H \times W$
$S_i$ は 0, 1 からなる長さ $W$ の文字列
入力される値（ $H, W, K$ ）はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$H \ W \ K$

$S_1$

$S_2$

$\vdots$

$S_H$

出力

答えを出力せよ。

今回私が怒り心頭で書き始めていた原因となっているD問題です。 $\mathcal{O}(H \times W^2)$ 解法を思い付きはしたものの、

$H \le 500, W \le 500$ の制約の中で何度も二次元累積和クラスから区間和メソッドを引っ張り出すという書き方をしてしまったために、TLEを喰らってしまいました。

$10^8$ 程度の処理回数なら重い処理を除けばPythonでも通ることもあるという経験則はあるものの、初めて言語の壁のようなものにぶち当たってしまったと動揺し、できる高速化処理を調べては書き直すという面倒に走りました。通ったからよかったようなものの…

しかし終わってみれば、 $500^3$ は $125,000,000$ とはじめからかなり怪しい値になりますから、それを鑑みてコーディングの時点で軽量な処理に書き換えることは可能だったかもしれません。

このことから、私のTLEは経験不足と判断ミスからきた失敗だともいえます。

解法にも言及すると、グリッドのある範囲上で何かを数え上げたり、数列上を複数の変数を使って走査するような問題では、考えやすいように一つの変数を固定して単純化するという見方が有効な場合があります。

この問題でいうと、探索範囲としての長方形の一辺の長さを固定するのがよさそうですね。 $\mathcal{O}(H^2 W^2)$ かかる長方形の全パターンを考える前に、まずはタテ幅が固定値だった場合にヨコ方向への探索を、 $\mathcal{O}(W^2)$ から $\mathcal{O}(W)$ などに短縮できるかどうかを考えました。これについては訓練を積んでいれば、累積和を利用すればよいことに気づけます。

方針が固まったら、あとはタテの辺の長さについて全探索するだけです。またタテとヨコが逆でも議論は同じです(テストケースがブラックボックスですが、天下のAtCoderがそこを偏らせるわけはありません)。

$H, W \le 400$ だったなら、考察のタテヨコが逆だったなら、結果は違ったかもしれないなどという野暮はご法度でしょう。AtCoder大好き。

ABC461-E

問題文を表示

問題文

$N$ 行 $N$ 列のグリッドがあります。はじめ、すべてのマスは白く塗られています。

$Q$ 回のクエリを与えられる順に処理してください。各クエリは以下のいずれかです。

タイプ 1: 整数 $R$ が与えられる。グリッドの上から $R$ 行目のマスをすべて黒く塗る。
タイプ 2: 整数 $C$ が与えられる。グリッドの左から $C$ 列目のマスをすべて白く塗る。

クエリを処理するたびに、処理が完了した時点でのグリッド内で黒く塗られているマスの個数を出力してください。

制約

$1 \le N, Q \le 3 \times 10^5$
タイプ 1 のクエリについて $1 \le R \le N$
タイプ 2 のクエリについて $1 \le C \le N$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N \ Q$

$\text{query}_1$

$\text{query}_2$

$\vdots$

$\text{query}_Q$

ここで、 $\text{query}_i$ が $i$ 回目のクエリであり、以下のいずれかの形式で与えられる。

タイプ 1:

$1 \ R$

タイプ 2:

$2 \ C$

出力

$Q$ 行出力せよ。

$i$ 行目には、 $i$ 回目のクエリの処理が完了した時点でのグリッド内で黒く塗られているマスの個数を出力せよ。

とっても面白い、そしてどこかで見たような設定のE問題でした。勘違いかな？

最近はC問題を解いたタイミングでDもEも見に行くようにしていますが、正直D問題を捨てて本気でE問題に集中しようか迷いました。まったく同じクエリと、それに直交する色の異なるクエリが過去にいつ出たかが重要なので、変化を累積させておいてキレイに解けないかなと考えていました。

またほのかにクエリ先読みテクニックを使えるような匂いがしていましたが、言語化できません…

結果論としては難易度が高い問題だったので、D問題に取り組んで正解でした。

最後に

終わってみれば面白い問題セットでした。が、最近記事を書く頻度が上がってきているような…代表は忙しそうですがなんとかして負担を押し付けられないものか。

憧れの5完には、まだまだ正確性と速度が足りないようです。新入生の子と一緒にC++の勉強もしたいし、課題は山積みですがゆっくり精進していきたいと思います。C++を始める理由？決して今回でPythonを使いたくなくなったからではありません。決して。

Caffeineholicでした。