yukicoder No.653 E869120 and Lucky Numbers
「3月中に毎日1問解いて黄色になろう!」キャンペーン2日目です。因みに問題はyukicoderの最新から★3を貪欲に選んでます。
問題概要
自然数pが与えられるので、これを「各桁が6または7の2つの数字の和」に分解できるか判定しろという問題。
p≦1020000
No.653 E869120 and Lucky Numbers - yukicoder
解説
やるだけ。ほんっとうにやるだけ。
当然ながらこれを数字として認識すると記録すらできないので、文字列として受け取ります。繰り上がりとか面倒なので、下の位から確定していきます。「今までその2つの数字に0となる位があったか(あるならその数字は以降0しか選べない)」「前の桁の繰り上がり分」だけ記録すればひたすら場合分けするだけです。最後まで見た後は繰り上がりが残っている場合を弾き出してYesを出力するだけです。
https://yukicoder.me/submissions/241340
int main() { string p; cin >> p; // 1番下の桁は2,3,4のどれかで無いといけない(0は良い数じゃないから) int under = p[p.size() - 1] - '0'; if (under != 2 && under != 3 && under != 4) { cout << "No" << endl; return 0; } bool usezero[] = { false,false }; int up = 0; rrep(i, p.size()) { int num = p[i] - '0' - up; if (usezero[0] & usezero[1]) { // 0のみOK if (num != 0) { cout << "No" << endl; return 0; } up = 0; } else if (usezero[0]) { // 0,6,7ならOK、upは0に。 up = 0; if (num == 6 || num == 7) continue; else if (num == 0) { usezero[1] = true; } else { cout << "No" << endl; return 0; } } else { // 0,2,4,6,7ならOK。 // 0 if (num == 0) { up = 0; usezero[0] = usezero[1] = true; } // 2(6+6),3(6+7),4(7+7)->up=1に else if (num == 2 || num == 3 || num == 4) { up = 1; } // 6,7(up=0,usezero[0]=trueに) else if (num == 6 || num == 7) { up = 0; usezero[0] = true; } else { cout << "No" << endl; return 0; } } } cout << (up == 0 ? "Yes" : "No") << endl; return 0; }
感想
これは★3なんですか(白目)。多分元々★2で、コンテスト中に昇格したんでしょうね…