C# と VB.NET の質問掲示板

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト

Re[7]: 会津大学のプログラムの問題が解けない

(過去ログ 95 を表示中)

[トピック内 8 記事 (1 - 8 表示)]　 << 0 >>

■56358 / inTopicNo.1)

　会津大学のプログラムの問題が解けない

▼■

□投稿者/ ｓ (1回)-(2011/01/11(Tue) 20:10:36)

分類:[C/C++]　

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0033&lang=jp

リンク先の問題なのですが、うまく解けず悩んでいます。

ボールが追加されるたびに右の筒と左の筒のTopの玉の数字を比べて、球の数字が大きいほうに追加できるかためし、だめなら反対の筒をためし、両方だめなら追加不可能。

というロジックで挑戦してみたのですが、判定はエラーとなりました。
何か考えミスがあったのか、どなたかアドバイスお願いします。
コードは下記のとおりです。

#include <iostream>
void search(void);

int main(void)
{
int n;
std::cin>>n;
for(int i=0;i<n;i++){
search();
}
}

void search(void){
int r=0;//右の筒のトップ
int l=0;//左の筒のトップ
bool comp=true;//きちんと球が入った場合Trueのまま
bool inOK;//球を一つ入れることができたらTrue

int num;//次のボールのNO

for(int i=0;i<10;i++){
std::cin>>num;
inOK=false;

if(r<l){
//左のほうが数が大きいのでボールを左に入れることを試す
if(l<num){
inOK=true;
l=num;
}else if(r<num){
inOK=true;
r=num;
}
}else{
//右のほうが大きいのでボールを先に右に入れることを試す
if(r<num){
inOK=true;
r=num;
}else if(l<num){
inOK=true;
l=num;
}
}

if(inOK==false){
//左右に入らない場合
comp=false;
break;
}
}

if(comp==true){
std::cout<<"YES\n";
}else{
std::cout<<"NO\n";
}
}

引用返信 編集キー/

■56360 / inTopicNo.2)

　Re[1]: 会津大学のプログラムの問題が解けない

▲▼■

□投稿者/ επιστημη (2593回)-(2011/01/11(Tue) 21:27:17)

> ボールが追加されるたびに右の筒と左の筒のTopの玉の数字を比べて、球の数字が大きいほうに追加できるかためし、だめなら反対の筒をためし、両方だめなら追加不可能。

どっちにも追加できるときは?

> 何か考えミスがあったのか、どなたかアドバイスお願いします。

コードにミスはありませんか? 検証しましたか?

# 右/左に振り分けるのは高々2^N通りなので目の子で勘定してもそんなに遅くなさげ。

引用返信 編集キー/

■56365 / inTopicNo.3)

　Re[2]: 会津大学のプログラムの問題が解けない

▲▼■

□投稿者/ s (1回)-(2011/01/11(Tue) 23:20:19)

>どっちにも追加できるときは?
そのときは両方の筒を比べて、値の大きなほうの筒から入れれないか調べます。

右の筒のトップが6で左の筒のトップが5　新しいボールが9だとしますと。
右に入れたら
9,5　A
左に入れたら
6,9　B

右と左を入れ替えて考えると
5,9と6,9で比べるなら5,9のほうが明らかにいいです。
大きなほうの筒に入れます。

Aの場合のほうが、より多くの球を受け入れ可能だと思うので、筒の一番上を比べて大きな値の入ってる筒に詰めていく。
基本的な考え方に間違いはないと考えてはいるのですが。

引用返信 編集キー/

■56368 / inTopicNo.4)

　Re[3]: 会津大学のプログラムの問題が解けない

▲▼■

□投稿者/ shu (353回)-(2011/01/12(Wed) 07:45:41)

■No56365 (s さん) に返信

B,Cの推移も表示して確認してみてはどうでしょう？

引用返信 編集キー/

■56388 / inTopicNo.5)

　Re[4]: 会津大学のプログラムの問題が解けない

▲▼■

□投稿者/ s (2回)-(2011/01/12(Wed) 14:35:10)

結局全経路探索に戻してみたら解けました。
ほぼ最速なコードを目指してみたかったのですがちょっと残念です。

一応後日再挑戦も考えてますのでこうすれば高速化できるよというアドバイスがあればよろしくお願いします。

次の問題を考えてたりしてます。
問0506　Stringの書きかけです。
これも高速化のアドバイスあれば募集します。

#include <iostream>
#include <vector>
using namespace std;
char* process(char *);

int main(void)
{
char *t;
int n;
std::cin>>n>>t;

for(i=0;i<n;i++){
t=process(t);
}

}

char * process(char *c){
int n=strlen(c);
char t,oldt;
int count=0;
vector<char> ans;
t=c[n-1];

for(int i=n-1;i>=0;i--){
oldt=t;
t=c[i];
if(oldt==t){
count++;
}else{
//逆順に入れていく
ans.push_back(oldt);
while(count!=0){
ans.push_back((char)(count%10+'0'));
count=count/10;
}
count=0;//念のため
}
}

//逆順に取り出す
n=ans.size();
char *ans2=new char[n];
for(int i=n-1;i>=0;i--){
ans2[n-1-i]=ans[i];
}
return ans2;
}

引用返信 編集キー/

■56390 / inTopicNo.6)

　Re[5]: 会津大学のプログラムの問題が解けない

▲▼■

□投稿者/ SS (1回)-(2011/01/12(Wed) 15:29:51)

ちょっと考えてみましが if 文いっぱいで美しくないですね・・・
C++ っぽさもない・・・

とりあえずサンプルの結果にはなります。
読み込み部分は固定で与えちゃってます。


bool search(const vector<int>& list)                                                             
{                                                                                                
    int r = 0, l = 0;                                                                            
    int* first = NULL, *second = NULL;                                                           
                                                                                                 
    for (auto it = list.begin(); it != list.end(); ++it)                                         
    {                                                                                            
        if (r + 1 == *it) r = *it;                                                               
        else if (l + 1 == * it) l = *it;                                                         
        else                                                                                     
        {                                                                                        
            if (r > l)                                                                           
            {                                                                                    
                first = &r;                                                                      
                second = &l;                                                                     
            }                                                                                    
            else                                                                                 
            {                                                                                    
                first = &l;                                                                      
                second = &r;                                                                     
            }                                                                                    
                                                                                                 
            if (*first < *it) *first = *it;                                                      
            else if (*second < *it) *second = *it;                                               
            else return false;                                                                   
        }                                                                                        
    }                                                                                            
    return true;                                                                                 
}

int main(int argc, char** argv)                                                                  
{                                                                                                
    vector<int> list1 = { 3, 1, 4, 2, 5, 6, 7, 8, 9, 10 };                                       
    vector<int> list2 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };                                       
    cout << (search(list1) ? "OK" : "NG") << endl;                                               
    cout << (search(list2) ? "OK" : "NG") << endl;                                               
}

引用返信 編集キー/

■56395 / inTopicNo.7)

　Re[6]: 会津大学のプログラムの問題が解けない

▲▼■

□投稿者/ ｓ (3回)-(2011/01/12(Wed) 20:05:53)

データは標準入力、標準出力で与えられてますので、少しコードを変更してから試してみます。

備考
サイトに登録し問題ページの下段にある”提出する”をクリックして、コードの投稿ページを表示できます。
投稿すればテストデータによるプログラムのテストが可能ですので気に入った方はどうぞ。

＞話題２
別の問題
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0506&lang=jp
を計算するコードを書いて提出したところRuntime Errorとなってしまいました。
ローカルではきちんと動くのですがサーバではだめなようです。
どなたかアドバイスお願いします。

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;
void process();
char *ans2;

int main(void)
{
int n;
ans2=new char[100];
std::cin>>n;
std::cin>>ans2;

while(n!=0){
for(int i=0;i<n;i++){
process();
}
std::cout<<ans2<<"\n";

std::cin>>n;
if(n!=0){
delete[] ans2;
ans2=new char[100];
std::cin>>ans2;
}
}
return 0;
}

void process()
{

int n=strlen(ans2);
char t,oldt;
int count=0;
vector<char> ans;
t=ans2[n-1];

for(int i=n-1;i>=0;i--)
{
oldt=t;
t=ans2[i];
if(oldt==t)
{
count++;
}else
{
//逆順に入れていく

ans.push_back(oldt);
while(count!=0)
{
ans.push_back((char)(count%10)+'0');
count=count/10;
}
count=1;
}
}
ans.push_back(t);
while(count!=0)
{
ans.push_back((char)(count%10)+'0');
count=count/10;
}

n=ans.size();
delete[] ans2;
ans2=new char[n+1];
//逆順に取り出す
for(int i=0;i<n;i++){
ans2[i]=ans[n-i-1];
}
ans2[n]='\0';
}

引用返信 編集キー/

■56656 / inTopicNo.8)

　Re[7]: 会津大学のプログラムの問題が解けない

▲▼■

□投稿者/ MAG (1回)-(2011/01/25(Tue) 09:02:31)

　Cですが、考えてみました。
高速化云々はわかりません。
　
#include <stdio.h>

void ball(void)
{
	int a, b = 0, c = 0, i;
	
	fputs("Balls < ", stdout);
	for(i = 0; i < 10; ++ i){
		scanf("%d", &a);
		if(a > b) b = a;
		else if(a > c) c = a;
		else break;
	}
	if(i < 10) puts("NO");
	else puts("YES");
}

void string(void)
{
	char s[2][128];
	int i, j, k, l, m, n, p;
	
	fputs("n < ", stdout);
	scanf("%d", &n);
	fputs("String < ", stdout);
	scanf("%s", s[0]);
	for(i = m = 0; i < n; ++ i, m = !m){
		l = p = 0;
		/*puts(s[m]);*/
		for(j = k = 0; ; ++ k){
			if(s[m][j] == s[m][k]) ++ l;
			else{
				p += sprintf(&s[!m][p], "%d%c", l, s[m][j]);
				l = 1;
				j = k;
			}
			if(!s[m][k]) break;
		}
	}
	puts(s[m]);
}

int main(void)
{
	ball();
	while(getchar() != '\n') ;
	string();
	return 0;
}

引用返信 編集キー/

トピック内ページ移動 / << 0 >>

このトピックに書きこむ

過去ログには書き込み不可

- Child Tree -