今日は
Aizu Online Judgeをやってました。ずっと。
簡単なのが多いですが、10問くらい解きました。
ちなみに私はこういうのを解くプログラミングサークルに入っています。
解いたものをピックアップ
0042:A Thief
よくわからなくて、調べたらナップサック問題というものみたいです。
これを普通に解くと、O(2
n)になり、タイムオーバーするため大変でした。
でも答えのソースはそんなに長くないっていう。orz
解き方はちゃんと覚えておきたい。
► スポイラーを表示
CODE:
#include
#include
#include
using namespace std;
struct Treasure{
Treasure():weight(0),price(0)
{
}
int weight;
int price;
};
int main(){
int W,N;
vector treas;
vector search;
for(int n=1;;n++){
treas.clear();
search.clear();
cin >> W;
if(W==0)break;
cin >> N;
for(int i=0;i0;j--){
Treasure temp;
if(j-treas[i].weight W)continue;
if(temp.price > search[j].price ||
(temp.price == search[j].price && temp.weight
#include
#include
using namespace std;
int main(){
int fuda[10],input[10];
bool ans[10];
string str;
while(cin >>str){
fill(input,input+10,0);
fill(ans,ans+10,false);
for(int i=0;i=3) fuda[j]-=3;
}
//全部消えたか確認
int is_erase=1;
for(int i=1;i=3) fuda[j]-=3;
}
//シークエンスを抜く
for(int j=1;j
#include
using namespace std;
int main(){
int Rcount=0;
string str;
while(cin >>str){
if(equal(str.begin(),str.end(),str.rbegin()))Rcount++;
}
cout をx,y座標として使っているが、使い方としてはいいんだろうか?
[spoil][code=cpp]#include
#include
#include
#include
#include
#include
using namespace std;
class AngleSort{
private:
pair check;
double now_angle;
public:
AngleSort(pair _check,double _now_angle):check(_check),now_angle(_now_angle){}
bool operator()(const pair& A,const pair& B){
double ret[2];
double angle[2];
if(A==check )
ret[0] =2*M_PI;
else{
angle[0] = atan2(A.second-check.second,A.first-check.first);
ret[0] = fmod( angle[0] - now_angle + 2*M_PI , 2*M_PI );
}
if(B==check)
ret[1] =2*M_PI;
else{
angle[1] = atan2(B.second-check.second,B.first-check.first);
ret[1] = fmod( angle[1] - now_angle + 2*M_PI , 2*M_PI );
}
return ret[0] > data;
map, bool> ans;
pair now,next,first;
double now_angle;
map, bool>::iterator m_itr;
while(1){
data.clear();
ans.clear();
cin >> N;
if(N==0)break;
for(int i=0;isecond)Acount++;
}
cout << Acount <<endl;
}
return 0;
}
とりあえずこれで、0000~0068まで0041を除いて全部解きました。
0042,0043,0068が難しかった。時間かかっちゃうね。
ナップサック問題とかよく解らなかったし、アルゴリズムの勉強もしっかりやらないと。