A - Div

N個のお菓子を一列に並べて、どこかに仕切りを入れて左側をAくんが貰う、右側をBくんが貰う、という図を思い浮かべます。

N=4のとき、以下の図のようになります。

今回の問題では「両者とも1個以上得る」という制約があるので「|oooo」や「oooo|」といった位置に仕切りが来ることはありません。

N個並んでいるときに、仕切りを入れる位置として考えられるのはN-1箇所なので、答えはN-1になります。

(もし、問題の制約で「0個以上もらう」と書いている場合は、両端を含めるので答えはN+1になります)

(ここから先、話がそれます)

「N人でM個の物を分けます。(ただしMはN以上。N,Mは1以上の整数。)全員が1つ以上貰えるようにして下さい。分け方は何通りありますか？」

という問題が出たとします。

2人→N人になった場合の解き方についてです。

N人いるとき、仕切りをN-1個置くことになり、他の条件は上と変わりません。

仕切りを置く場所の候補はM-1箇所で、その中にN-1個の仕切りを置くので、(M-1)C(N-1)が答えとなります。

この問題で、「全員が1つ以上貰う」→「0個貰う人がいても良い」となったときは少し複雑になってくるので、今回は省略します。

(一応書いておくと(M+N-1)! / (M! * (N-1)!)という式で出せます。)

B - Palindrome with leading zeros

言語によって実装が異なるので、C++前提で書きます。

まず、回文判定をするということは入力される数値の数学的性質を使わなさそうなので、文字列として受け取ることにします。

0を好きなだけ足して良い、ということは「足す行為はせずに、好きなだけ末尾から0を取り除いてよい」という解釈もできます。

なので、この問題を2つのステップに分けて考えます。

1. 末尾の0を全て取る

2. 残った文字列が回文かどうか判定する

まずは1.についてです

string s;
cin >> s;
while(s[s.size()-1]=='0'){
  s.pop_back();
}

(このあたり、C++の文字列の扱いについて丁寧にまとめられたページがあったので、そこを参考にしながら書いています。)

文字列の長さを得るのは s.length() でも s.size() でもできるみたいなので、どちらかを使います。

例えば、s="HelloWorld" だと s.length() は 10 を返します。

文字列には、s[i]でi番目の文字にアクセスできます。

例えば、s="HelloWorld" において s[7] は r となります。

(先頭は0から始まるので、0番目がH、1番目がe、...、9番目がdという風に1つずつずれることには注意です。)

末尾の削除の仕方は複数ありますが、上のリンクに書いてあったpop_back() を使って書いてみました。

他にも substr(X,Y) を使った書き方もあります。

substr は、X番目からY文字だけ抜き取って返すので、例えば s="HelloWorld" に対して s.substr(2,5) をすると "lloWo" となります。

(substr の引数が1つの場合もあるので、詳しくは上のリンクを参照して下さい)

今回は、末尾以外の全ての文字が欲しいので、substr 的に言うと「sの先頭から、長さが(sの長さ-1)の文字列が欲しい」ということになります。

string s;
cin >> s;
while(s[s.size()-1]=='0'){
  s = s.substr(0,s.size()-1);
}

ここまでで1. が終了したので、次は2. です。

例えば、s="noteton"のときに回文かどうか判定するのは、先頭と末尾、(先頭+1)文字目と(末尾-1)文字目、(先頭+2)文字目と(末尾-2)文字目、...、末尾と先頭、のそれぞれのペアが全て同じかチェックすることで実装できます。

(計算量を半分にする処理は書く気力があるときに追記します)

先頭と末尾はそれぞれ s[0],s[s.size()-1] でアクセスできるので、そこからひとつずつずらして判定していきます。

string s = "level";
for(int i=0;i<s.size();i++){
    if(s[i] != s[s.size()-1-i]){
        cout << "No" << endl;
        return 0;
    }
}
cout << "Yes" << endl;

そろそろ1時を過ぎて眠くなってきたので以上です。

今回説明した流れにそってコードを書くと以下のようになり、無事にACできました。

A問題

B問題