AtCoder Beginner Contest211に参加しました。
結果
A,B,C,D問題の4問正解でパフォーマンスが920でした。 時間ギリギリだったけど久々にD問題まで解けた。結構うれしい。
A - Blood Pressure
問題文の通りに計算を行う。割り算をするときに小数点以下を切り捨てられないように注意すればOK。
B - Cycle Hit
問題文の通り各文字列が何回出てきているかを数える。mapとかの連想配列的なデータ構造を使えば簡単に処理できる。
もしくは力技で、4つの内から2つを選んで文字列が同じかどうかの判定を6通り行う。
C - chokudai
似た問題を解いたことがあったので助かった。C問題にしては難しいような気もするけど、典型的なDPの問題だからC問題でもいいのかなあ。（典型90問の008問で解いてたみたい。）
動的計画法を使って解く種類の問題。DP[Sの先頭からi文字目までチェックした][chokudaiの先頭からj文字目まで選択した]として、
Sの先頭からi番目まで見たときにchokudaiのj文字目の文字列まで選択する場合の通り数を数える。
こうした場合、DP[i][j]はDP[i-1][j]+DP[i-1][j-1]となる。
基本的な考え方は
- i番目の通り数はi-1番目の通り数をもとに計算できる。
- i-1番目がchokudaiのj文字目と一致しないならDP[i][j]＝DP[i-1][j]となる。（i-1番目までj文字目の選び方が5通りなら次のi番目まで見ても5通りのまま。）
- i-1番目がchokudaiのj文字目と一致するならDP[i][j+1]はDP[i-1][j+1]+DP[i-1][j]となる。（i番目まででj文字目を選ぶ通り数は、i-1番目でj-1文字目に一致した場合+i-1文字目でj文字目に不一致だった場合となる。）
D - Number of Shortest paths
はじめはDPっぽい問題かなと思いつつ、最終的には幅優先探索を改造して解いた。
問題文を読むと、都市Nまでの通り数は、都市Nに隣接している都市X1,都市X2,・・・への通り数の和になりそうなので、メモ化再帰で都市1に遡りつつ計算して解くか、都市1から都市Nに向かって順番に隣接する都市への通り数を数えていくかで解けそうな気がした。
はじめはメモ化再帰でコードを書いていたけど幅優先探索の方が楽そうな気がしたので途中で方針を変更。
幅優先探索しつつ、その都市への行き方は何通りあるのかを数えていった。
バグ取りしてたら時間がギリギリになったけどちゃんと解けた。
