G4NP0Nのブログ

競プロとそれ以外のことについてしゃべります。

【久しぶりの全完】ABC185 参加記&解法メモ

AtCoder Biginner Contest 185 全完しました!

やったぜ。

f:id:G4NP0N_kyopro:20201213221220p:plain

 

A - ABC Preparation

1回のコンテストを開くのに100~400点の各問題が1問ずつ必要なので、入力のうち最も小さい数字を出力すればよいです。配列で受け取って最小値を返す関数を使うのが楽だと思います。

B - Smartphone Addiction

家を出る時をB0、家に帰る時をAM+1として、(現在の容量)-(Ai+1-Bi)>0 のチェックと(現在の容量)=max(N,(現在の容量+(Ai+1-Bi))を繰り返せばいいです。

これがBに置かれるの、令和を感じますね……

C - Duodecim Ferra

なんか最初箱とボールと勘違いしました……

鉄の棒の欠片がL個あると考えると、L-1個の欠片のすき間のうち11個を選ぶ通り数、すなわちL-1C11

オーバーフローしそうだな~と思ってL=200を試すと明らかにオーバーフローしていたので、BigIntegerで殴ると通りました。

D - Stamp

ハンコの使用回数を最小にしたいので、ハンコの幅kをなるべく大きくしたいです。

kの上限は白が連続する区間の最長の長さなので、(それを超えると青に重ならずハンコを押すのが不可能になります)白が連続する部分の長さを数えてNに対して切り上げ除算すればいいです。これはAi+1-Ai-1の最小となります。端っこは別途計算しておきました。0除算とかM=0の場合とかいろいろコーナーもあるので気を付けました。

F - Range Xor Query

Dを解き終わった時点で順位表を見ると茶緑の人達が無限人Fを通していたので、先にFを見ました。問題開きながら「タイトル的にセグ木とかかな~」とか思ってました。そしたら親戚のおじさんの顔より見た貼るだけセグ木だったので、貼ったら通りました。

E - Sequense Matching

これ最初全然わかんね~っつってたんですが、A'i!=B'iであるときにコスト1で両者を取り除く、みたいに考えると、DP[i][j]:=AiとBjまで見たときの最小コスト、みたいに管理できそう、と思いつきました。

こんな感じの漸化式に帰着できます。

f:id:G4NP0N_kyopro:20201213223734p:plain

 

このDPなんか名前付いてないのかな~とか思ったけどよく考えたらLCSとやってることほとんど変わらないですね。それぞれi,j文字目まで見たときの状況を2次元テーブルの要素として管理する、みたいな。

 

感想

50分ノーペナ全完、かなりいい出来だと思ったんだけど黄パフォ取れないんですね。壁が高いぜ……。