ABC483参加記

はじめに

こんにちは、Caffeineholicです。今回のABCは4完にとどまりました。最近いくつか並行して個人的に記事を書いていますが、書いているうちに楽しくなってきました。その勢いのままこの記事も書ききってしまいます。参加記を書けていない回は他のメンバーが埋めてくれることを信じて。

成績としては、4完となりました。E問題が難しかったようです。 E問題を解ききっている人がとても少ないことが本番中の順位表からわかったので、ちらっと問題を見ただけで解かずに戻りました。判断としては正解だったようです。体感難易度としては A < B << D < C でしたね。

D問題までの所感を載せておきます。

結果サマリ

ABC483
WCPC参加人数: 5人
各問題の最速解答者（実AC時刻）:

問題	参加者名	タイム	言語
A	nsubaru	0:33	Java24 (OpenJDK 24.0.2)
B	nsubaru	3:55	Java24 (OpenJDK 24.0.2)
C	nsubaru	29:41	Java24 (OpenJDK 24.0.2)
D	nsubaru	65:01	Java24 (OpenJDK 24.0.2)
E	-	-	-
F	-	-	-
G	-	-	-

今週の出題

ABC483-A

問題ページ

問題文を表示

問題文

正整数 $N$ が与えられます。

$N$ ページからなる資料をコピー用紙に印刷します。

印刷には両面印刷を使い、コピー用紙 1枚の表と裏にそれぞれ $1$ ページずつ印刷することができます。

$N$ ページを全て印刷するために必要なコピー用紙の枚数の最小値を求めてください。

制約

$1\le N\le 100$
入力される値は整数

入力

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

$N$

出力

答えを出力せよ。

$5$ ページまたは $6$ ページの資料なら3枚の用紙に印刷できます。 $2n-1$ ページまたは $2n$ ページの資料なら $n$ 枚の用紙に印刷できます。私は計算ミスで焦ることを恐れてif文を使ってゆっくり書きましたが、最短で書くならこうです。

n = int(input())
print((n + 1) // 2)

ABC483-B

問題ページ

問題文を表示

問題文

$1$ から $N$ までの番号が書かれた（表裏の区別できる） $N$ 枚のカードがあり、最初、上から $1,2,\ldots,N$ の順ですべて表向きで積まれています。

高橋君はこの山に $Q$ 回の操作を行います。 $i$ 回目（ $1\leq i\leq Q$ ）の操作では以下の操作を行います。

上から $K_i$ 枚のカードをひとまとめにして裏返し、元の位置に戻す。

これにより、上から $K_i$ 枚のカードの順序が上下逆になり、それぞれのカードの表裏も反転する。

すべての操作を終えた後のカードの順序と表裏を求めてください。

具体的には、 $i=1,2,\ldots,N$ について、上から $i$ 枚目に置かれているカードに書かれている番号が $X_i$ のとき、そのカードが表向きで積まれている時 $X_i$ を、裏向きなら $-X_i$ を出力してください。

制約

$1 \leq N,Q \leq 100$
$1 \leq K_i \leq N$
入力はすべて整数

入力

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

$N$ $Q$
$K_1$ $K_2$ $\cdots$ $K_Q$

出力

$N$ 行出力せよ。 $i$ 行目（ $1\leq i\leq N$ ）には、 $Q$ 回の操作の後で上から $i$ 枚目に置かれているカードに書かれている番号が $X_i$ のとき、そのカードが表向きで積まれている時 $X_i$ を、裏向きなら $-X_i$ を出力せよ。

Python使いはデータ構造Listに対してスライスという操作を行えるのでより簡単になりますが、各カード情報を配列に記録してfor文を使って作り直していくという操作で、比較的単純に解けるかと思います。 B問題らしいB問題でした。グリッド関連の問題が出ると焦りやすいので良かったです。

ABC483-C

問題ページ

問題文を表示

問題文

AtCoder 村で村長を決める投票を行うことになりました。

候補者は $N$ 人おり、候補者 $1$ , 候補者 $2$ , $\ldots$ , 候補者 $N$ と番号づけられています。

投票者は $M$ 人おり、 $i$ 人目 $(1\leq i\leq M)$ の投票者の投票先の第一希望は候補者 $A_i$ 、第二希望は候補者 $B_i$ です。

候補者のうち一人のみが辞退した時、それぞれの投票者は以下のように投票します。

第一希望の候補者が辞退していなければ、第一希望の候補者に投票する。
第一希望の候補者が辞退していれば、第二希望の候補者に投票する。

辞退していない候補者のうち、得票数が最大の候補者が当選します。そのような候補者が複数いる場合は、番号が最小の候補者が当選します。

$k=1,2,\ldots,N$ それぞれについて、候補者 $k$ のみが辞退した場合に当選する候補者の番号を求めてください。

制約

$2 \leq N \leq 2\times 10^5$
$1 \leq M \leq 2\times 10^5$
$1 \leq A_i,B_i \leq N$
$A_i\neq B_i$
入力はすべて整数

入力

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

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

出力

$N$ 行出力せよ。 $i$ 行目には、候補者 $i$ のみが辞退した場合に当選する候補者の番号を出力せよ。

僕たちが計算量マジックと呼んでいる類の問題です。一見不可能な回数の操作が必要であるように見えて、考察を進めると愚直にシミュレーションできることに気づくというものでした。こういう問題には出るたびに敗北を喫していますが、今回はSegmentTreeに二次元の情報を詰め込むというリッチな手段で解ききりました。

弁解をしておくと、途中から愚直なシミュレーションが通るという考察には至っていました。が、最初に書いた方法でも正解できるという自信があったためにその書き方に固執して、結果デバッグにかなりの時間を費やすことになってしまいました。 C問題に50分ほどかかりました。

ABC483-D

問題ページ

問題文を表示

問題文

数直線上にロボットがいます。はじめ、ロボットは座標 $0$ にいます。また、高橋君は長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ を持っています。

高橋君は次の操作を行います。

1. $A$ の要素を 高々 $1$ つ 選び、その符号を反転させる。すなわち、 $1\leq i\leq N$ をみたす $i$ を $0$ または $1$ つ選び、 $A_i$ を $-A_i$ に書き換える。

ロボットを起動する。ロボットは起動後、 $N$ 回の行動を行う。 $i$ 回目 $(1\leq i\leq N)$ の行動では、現在の座標を $x$ として、座標 $x+A_i$ へ直線的に移動する。

高橋君はロボットが一度以上通る整数座標の個数をなるべく多くしたいです。

高橋君が最適に行動したときの、「ロボットが一度以上通る整数座標の個数」としてあり得る最大の値を求めてください。

なお、ロボットは連続的に移動するものとし、ある移動で座標 $S$ から $T$ まで移動したとき、 $S\leq T$ ならば $S$ 以上 $T$ 以下の任意の整数座標、 $S>T$ ならば $T$ 以上 $S$ 以下の任意の整数座標を通ったとみなします。

制約

$1 \leq N \leq 2\times 10^5$
$-10^9 \leq A_i \leq 10^9$
$A_i\neq 0$
入力はすべて整数

入力

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

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

出力

高橋君が最適に行動したとき、ロボットが一度以上通る整数座標の個数としてあり得る最大の値を出力せよ。

動きのイメージが付けば実装を頑張るだけという問題だったと感じています。

$i$ 回目の移動の正負を反転させても $i+1$ 回目以降の移動の仕方は変わらないことに気づくことが大切です。左右への移動の仕方は変わらずその基点が $A_i$ の反転によって変わるだけ。だから、 $i-1$ 回目までと $i+1$ 回目以降とについての累積minと累積maxを利用して、仮に $i$ 回目の移動を反転した際に最終的な左右差がどれだけできるかを計算しました。

E問題以降は、割愛とさせていただきます。

最後に

今週もお疲れさまでした。そろそろサイトのデザインを改修したいです。

Caffeineholicでした。