※彼の祖父は十分裕福であり、お年玉袋は十分に大きいものとする【ABC085C - Otoshidama】

AtCoderの問題文は独特なユニークさがあって好きです。

ABC085C - Otoshidama

やること

お札の枚数N,合計金額Y(Yは最大7桁)を受け取る
10000x+5000y+1000z=Y かつ　x+y+z=Nとなる組み合わせを1つでもいいので見つける
組み合わせが見つかったらx,y,zの値を出力する
見つからなかった時-1,-1,-1を出力する

普通に多重ループで解決できそうです。
zの値については、z=N-x-yで求められるのでzのループは省略できそう。
ただしz>=0ということを明示しないとダメ（コードテストでひっかかったところ）

解答　素直に書く

    #include <bits/stdc++.h>
    using namespace std;
     
    int main(){
      int N,Yen;
      cin >> N>>Yen;
      int x=0,y=0,z=0;
      int smalYen=Yen/1000;
      bool Ansflag=false;
      
      for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
          int kariZ=0;
          if(N-i-j>=0){
            kariZ=N-i-j;
          }
          if((10*i)+(5*j)+kariZ==smalYen && i+j+kariZ==N){
            Ansflag=true;
            x=i,y=j,z=kariZ;
          }      
        }
      }
      if(Ansflag){
      cout <<x <<" "<<y <<" "<<z <<endl;
      }else{
        cout << -1<<" "<< -1<<" "<< -1<<endl;
      }
     
    }

Y(en)は制約で1000の倍数であることが保証されているので、いつでも1000で割ることができます。
10000x+5000y+1000(N-x-y>=0)=smalY×1000となるので全ての項を1000で割って
10x+5y+(N-x-y>=0)=smalYを判定式として使えます。この式の条件を満たし、かつ
x+y+(N-x-y>=0)=Nという判定式を満たす時に組み合わせが存在することになります。

組み合わせを見つけたらi,j,N-i-jをそれぞれx,y,zに代入して、bool型のAnsflagをtrueにすることで、
Ansflagがtrueならx,y,zを表示、falseならば-1,-1,-1を表示させる分岐を作ります。

つまづき(コードテストで変なことになった)ポイントは
for文の条件式i<=Nをいつもの手癖でi

O(1)で解く方法があるらしい

x,y,zが全て0以上の正の整数であることなどを用いて連立方程式をこねくりまわすと導出できるらしい。
自力で導出できるように、いくつかの解説を読みながら自分で説明することで体系的な理解を試みる。

$10x×10^3+5y×10^3+z×10^3=Y(n×10^3)$
これをまず変形させて
$10x+5y+z=Y'$
ここまではできる。ここから、zを移項させた上で左辺の共通因数5をくくりだす
$5(2x+y)=Y'-z\tag{1}$
これが新しく導き出せる判定式、Y'-zは5の倍数であることが条件の1つになる。
また、合同式の性質の1つに
$a \equiv b(mod m) \iff a-b \equiv 0 (mod m)$
つまりY'を5で割った余りとzを5で割った余りは等しい、ということになる。

またzが取りうる値の範囲について
$0 \leq z \leq min(N,Y')\tag{2}$
zは最大でもNとY'のどちらか小さい方までの値しかとることはない。
$Y'-z=5(2x+y)$
$N-z=x+y$
であり、かつxとyは正の整数なので
$x+y \leq 2x+y \leq 2(x+y) \tag{3}$
左辺値での不等式なので、これに右辺値(Y'-z),(N-z)を代入すると
$N-z \leq \dfrac{(Y'-z)}{5} \leq 2(N-z) \tag{3'}$

(1)(2)(3')で用いる変数がzのみとなり（N,Y'は入力時に決定する定数）
この3つの式の条件に合うzが見つかる時に、xとyの値が一意に決まる（かつ、x,yも条件を満たしている）
ただ(3')が扱いにくいので、単純なzで不等式ができるように改変する必要がある。
数学苦手マンなのでかなり混乱したが、
まずはN-z≦(Y'-z)/5から1つずつ整理していくと
$5N-5z \leq Y'-z$ 両辺に5を掛けて分母を払い、右辺のY’を消すために両辺に-Y’して
$5N-Y'-5z \leq -z$ 左辺から-5zを消すために両辺に+5zを足す
$5N-Y' \leq 4z$ 最後に、zの係数を払うために両辺を4で割ることで
$\frac{5N-Y'}{4} \leq z$ シンプルな不等式に整理できる。
これをY'-z/5≦2(N-z)についても同様に行う。*1
$\dfrac{5N-Y'}{4} \leq z \leq \dfrac{10N-Y'}{9} \tag{4}$

このへんで計算量でパソコンが爆発するより先に私の頭が爆発した。

(追記) 一応形はできたがfor文に無駄を感じる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
  ll N,Y;
  cin >>N>>Y;
  ll Ydash=Y/1000;//Y'
  
  ll min_N_Yd=min(N,Ydash);//最大値の最低ラインを決定

  ll modz=Ydash%5;//Ydash%5とz%5(両者を5で割った余り)は等しい  
  ll sahen=(5*N-Ydash)/4;//判定3の最低ライン
  ll uhen=(10*N-Ydash)/9;//判定3の最大ライン
  bool ans=false;
  
  for(int z=modz;z<=min_N_Yd;z+=5){
      bool flag1=(0<=z&&z<=min_N_Yd);//判定式1
      bool flag2=(z%5==modz);//判定式2
      bool flag3=(sahen<=z&&z<=uhen);//判定式3
      if(flag1 && flag2 && flag3){
        int x=0;
        int y=0;
        int siki=((Ydash-z)/5)-(N-z);
        if(siki>=0){
          x=siki;
        }
        y=N-z-x;
        cout << x << " "<< y << " "<< z <<endl;
        ans=true;
        return 0;
      }
     }
     if(ans==false){
       cout << -1 <<" "<<-1<<" "<<-1<<endl;
     }
}

一応ACを取れる。二重ループの実行時間が14msだったところ、こちらは6msとかなり早い。
for文をmod式の余りから始めて+5ずつ増やしているが、for文自体が無駄のような気がする。
どう消せばいいかまではちょっと考えられない(すでに頭が爆発しているため)
判定式3の範囲の最大値が0ならばzは0だし、判定式3の最低値以上かつmod5がY'と等しい値から始まるならばそれがzにすればいい。
(判定式3<=0)のときz=0,0<=判定式3のとき、判定式3の範囲の任意のY'≡z mod5を1つ選ぶ、という処理で
xとyは求められる、はず
stlに範囲と条件を渡せば返してくれる関数はあるとおもう
今日はもうむり

*1: (Y'-z/)5≦2N-2z →　Y’-z≦10N-10z →-z≦10N-10z-Y' →9z≦10N-Y' →z≦(10N-Y')/9

ABC085C - Otoshidama

解答 素直に書く

O(1)で解く方法があるらしい

解答　素直に書く