---- *1021 Emacs-like Editor Emacsエディタの簡易版をシミュレートする問題。 解法 テキストエディタって結構設計が大変なのですね。 簡単な問題とみて甘く見てました。 改行だけしかない空行、先頭行、末尾行などの取り扱いが意外と大変な問題でした。 一晩色々なパタンを考えてから提出、ポカミスを2度修正して合格となりました。 入力データの文章の最終行は\nがないようです。 後答えの最終行に\nをつけないと不正解になります。 #include<stdio.h> #include<string> #include<iostream> #define ss std::string //グローバル変数まとめ unsigned int nowP;//カーソルの現在位置、nowP文字目 ss text;//テキスト 効率悪いが実装が楽な方を選ぶ ss buffer;//カットコピーした文字を覚えておく //グローバル変数終わり void a(){ //先頭文字に移動 if(nowP==0)return; while(0<nowP){ nowP--; if(text[nowP]=='\n') break; } if(text[nowP]=='\n')nowP++; } void e(){ //行末へ移動する操作 while(nowP<text.size()){ if(text[nowP]=='\n')break; nowP++; } } void p(){ //上の行の先頭文字へ移動 a(); if(nowP==0) return ; nowP--; if(nowP==0)return; a(); } void n(){ //下に行があればカーソルを下の行の先頭文字に e(); if(nowP<text.size()){ nowP++; }else{ a();//次の行がないので先頭文字へ移動する } } void f(){ //カーソルを一つ右に移動する if(nowP<text.size()){ nowP++; } } void b(){ //カーソルを一つ左に移動する if(nowP>0){ nowP--; } } void d(){ //一文字削除する if(nowP<text.size()){ text.erase(nowP,1); } } void k(){ //バッファに記録する、カーソルが行末を指してない場合末尾の改行はどうなるのだろうか,Bufferに保存する？ if(nowP==text.size())return; if(text[nowP]=='\n'){ d(); buffer="\n"; }else{ int oldP=nowP; e(); buffer=text.substr(oldP,nowP-oldP); text.erase(oldP,nowP-oldP); nowP=oldP; } } void y(){ if(buffer.size()==0)return; text.insert(nowP,buffer); nowP+=buffer.size(); } int main(){ text=""; nowP=0; ss line; while(1){ std::getline(std::cin, line); if(line=="END_OF_TEXT")break; text+=line+"\n"; } text.erase(text.size()-1,1); char com; while(1){ std::cin>>com; switch(com){ case 'a': a(); break; case 'e': e(); break; case 'p': p(); break; case 'n': n(); break; case 'f': f(); break; case 'b': b(); break; case 'd': d(); break; case 'k': k(); break; case 'y': y(); break; } if(com=='-')break; } std::cout<<text<<"\n"; } ---- *1028 ICPC: Ideal Coin Payment and Change http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1028 円コイン6種類で品物を買うとき、支払うコインの枚数と釣銭で受け取るコインの枚数を最小化する問題。 解法 大きな金額のコインから使いできるだけPに近いP近辺の値段を深さ優先探索で求めて解きます。 WAが怖かったのでコインの使用枚数を表すupやdownを広めに取っていますが多分もう少し狭い範囲で計算しても大丈夫でしょう。 コインの枚数制限を忘れないように注意さえすれば簡単な問題です。 #include<stdio.h> const int coins[]={500,100,50,10,5,1}; const int type=6; int ans; int coinCounts[type]; int turisen(int r){ int re=0; for(int i=0;i<type;i++){ re+=r/coins[i]; r%=coins[i]; } return re; } void saiki(int deep,int r,int cc){ //ｒが金額残余。ccがコインカウント if(deep==type&&r<=0){ int t=cc+turisen(-r); ans=(ans>t)?t:ans; return; }else if(deep==type){ return; } if(cc>ans) return; int t=r/coins[deep]; int up =t+5;//大きなコインでできるだけPに近い金額を作ろうとする処理 int down=t-4; up= up<5?5:up; up= up>coinCounts[deep]?coinCounts[deep]:up; down=down>coinCounts[deep]?coinCounts[deep]:down; down=down<0?0:down; for(int i=down;i<=up;i++){ saiki(deep+1,r-i*coins[deep],cc+i);//downからupの枚数のコインを試しに使ってみる } } void setData(int p){ ans=1000000000; for(int i=type-1;i>=0;i--){ scanf("%d",&coinCounts[i]); } saiki(0,p,0); printf("%d\n",ans); } int main(){ int p; while(1){ scanf("%d",&p); if(p==0) break; setData(p); } }
