sankantsuのブログ

技術メモ・競プロなど

ABC252 感想・反省

atcoder.jp

結果

atcoder.jp

ABCDEF6完 (72:26+4ペナ) ペナルティ多いのは少しもったいないが,6完は初なので嬉しい.

青パフォも初.

コード (C++)

github.com

各問題の振り返り

A

与えられたASCIIコードに対応する文字を出力する問題

文字コードとか知らないと厳しいかもしれないが,知っていれば実装は一瞬で終わる. 迷わず書くことができた.

1分消費

B

一方の配列の最大値を与えるインデックスがもう一方の配列に含まれるかどうか判定する問題

配列に含まれるかどうか検査するのにsetを使ったが,あまり計算量気にする必要もないので線形探索したほうが素直かもしれない.

添字ずれで1WA. 実装に少し手間取ったり,しょうもないWA出したりするので,低難度ももう少し練習したほうがいいのだろうか...

7分消費

C

スロットを揃えるためにかかる最短秒数を求める問題

秒数が同じタイミングで出る文字が被る場合,文字を揃えるためには一方を押してからもう一方を押すために一周待つ必要がある. ある文字について,タイミングごとに出現回数を数えておけば,最も多くその文字の出現が被っているタイミングで揃えるまでにかかる秒数が決まる. それぞれの文字について揃えるまでにかかる秒数を調べ,もっとも短いものを出力すれば良い.

12分消費

D

異なる数字を3つ選ぶ選び方の数を求める問題

文字の出現回数を数えればそこから計算できそうな気がしたが,すぐにはわからずいったんEに移動.

数え方をよく考えてみると,数字の出現にかぶりがなければ  {}_n C_3 通り. 同じ数字が2回以上出現する場合は,この数字を複数回選ぶような選び方を除外すればいい. ある数字がk回出現するとき,除外するパターンの数は  (n-k){}_k C_2 + {}_k C_3 である.

intのオーバーフローで2WA

24分ぐらい (D+Eで39分)

E

ある頂点からほかの頂点までの距離が短くなるように辺を残して木をつくる問題

ダイクストラで頂点1から他の頂点への最短経路を求め,各最短経路に必要な辺だけを残せば閉路はできていないはずなので,木になるはず. したがって,通常のダイクストラで最短距離を求めながら,使った辺を保存していくことで解ける.

intのオーバーフローで1WA

15分ぐらい

F

パンを切るためのコストが切る前の長さで決まっていて,つくりたいパンの長さが決まっているときに切り出すのにかかる最小コストを求める問題

見てすぐ既視感があり,蟻本にのっている下の問題とほぼ同じとわかる.

3253 -- Fence Repair

最終的にパンを切り終わった状態からはじめ,かけらが小さいほうから切り出すためのコストを確定させていく貪欲法的なアルゴリズムで解ける.

蟻本は偉大

12分ぐらい

G

与えられたDFSの行きがけ順を達成する木構造のパターン数を求める問題

与えられた行きがけ順の前から見ていって,最後のノードをどの深さに足すかでdpとかするのかなとか考えてみるがコンテスト中には解けず.

後日解いて解説を書いた.

sankantsu.hatenablog.com