UAPC 2011(会津大学プログラミングコンテスト) 参加記 - ひよっこプログラマのプログラミング

UAPC 2011

結果

A,B,Kの3問Acceptで、最終順位は46位でした。自分が思ったほどひどい結果にはなりませんでしたが、もう少し上位に入りたかったです。
解答と解説はAcceptした問題だけ書いています。

Rank

Time

463

25/0

265/2

0/4

131/0

解説とソースコード

問題A : It's our delight!!

問題文(AOJ:1062)

レストランの伝票に関する問題です。
発行された伝票の時間からどの時間帯(昼・夕・夜・その他)か判断し、各時間帯ごとに商品を出すまでの時間が8分以下の伝票の割合を調べます。割合は小数点以下切り捨てで出力します。int型同士の除算は小数点以下が切り捨てられるのでdouble型を使う必要はないです。
伝票の発行が8:52で商品提供が03分(9:03)のように時間をまたぐ入力や伝票の時間が午前1時などの入力に気をつけましょう。問題文をきちんと読んで落ち着いて解けば易しい問題です。

ソースコード

#include <iostream>
#include <cstdio>
using namespace std;

int f(int m,int m_){
    if( m > m_ ) m_ += 60;
    return (m_-m);
}

int main(){
    int n,h,m,m_,L,L_,D,D_,M,M_;
	
    while( scanf("%d",&n) , n ){
        L=L_=D=D_=M=M_=0;
        for(int i=0 ; i<n ; i++ ){
            scanf("%d%*c%d%d",&h, &m, &m_);

            if( h <= 1 ) h += 24;
			
            if( h >= 11 && h <= 14 ){
                L++;
                if( f(m,m_) <= 8 ){
                    L_++;
                }
            }else if( h >= 18 && h <= 20 ){
                D++;
                if( f(m,m_) <= 8 ){
                    D_++;
                }
            }else if( h >= 21 && h <= 25 ){
                M++;
                if( f(m,m_) <= 8 ){
                    M_++;
                }
            }	
        }
        if( L == 0 ){
            printf("lunch no guest\n");
        }else{
            printf("lunch %d\n",L_*100/L);
        }
        if( D == 0 ){
            printf("dinner no guest\n");
        }else{
            printf("dinner %d\n",D_*100/D);
        }
        if( M == 0 ){
            printf("midnight no guest\n");
        }else{
            printf("midnight %d\n",M_*100/M);
        }
    }
}

問題B : Watchin' TVA

問題文(AOJ:1063)

できる限りアニメをたくさん見るようにしたときに最大でいくつのアニメが見られるか調べる問題です。
典型的な区間スケジューリング問題です。区間スケジューリング問題は蟻本(プログラミングコンテストチャレンジブック)にも載っていて、コンテストではよく出る問題なので確実に解けるようにすべき問題です。
区間スケジューリング問題では、選ぶことが可能なもののなかで終了時間の最も早いものを選ぶ操作を繰り返すというものです。

まず問題Bでは曜日・時間・分で与えられてやりづらいので、これらを日曜日の0:00からの経過分に変換しましょう。
問題では月曜日25:30は、火曜日1:30としなければならないので、時間が24時をこえる入力には気をつける必要があります。

お気に入りのアニメは必ず見なければならないので、お気に入りのアニメの終了時間をソートし、放映時間が衝突していないか調べましょう。ひとつでも衝突していたら-1を出力します。

衝突していなかったら、まだ見ることが確定していないアニメのうち、一番終了時間の早いものを選ぶアニメがなくなるまで繰り返し選びます。選ぶ時はすでに見ることが確定しているアニメと放映時間が衝突していないか調べましょう。そして選んだアニメは見ることが確定したアニメとして追加しておきましょう。

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int toTime(int start, int& w){
    int m = start%100;
    int h = start/100;
    if( h >= 24 ){
        h -= 24;
        w++;
    }
    return ( m + h*60 + w*60*24 ) ;
}

int main(){
    int n,p,w,start;
    string name;
	
    while( cin >> n , n ){
        map<string,int> f;
        vector<int> favTime, Time;
        int ans = 0;
        bool flag = true;

        for(int i=0 ; i<n ; i++ ){
            cin >> name >> w >> start;
            int t = toTime( start , w ) + 30;
            f[name] = t;
            Time.push_back( t );
        }
		
        cin >> p;
        for(int i=0 ; i<p ; i++ ){
            cin >> name;
            favTime.push_back( f[name] );
        }

        sort( favTime.begin() , favTime.end() );
        for(int i=1 ; i < (int)favTime.size() ; i++ ){
            if( favTime[i] - favTime[i-1] < 30 ){
                flag = false;
            }
        }

        sort( Time.begin() , Time.end() );
        for(int i=0 ; i < (int)Time.size() ; i++ ){
            bool flag_ = true;
            for(int k=0 ; k < (int)favTime.size() ; k++ ){
                if( max(favTime[k],Time[i]) - min(favTime[k],Time[i]) < 30 ){
                     flag_ = false;
                }
            }
            if( flag_ ){
                ans++;
                favTime.push_back( Time[i] );
            }
        }
        cout << ((flag)? (ans+p) : -1 ) << endl;
    }
}

問題K : Rearranging Seats

問題文(AOJ:1072)

r*c個の席があり、隣接する前後左右の4つの席のどれかに全員が席を替えられることがで可能か調べる問題です。
実はこの問題は、今回のコンテストで一番簡単な問題です。
結論をいうと整数値r,cがともに奇数のときに"no"を出力し、そうでないときには"yes"を出力します。

例えばr=1,c=1のときは、席がひとつしかないので"no"になります。
r=1,c=2のときは1に座っている人と2に座っている人が入れ替わればよいので"yes"です。
r=1,c=3のときは1に座っている人は2にしか移ることができません。3の人も2にしか移ることができません。
とこのようにいくつかの具体例を考えるとr,cがともに奇数のときに必ず前後左右の席に移ることができない人が出てしまい、それ以外のときは、席の個数(r*c個)は偶数なので、隣接する同士で二人組をつくり場所を交換すれば席替えを行うことができます。

ソースコード

#include <iostream>
using namespace std;
int main(){
    int r,c;
    while( cin >> r >> c , r||c ){
        cout << ( ( r%2 && c%2 )? "no" : "yes" ) << endl;
    }
}

途中経過

13:00

コンテスト開始。

13:25頃

問題AをAccept。

13:25-15:00頃

問題Bに取り掛かる。デバッグに苦戦し、時間がかかった上に途中Bをジャッジできないトラブルが発生。

15:00-15:11

問題Bが提出できないので、正答率が高い問題Kに手をつけAccept。

15:11-16:30

とりあえずCからLまで問題全部に軽く目を通し適当にコードを書いてみるがうまくいかない。

16:30-17:25

問題Bが提出できるようになっているのに気付いたのでB問題を提出。2回TLEを出してしまったが修正してAccept。

17:25-18:00

TLEしていた問題Hをいろいろ修正してみるが、なかなかいい方法が思いつかずコンテスト終了。

感想

結果はおそらく実力通りで良くもなく悪くもない感じでした。
当日は体調が悪く大変でしたが、その割には頑張れたかと思います。
難しめの問題が多いように感じましたが、解けそうな問題はあったはずなのでどの問題から手をつけるか判断する能力と素早く正確に実装する力が不足していたように感じました。

おまけ

UAPC 2011の臨場感(?)を味わえるTogetterまとめをつくったのでどうぞ。
UAPC 2011 まとめらしきもの