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

ferinの競プロ帳

競プロについてのメモ

ABC007を解いてみた

abc007.contest.atcoder.jp

A問題

 入力から1を引いた数を出力しました。特につまずくこともなかったです。

print(int(input())-1)

B問題

 辞書順で前になるものならば何でもいいということだったので入力がaのときだけ-1を出力しそれ以外ならば辞書順で1番前の数であるaを出力しました。ここまでパパっと実装でき、10分くらいで解けました。

C問題

 C++では解いたことのある迷路の幅優先探索だったんですが、配列や内包表現あとは変数の名前被りなんてしょうもない理由で悩んでしまい、この問題で1時間近くかけてしまいました… 幅優先探索くらいであればパパっとかけるように頑張りたいです。

D問題

 10^18を2秒以内に計算できるアルゴリズムは思い浮かばなかったので、部分点狙いで全探索を実装しました。数値を文字列に変換し前から1文字ずつ確かめていき4と9が含まれていればcount++し、countを出力しました。
 解説を読んだだけではいまいち理解できなかったので桁DPで調べたところ以下のサイトで理解できました。
桁DP - CCS Wiki
桁DP入門 - pekempeyのブログ
桁DPのこと - 備忘録的な何か - ぼくの競プロ日記

全体的な雑感

 幅優先探索と桁DPを解けて満足です。毎回i++って書いてエラー食らってるのでいい加減i+=1に慣れたい…