読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC011を解いてみた

abc011.contest.atcoder.jp

A問題

 nが12のときだけn=0にしてn++を出力しました。

B問題

 文字列型の配列の形で入力を受け取り、upper()とlower()を利用して1文字目を大文字に、残りの文字を小文字にする処理をしました。

C問題

 全探索以外のアルゴリズムを思い浮かばず、全探索では3^100~3^300程度の計算量となり間違いなく2秒以内に終わらないので諦めました…
 貪欲法の3で引けるときに-1-1-1とする理由はないため引ける数の中でもっとも大きい数を引いて行けばよい(by解説)というアルゴリズムで実装しました。

D問題

 全探索で実装しました。深さ優先探索で探索回数がn回になったタイミングでx, yが目的地に到達していれば変数countを+1して最終的にcountを4^nで割ることで確率を求めました。
 解説読んで99点のメモ化再帰は納得できました。深さ優先探索で実行速度を上げる必要があるときは積極的に使っていきたいです。Dの完答のアルゴリズムはよく理解できてないのでまた勉強します。

雑感

 やっぱり全探索で解けるような問題しか解けないのでメモ化再帰だったり動的計画法をマスターできるよう頑張りたいです。でも、全探索で解ける問題は大体解けるようになってきたかな…?