スクリーンショット_2019-04-04_23

文系ギャルが0から始める競技プログラミング#13

マリー

Intro


この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0

↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#12

・記事への反響


#11で書いた鏡餅について、Twitterでアドバイスいただきました！

setって便利なものがあるらしいです、また一つ天才になってしまいました。

別解等も助かります！ありがとうございました！！！！
Twitterやコメントで引き続きよろしくおねがいします！
（フォローしていただいた諸先輩方を競プロリストに入れてめっちゃみてます。）

・ABC085C　- 初めてのTLE


引き続きAtCoder Beginners Selectionの問題を解いていきます。

問題文
日本でよく使われる紙幣は、
10000円札、5000円札、1000円札です。
以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札がN枚入っていて、合計でY円だったそうですが、嘘かもしれません。
このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。
なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約
1≤N≤2000
1000≤Y≤2×10^7
Nは整数である。
Yは1000の倍数である。

入力
入力は以下の形式で標準入力から与えられる。
N Y

出力
N枚のお札の合計金額がY円となることがありえない場合は、-1 -1 -1 と出力せよ。
N枚のお札の合計金額がY円となることがありうる場合は、そのようなN枚のお札の組み合わせの一例を「10000円札x枚、5000円札y枚、1000円札z枚」として、x、y、zを空白で区切って出力せよ。
複数の可能性が考えられるときは、そのうちどれを出力してもよい。
― ABC085C - Otoshidama

わたしも十分裕福な祖父からでっかいお年玉袋もらいたい！！！！！
しかも入力例、ヤバい金額もらってて羨ましすぎワロタ状態です。

問題文を整理していきます。

iPadとApple Pencilを買ったので、今回からメモが電子化されました！
ペーパーレス！！！

全部でY円になるx,y,zの組み合わせを探せばよさそうなので、
forを使って総当たりしてみることにしました。

実際の提出物がこちら↓

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
   int N,M;
   cin >> N >> M;
   
   int x = 0;
   int y = 0;
   int z = 0;
   
   int X = -1;
   int Y = -1;
   int Z = -1;
   
   for(x=0;x<=N;x++){
       for(y=0;x<=N;y++){
           for(z=0;z<=N;z++){
               if(M == x*10000+y*5000+z*1000 && x+y+z == N){
                   goto out;
               }
           }
       }
   }
out:
   
   X = x;
   Y = y;
   Z = z;
   
   cout << X << " " << Y << " " << Z << endl;


該当する組み合わせがあったら、-1から書き換えればいっか〜と思って書いたら動いたので、提出するとTLE…
人生初TLEいただきました！！！！
ありがとうございます！！！！！！！！

パワープレイすぎて、手数が多すぎるんですね。


師「組み合わせお姉さんの動画みよう」

ということで、もうちょっと手数をへらす方法を考えます。
さっきのメモに…立ち返って…

xとyが決まれば、x+y+z=Nから自動的にzが決まることがわかります。
3重ループでパワープレイしようとしていたのが、2重で十分だということがわかりました。
（Apple Pencil楽しい！！！！！！）

これなら間に合いそうですし、組み合わせお姉さんもロボットにならなくて済みそうです。
（ああ・・・おねえさんに・・・教えてあげたい・・・）

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
   int N,M;
   cin >> N >> M;
   
   int x = 0;
   int y = 0;
   
   int X = 0;
   int Y = 0;
   int Z = 0;
   
   for(x=0;x<=N;x++){
       for(y=0;y<=(N-x);y++){
           if(M == x*10000+y*5000+(N-x-y)*1000){
               goto out;
           }
       }
   }
out:
   if(M == x*10000+y*5000+(N-x-y)*1000){
       
       X = x;
       Y = y;
       Z = (N-x-y);
   }else{
       X = -1;
       Y = -1;
       Z = -1;
   }
   
   cout << X << " " << Y << " " << Z << endl;
   return 0;
}

はい！！！！優勝！！！！
天才ムーブに至るまでに1時間近くかかりましたが優勝できました。
C問題に入ると壁を感じますね。

手数を考えないと、解けないことがわかりました…。
アルゴリズム力………。
というわけで、とりあえず蟻本をKindleで買ったらiPadが欲しくなって買ってしまいましたとさ。

Outro

#14に続く！(不定期連載です。)

これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。

この記事が気に入ったらサポートをしてみませんか？