ABC471参加記

はじめに

こんにちは。Caffeineholic です。

世間は夏休みムード一色ですが、持ち前のフットワークの重さを発揮し夏を謳歌しきれていない私です。 AtCoderにだけはほぼ毎週欠かさず参加できており、今回はABCDの4問を解くことができました。しかしそろそろレートが停滞してきています。今回のE問題のような問題への対応力を磨きたいです。

結果サマリ

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

問題	参加者名	タイム	言語
A	Caffeineholic	1:05	Python
B	Caffeineholic	2:04	Python
C	ShoboiNamae	13:52	C++
D	ShoboiNamae	29:33	C++
E	ShoboiNamae	67:01	C++
F	-	-	-
G	-	-	-

今週の出題

ABC471-A

問題ページ: A問題

問題文を表示

問題文

正の整数 $A, B$ が与えられます。以下の値のうち少なくとも $1$ つが $9$ に等しい場合は Nine を、そうでない場合は Nein を出力してください。

$A+B$
$A-B$
$A \times B$
$A \div B$

制約

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

入力

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

$A \ B$

出力

答えを出力せよ。

長い条件式を書きました。

if a+b == 9 or a-b == 9 or a*b == 9 or a == 9*b:
    ans = "Nine"

ABC471-B

問題ページ: B問題

問題文を表示

問題文

高橋君はアンケート結果を集計しています。アンケートには $N$ 人が回答し、 $i$ 人目の回答は英字からなる文字列 $S_i$ です。このアンケートにおいて、同じ回答をした人数の最大値を求めてください。ただし、回答の大文字と小文字は区別しません。例えば AtCoder, ATCODER, atcoder はいずれも同じ回答とみなします。

制約

$1 \le N \le 100$
$S_i$ は長さ $1$ 以上 $10$ 以下の、英大文字及び英小文字のみからなる文字列
$N$ は整数である

入力

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

$N$
$S_1$
$\vdots$
$S_N$

出力

答えを出力せよ。

Pythonにはstr型を大文字に破壊的に変更する upper() メソッドがあるので、私はそれを利用しました。すべての文字列を一旦大文字に変換して比較するという考え方です。他言語では、受け取った文字列S内のすべてのASCII値について32とOR演算することで小文字化するというテクニック(コード例の二つ目)もあるようです。

大文字 (‘A’ = 01000001) と小文字 (‘a’ = 01100001) は6ビット目のみが異なりますから、そこを揃えるという意味です。

文字列sに対する処理部分のコード例：

// 大文字なら、小文字に揃えるためにASCII差分で更新
for (char &c : s) {
    if ('A' <= c && c <= 'Z') {
        c = c - 'A' + 'a';
    }
}

// 0b00100000 = 32 と OR演算
for (char &c : s) {
    c |= 32;
}

ABC471-C

問題ページ: C問題

問題文を表示

問題文

数直線上の $N$ 箇所にクッキーが落ちています。 $i$ 番目のクッキーの落ちている座標は $A_i$ です。高橋君は最初、数直線の座標 $0$ にいて、 $N$ 個のクッキー全てを拾うまで以下の行動を繰り返します。

行動：自身から最も近いクッキーのある座標(複数あるときは座標の最も小さいもの)へ移動し、そのクッキーを拾う。

全てのクッキーを拾うまでの高橋君の移動距離の合計を求めてください。

制約

$1 \le N \le 3 \times 10^5$
$-10^9 \le A_i \le 10^9$
$A_i \neq 0$
$A_i$ は相異なる
入力は全て整数である

入力

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

$N$
$A_1 \ \ldots \ A_N$

出力

答えを出力せよ。

解くために何がしたいのかを言語化しましょう。毎回「今いる座標から最も近いクッキーのある座標」を高速に探し、拾ったクッキーは検索対象から除外したいとなれば、Pythonの外部ライブラリsortedcontainersのSortedListクラスが利用できるとすぐに思いつけます。 C++ではデータ構造 std::set(ordered set) を利用できます。いずれも「二分探索」「要素の追加・削除」が高速にできるデータ構造です。

あるいは、開始座標が原点であること、常に現在地の左右2箇所しかチェックしなくても良いことを利用して、「負の座標にあるクッキーを順に並べたもの」「正の座標にあるクッキーを順に並べたもの」の二つのリストの端のみを見て比較し、要素を削除し続けるという解法も適切です。こちらのほうが美しいですね。コーディング負担も少なそうです。

ABC471-D

問題ページ: D問題

問題文を表示

問題文

無尽蔵の差込口をもつ充電器があります。時刻 $0$ にはどの差込口も空です。バッテリーの最大容量は $V$ です。バッテリーは差込口に挿入されているあいだ、残量が最大容量に達するまで速度 $1$ で充電されます(つまり、 $1$ 単位時間が経過するごとに残量が $1$ 増加します)。

$Q$ 個のクエリを順に処理してください。 $q$ 番目のクエリは以下の形式で与えられます。なお、 $t_1 < \dots < t_Q$ が保証されます。

タイプ 1 ( $1 \ t_q \ w_q$ ): 時刻 $t_q$ に、残量 $w_q$ のバッテリーを $1$ つ差込口に挿入する。
タイプ 2 ( $2 \ t_q$ ): 時刻 $t_q$ に、最も残量が多いバッテリーを $1$ つ差込口から排出し、そのバッテリーの残量を出力する。どの差込口にもバッテリーが無い場合は代わりに $-1$ を出力する。

制約

$1 \le Q \le 3 \times 10^5$
$1 \le V \le 10^9$
タイプ 1 のクエリにおいて、 $1 \le t_q \le 10^9$
タイプ 1 のクエリにおいて、 $0 \le w_q \le V$
タイプ 2 のクエリにおいて、 $1 \le t_q \le 10^9$
$t_1 < \dots < t_Q$
入力される値はすべて整数

入力

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

$Q \ V$
$\text{query}_1$
$\vdots$
$\text{query}_Q$

ここで、 $\text{query}_q$ は $q$ 番目のクエリを表し、以下の $2$ 種類のいずれかの形式で与えられる。

$1 \ t_q \ w_q$
$2 \ t_q$

出力

タイプ 2 のクエリの個数を $x$ として、 $x$ 行出力せよ。

$k$ 行目 ( $1 \le k \le x$ ) には、 $k$ 番目のタイプ 2 のクエリで出力するべき値を出力せよ。

クエリ2において、何を見て充電器残量を計算するかを考えます。現在時刻を $t$ 、ある充電中の充電器 $i$ の挿入された時刻を $t_i$ 、挿入された際の残量を $w_i$ とおくと、充電中の充電器 $i$ を取り出すときの残量は $w_i + (t - t_i)$ ですから、見やすいように書き換えて $t + (w_i - t_i)$ となります。この $w_i - t_i$ を挿入することと、最も大きいものを取り出すことが高速にできるデータ構造を使えば、解くことができます。優先度付きキュー や前述の SortedList (std::set) が利用できると思います。

各充電器の残量は ${V}$ を超えないことに注意します。

ABC471-E

問題ページ: E問題

問題文を表示

問題文

$1$ から $N$ の番号がついた $N$ 個のボールがあります。ボール $i$ には整数 $A_i$ が書かれています。

$N$ 個のボールからいくつかのボールを選ぶ方法に対して、選んだボールに書かれた数の和の $2$ 乗をその選び方のスコアと定めます。

$N$ 個のボールから $K$ 個を選ぶ方法 $\binom{N}{K}$ 通り全てのスコアの総和を $998244353$ で割った余りを求めてください。

制約

$1 \le K \le N \le 2 \times 10^5$
$1 \le A_i \le 10^9$
入力は全て整数

入力

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

$N \ K$
$A_1 \ \dots \ A_N$

出力

答えを出力せよ。

不勉強で申し訳ございませんが、まだ復習中です(次回からは多く解けたメンバーに記事を書かせ、自分はサボる作戦に出ようと画策しています)。 diffは低いので次見かけたら解けるようにしておきたいですね。式変形してある項の解への寄与数を考える問題には何度か出くわしていますが、解けずに終わることがほとんどで悔しいです。

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

最後に

なぜか休暇に入っても私のタスクは減っていませんが、力を抜けるところは抜いて、楽しいものは全力で楽しんでやっていきます。来週も頑張りましょう。 Caffeineholicでした。