[yukicoder] No.762 PDCAパス

PDCAパス

https://yukicoder.me/problems/no/762

考え方

題意

長さ \( 3 \) のパスの中で P → D → C → A となるものの本数を数え上げます。

方針

考慮する辺は、PD、DC、CA の三種類だけで良いことが分かります。

まず初めに文字列 S を用いて、P、D、C、A の個数による番号を振ります。例えば、PDDCAA という文字列が与えられたら、各文字の番号を 0, 1, 2, 0, 0, 1 のように番号を付けます。

各文字の総数をそれぞれ、\( N_p, N_d, N_c,  N_A \) とし、新しい頂点の番号をそれぞれ、\( p_i, d_i, c_i, a_i\) とします。

頂点 \( c_i \) から A へのパスの本数は、頂点 \( c_i \) に隣接する A への辺の数になります。この値を \( v(c_i) \) とします。

次に、頂点 \( d_i \) から C → A となるパスの本数は、頂点 \( d_i \) に隣接する 頂点 \( c_j \) から A へのパスの本数の総和となるので、\( v(c_j) \) の値を足せばよいです。

同様にして、頂点 \( p_i \) から D へのパスの本数を数え上げます。最後に各頂点 \( p_i \) の値を足し上げます。

 コード

感想

樹形図のようなものを書くと分かりやすいと思いました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする