Atomic String
任意の英小文字列 () が与えられます。この文字列からいくつかの小文字を大文字にすることで、元素記号を並べた文字列にできるかを判定し、ないなら"No"、あるならそのような文字列の個数をで割った余りで答えます。
s = "co" が与えられたとき、元素記号での表記が "CO", "Co" の2通りあるので2と答えます。
s = "a" には対応する表記が無いのでNoと答えます。
以下C++での解答:
#include <iostream> #include <vector> #include <set> #define LMAX 100000 using namespace std; const int MOD = 1000000007; int main(){ vector<string> p = {"H", "He", "Li", "Be", "B", "C", "N", "O", "F", "Ne", "Na", "Mg", "Al", "Si", "P", "S", "Cl", "Ar", "K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu", "Zn", "Ga", "Ge", "As", "Se", "Br", "Kr", "Rb", "Sr", "Y", "Zr", "Nb", "Mo", "Tc", "Ru", "Rh", "Pd", "Ag", "Cd", "In", "Sn", "Sb", "Te", "I", "Xe", "Cs", "Ba", "La", "Ce", "Pr", "Nd", "Pm", "Sm", "Eu", "Gd", "Tb", "Dy", "Ho", "Er", "Tm", "Yb", "Lu", "Hf", "Ta", "W", "Re", "Os", "Ir", "Pt", "Au", "Hg", "Tl", "Pb", "Bi", "Po", "At", "Rn", "Fr", "Ra", "Ac", "Th", "Pa", "U", "Np", "Pu", "Am", "Cm", "Bk", "Cf", "Es", "Fm", "Md", "No", "Lr", "Rf", "Db", "Sg", "Bh", "Hs", "Mt", "Ds", "Rg", "Cn", "Nh", "Fl", "Mc", "Lv", "Ts", "Og"}; set<string> atom; for(auto q: p){ q[0] = tolower(q[0]); atom.insert(q); } string s; cin >> s; int l = s.size(); /* if(l>LMAX){ cout << "s is longer than the limit.\n"; return 0; } if(!l){ cout << "s is null.\n"; return 0; } */ vector<long long> dp(l+1, 0); dp[0] = 1; for(int i=0; i<l; i++){ string a; a += s[i]; if(atom.count(a))dp[i+1] += dp[i]; if(!i)continue; a = s[i-1] + a; if(atom.count(a))dp[i+1] += dp[i-1]; dp[i+1] %= MOD; } if(!dp[l])cout << "No" << endl; else cout << dp[l] << endl; return 0; }
元素記号名は高々長さ2なので、「i文字目までが何通りで表せるか」は「i-1文字目~」と「i-2文字目~」を使った漸化式で表せます。上のプログラムではdpにしてるけど変数は3個とっておけばよいです。