はじめに
こんにちは。
この記事を担当する nsubaru です！Java 使いの緑コーダーです。
今回こそ E を解くぞと意気込んでいたものの、結果 D まで4完21分という、ただ速解きしてイスを温めるという回でした…
しかしメンバーのほぼ全員レートが上昇しており良い傾向です！！
結果サマリ
- コンテスト: ABC455
- 言語: Java
- 完答数: 4完（A-D）
- ペナルティ込み時間: 21分17秒
- 順位: 2591位
- パフォーマンス: 1185
- レート変動: 985 → 1007（+22）
- WCPC参加人数: 7人
今週の出題
ABC455-A
問題文を表示
問題文
整数 A, B, C が与えられます。A ≠ B かつ B = C であるならば Yes を、そうでないならば No
を出力してください。
制約
- 1 ≤ A, B, C ≤ 9
- 入力される値は全て整数
入力
A B C
出力
問題文中の指示に従って Yes, No のいずれかを出力せよ。
A問題はこれくらいであってくれって感じの簡単な判定問題でしたね。
bool を そのまま Yes/No で出力するメソッドを用意しているので、out.println(A != B && B == C); で瞬殺。
私は23秒ACで言語別1位に！！
ABC455-B
問題文を表示
問題文
H 行 W 列のグリッドがあります。各マスは白 (.) または黒 (#) で塗られています。
グリッドの長方形領域のうち、点対称に塗られているものの個数を求めてください。
制約
- 1 ≤ H, W ≤ 10
- H, W は整数
- S_i は
.,#からなる長さ W の文字列
入力
H W
S_1
S_2
⋮
S_H
出力
答えを出力せよ。
B問題では珍しくめんどくさい問題でした…
左上の座標を決定するループ、長方形のサイズを決定するループ、判定のループで計6重ループで解けます。
Javaならループにラベルを付与できるので、bool変数を使わないで書くこともできます。
解説には O(HW²) で解く方法もあるそうな…
ABC455-C
問題文を表示
問題文
整数列 A = (A_1, A_2, …, A_N) が与えられます。
次の操作をちょうど K 回行った後の A の各要素の和として考えられる最小値を求めてください。
- 整数 x を選び、A_i = x なる全ての i について A_i を 0 に置き換える。
制約
- 1 ≤ K ≤ N ≤ 3 × 10^5
- 1 ≤ A_i ≤ 10^9
- 入力される値は全て整数
入力
N K
A_1 A_2 … A_N
出力
答えを出力せよ。
Mapの練習問題です。
HashMap で各要素の出現回数を記録していき、key * value の配列を作成、ソートして 配列のサイズ-K 個の総和をとるだけで解けます。
マルチセット（要素に対してその個数を value に持つ Map）を読み込む関数などがあれば簡潔に書けます。
ABC455-D
問題文を表示
問題文
カードが N 枚、カードの山が N 個あります。初め、山 i にはカード i のみがあります。
各操作で「カード C_i とその上に積まれているカード」を順序を保ってカード P_i の上に移動します。
全ての操作後、各山に積まれているカード枚数を求めてください。
制約
- 1 ≤ N, Q ≤ 3 × 10^5
- 1 ≤ C_i, P_i ≤ N
- 各操作直前で C_i と P_i は異なる山にあることが保証される
- 各操作直前で P_i はある山の一番上にあることが保証される
- 入力される値はすべて整数
入力
N Q
C_1 P_1
C_2 P_2
⋮
C_Q P_Q
出力
最終的に山 i に積まれているカード枚数を A_i として、A_1, A_2, …, A_N を空白区切りで出力せよ。
今回もこのD問題が速く解けるかが大事でした。連結リストの構造を分かっていればすぐ思いつきそうな問題です。 この問題は、あるカードが現在どこのタワーにいるかを覚える必要がありません。覚える必要があるのは、ある要素につき前後の要素だけで十分です。 私はここまでしか解けませんでしたが、何とか速解きでレートは上がりました。Eを解かないことには水色に上がれそうにありません…
ABC455-E
問題文を表示
問題文
A, B, C の 3 種類の文字のみからなる長さ N の文字列 S が与えられます。
非空部分文字列のうち、A, B, C の出現回数が相異なるものの個数を求めてください。
同じ文字列でも取り出す位置が異なれば別の部分文字列として数えます。
制約
- 1 ≤ N ≤ 2 × 10^5
- |S| = N
- N は整数
- S は
A,B,Cのみからなる
入力
N
S
出力
答えを 1 行で出力せよ。
残された80分を使ったにも関わらず、更新ロジックにバグがあり解けませんでした… 解法自体は簡単で、命題の対偶を求めることで解けます。 i番目までの A, B, C の出現回数の差に着目し、出現回数の差が同じパターンのものを数え上げるだけです。 反省として、JavaではPair型を扱おうと思うと非常に冗長なコードを記述する必要があり、実装を複雑化させてしまいました。 また、HashMapも少し冗長なコードになりやすく苦労しました。そのためコンテスト後に複数キーに対応した自前のHashMapをライブラリ化することでAC出来ました。
ABC455-F以降
（これ以降の問題文は割愛）
最後に
以上、ABC455の参加記でした。この記事を読んで競技プログラミングに興味を持った！解法について議論したい！など感じてくだされば幸いです。サークルとしても、お気軽にご連絡お待ちしております。nsubaruでした。