AtCoder に登録したら解くべき精選過去問 10 問を Objective-C で解いてみた

75579 ワード

競技プログラミング AtCoder Objective-C Objective-C テキストリンク

@drken さんの名記事

AtCoder に登録したら次にやること～これだけ解けば十分闘える！過去問精選 10 問～

にある精選10問を，Objective-C で解いてみました。

他の言語の記事はこちらにまとまっています。

百花繚乱！なないろ言語で競技プログラミングをする資料まとめ

制限事項

AtCoder での Objective-C には，前記事に挙げた様々な制約があります。その制約下で頑張ることを目指します。

Objective-C で AtCoder に参加する際の苦労

準備：標準入出力クラス

前記事で述べたように，Objective-C での標準入出力はとても面倒です。C言語標準の scanf や printf を使えばよいのですが，それではもはや「Objective-C で解いた」とは言えなくなってしまいます。そこで，面倒な標準入出力をラップした次のクラスを用意しておきます。

#import <Foundation/Foundation.h>
#import <stdarg.h>

@interface StdIO : NSObject
+(NSString*)stringFromStdIn; // 標準入力から NSString を得る
+(void)printf:(NSString*)format, ...; // 標準出力へ出力
@end

@implementation StdIO
+(NSString*)stringFromStdIn
{
    NSFileHandle *handle = [NSFileHandle fileHandleWithStandardInput];
    NSMutableString *result = [NSMutableString string];
    NSData *data = [handle availableData];
    while ([data length] > 0) {
        [result appendString:[[[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding] autorelease]];
        data = [handle availableData];
    }
    NSUInteger length = [result length];
    if (length >= 1 && [result characterAtIndex:length-1] == '\n') { // 入力末尾に改行文字があれば削除
        [result deleteCharactersInRange:NSMakeRange(length-1,1)];
    }
    return result;
}
+(void)printf:(NSString*)format, ...
{
    va_list arguments;
    va_start(arguments, format);
    NSString *string = [[[NSString alloc] initWithFormat:format arguments:arguments] autorelease];
    NSFileHandle *fileHandle = [NSFileHandle fileHandleWithStandardOutput];
    [fileHandle writeData:[string dataUsingEncoding:NSUTF8StringEncoding]];
    va_end(arguments);
}
@end

以下の解答コードにおいては，このクラスの定義部は省略して示します。

第 1 問: ABC 086 A - Product

与えられた2つの整数 a，b の積の偶奇を判定します。

int main() {
    @autoreleasepool {
        NSString *input = [StdIO stringFromStdIn];
        NSArray *numbers = [input componentsSeparatedByString:@" "];
        NSInteger a = [(NSString*)[numbers objectAtIndex:0] integerValue];
        NSInteger b = [(NSString*)[numbers objectAtIndex:1] integerValue];
        [StdIO printf: (a*b % 2 == 0) ? @"Even" : @"Odd"];
    }
    return 0;
}

ポイント

NSString の -componentsSeparatedByString: で文字列を分割して NSArray の配列を得ます。
AtCoder では Object Subscripting は使えないので NSArray の要素には -objectAtIndex: でアクセスします。
整数値の NSString 文字列に対して -integerValue を送信することで整数値に変換できます。

第 2 問: ABC 081 A - Placing Marbles

与えられた文字列中の 1 の個数を数えます。

int main() {
    @autoreleasepool {
        NSString *input = [StdIO stringFromStdIn];
        NSInteger count = 0;
        for (NSUInteger i=0; i<[input length]; i++) {
            if ([input characterAtIndex:i] == '1') {
                count++;
            }
        }
        [StdIO printf:@"%ld", count];
    }
    return 0;
}

ポイント

NSString の長さは -length で取得します。
i番目の文字は -characterAtIndex: で取得できます。unichar 型の値として返ってきます。

第 3 問: ABC 081 B - Shift Only

与えられた N 個の整数それぞれの「2で割れる回数」の最小値を求めます。

int main() {
    @autoreleasepool {
        NSString *input = [StdIO stringFromStdIn];
        NSArray *numbers = [(NSString*)[[input componentsSeparatedByString:@"\n"]
                                       objectAtIndex:1]
                            componentsSeparatedByString:@" "];
        NSInteger min = NSIntegerMax;
        for (NSString *number in numbers) {
            NSInteger i = [number integerValue];
            NSInteger count = 0;
            while (i%2 == 0) {
                i >>= 1;
                count++;
            }
            min = MIN(min, count);
        }
        [StdIO printf: @"%ld", min];
    }
    return 0;
}

ポイント

入力文字列を改行文字単位で分割した後，最初の行の入力は捨てて，2行目だけを取得し，それをさらに空白文字で分割して数値の列を取得しています。
Objective-C 2.0 の Fast Enumeration（for-in 構文）で走査します。
MIN(a,b) マクロは Foundation.h を #import していれば使えます。

第 4 問: ABC 087 B - Coins

入力された X を 50 で割っておき，$10x+2y+z=X,\ 0\leq x\leq A, 0\leq y\leq B, 0\leq z\leq C$ をみたす $(x,y,z)$ の組の数を数えます。愚直に数えるとこんな感じでしょう。

int main() {
    @autoreleasepool {
        NSArray *numbers = [[StdIO stringFromStdIn] componentsSeparatedByString:@"\n"];
        NSInteger A = [(NSString*)[numbers objectAtIndex:0] integerValue];
        NSInteger B = [(NSString*)[numbers objectAtIndex:1] integerValue];
        NSInteger C = [(NSString*)[numbers objectAtIndex:2] integerValue];
        NSInteger X = [(NSString*)[numbers objectAtIndex:3] integerValue] / 50;
        NSInteger count = 0;
        for (NSInteger x=0; x <= MIN(A,X/10); x++) {
            NSInteger Y = X-10*x;
            for (NSInteger y=0; y <= MIN(B,Y/2); y++) {
                NSInteger z = Y-2*y;
                if (z <= C) {
                    count++;
                }
            }
        }
        [StdIO printf:@"%ld", count];
    }
    return 0;
}

もう少し数学的に考察すると for ループは一重で済みます。まず $x$ を固定しておき，$Y=X-10x$ とおいて，直線 $2y+z=Y$ 上で $0\leq y\leq B, 0\leq z\leq C$ をみたす格子点 $(y,z)$ の数を数えます。$z$ を消去すると，数えるべきは $0\leq y\leq B$ かつ $0\leq Y-2y \leq C$ をみたす $y\in\mathbb{Z}$ の個数となりますので，

\max\left\{0,\left \lceil\frac{Y-C}{2}\right\rceil\right\}\leq y \leq \min\left\{B, \left\lfloor\frac{Y}{2}\right\rfloor\right\}

をみたす $y\in\mathbb{Z}$ の個数，すなわち

\max\left\{ \min\left\{B, \left\lfloor\frac{Y}{2}\right\rfloor\right\} - \max\left\{0,\left \lceil\frac{Y-C}{2}\right\rceil \right\} + 1, 0\right\}

となります。この方針で解くとこんな感じでしょうか。

NSInteger CEIL(double x) {
    NSInteger n = (NSInteger)x;
    return n + (((x != n) && (x > 0)) ? 1 : 0);
}

int main() {
    @autoreleasepool {
        NSArray *numbers = [[StdIO stringFromStdIn] componentsSeparatedByString:@"\n"];
        NSInteger A = [(NSString*)[numbers objectAtIndex:0] integerValue];
        NSInteger B = [(NSString*)[numbers objectAtIndex:1] integerValue];
        NSInteger C = [(NSString*)[numbers objectAtIndex:2] integerValue];
        NSInteger X = [(NSString*)[numbers objectAtIndex:3] integerValue] / 50;
        NSInteger count = 0;
        for (NSInteger x=0; x <= MIN(A,X/10); x++) {
            NSInteger Y = X-10*x;
            count += MAX( MIN(B, Y/2) - MAX(0, CEIL((double)(Y-C)/2)) + 1, 0);
        }
        [StdIO printf:@"%ld", count];
    }
    return 0;
}

ポイント

AtCoder の Objective-C のコンパイルオプションの仕様上 math.h が使えなくなっているようなので，math.h の ceil() は使わずに同様のものを自前で実装しています。

第 5 問: ABC 083 B - Some Sums

@interface NSString (Extension)
-(NSArray*)characters;
@end

@implementation NSString (Extension)
-(NSArray*)characters
{
    NSMutableArray *result = [NSMutableArray array];
    for (NSUInteger i=0; i<[self length]; i++) {
        [result addObject:[NSString stringWithFormat:@"%C", [self characterAtIndex:i]]];
    }
    return result;
}
@end

int main() {
    @autoreleasepool {
        NSArray *numbers = [[StdIO stringFromStdIn] componentsSeparatedByString:@" "];
        NSInteger N = [(NSString*)[numbers objectAtIndex:0] integerValue];
        NSInteger A = [(NSString*)[numbers objectAtIndex:1] integerValue];
        NSInteger B = [(NSString*)[numbers objectAtIndex:2] integerValue];
        NSInteger result = 0;
        for (NSInteger i=1; i<=N; i++) {
            NSArray *digits = [[NSString stringWithFormat:@"%ld", i] characters];
            NSInteger sum = 0;
            for (NSString *digit in digits) {
                sum += [digit integerValue];
            }
            if (A<=sum && sum<=B) {
                result += i;
            }
        }
        [StdIO printf:@"%ld", result];
    }
    return 0;
}

ポイント

「NSString を各文字単位の NSString に分割する」という処理は今後も役立ちそうなので，カテゴリを使って NSString に -characters というメソッドを追加しておくと便利そうです。
NSString の -characterAtIndex: の返値は unichar 型です。
unichar を NSString に変換するには [NSString stringWithFormat:@"%C", hoge] のようにします。%C は unichar に対応するフォーマット指定子です。

第 6 問: ABC 088 B - Card Game for Two

与えられた整数列を降順にソートし，「奇数番目と偶数番目のそれぞれの和」の差をとります。

@interface NSArray (Extension)
-(NSArray*)integerValues;
@end

@implementation NSArray (Extension)
-(NSArray*)integerValues
{
    NSMutableArray *result = [NSMutableArray array];
    for (id obj in self) {
        [result addObject:@([obj integerValue])];
    }
    return result;
}
@end

int main() {
    @autoreleasepool {
        NSSortDescriptor *descriptor = [[[NSSortDescriptor alloc] initWithKey:@"self" ascending:NO] autorelease];
        NSArray *numbers = [[[(NSString*)[[[StdIO stringFromStdIn]
                                componentsSeparatedByString:@"\n"]
                               objectAtIndex:1]
                              componentsSeparatedByString:@" "]
                             integerValues]
                            sortedArrayUsingDescriptors:@[descriptor]];

        NSInteger result = 0;
        BOOL odd = YES;
        for (NSNumber *number in numbers) {
            result += (odd ? 1 : -1) * [number integerValue];
            odd = !odd;
        }
        [StdIO printf:@"%ld", result];
    }
    return 0;
}

ポイント

NSArray の各要素に対して -integerValue をかましたものを NSNumber でボクシングして得られる配列を得る -integerValues というメソッドを，NSArray のカテゴリとして定義しておきました。文字列の配列として得た配列を数値列に変換する機会は多いので役立つでしょう。
AtCoder では Blocks が使えないので，-sortedArrayUsingComparator: は使えません。ソートは -sortedArrayUsingDescriptors: に NSSortDescriptor オブジェクトを与えることで行います。

第 7 問: ABC 085 B - Kagami Mochi

与えられた数値列を一意化することで「値の種類の数」を求めます。


@interface NSArray (Extension)
-(NSArray*)unique;
@end

@implementation NSArray (Extension)
-(NSArray*)unique
{
    return [self valueForKeyPath:@"@distinctUnionOfObjects.self"];
}
@end

int main() {
    @autoreleasepool {
        NSArray *numbers = [[StdIO stringFromStdIn] componentsSeparatedByString:@"\n"];
        numbers = [numbers subarrayWithRange:NSMakeRange(1, [numbers count]-1)]; // 入力のうち最初の行を捨てる
        [StdIO printf:@"%lu", [[numbers unique] count]];
    }
    return 0;
}

ポイント

Key-Value Coding により，NSArray オブジェクトに対して [numbers valueForKeyPath:@"@distinctUnionOfObjects.self"] とすることで，要素の重複を除去した新しい NSAarray オブジェクトが得られます。
毎回 valueForKeyPath:@"@distinctUnionOfObjects.self" と書くのは面倒なので，一意化した配列を返す -unique というインスタンスメソッドを NSArray のカテゴリを定義しておきました。
別解として，[[NSSet setWithArray:numbers] count] として NSSet を経由することで一意な要素数を求める手もあります。
NSUInteger 型に対するフォーマット指定子は %lu です。

第 8 問: ABC 085 C - Otoshidama

$x$ を固定すると，連立方程式

\left\{\begin{array}{l}
y+z=N-x\\
5y+z=\frac{Y}{1000}-10x
\end{array}
\right.

の解は一意に定まりますので，それが $(y,z)$ の定義域の条件に適合するかをチェックします。

int main() {
    @autoreleasepool {
        NSArray *numbers = [[StdIO stringFromStdIn] componentsSeparatedByString:@" "];
        NSInteger N = [(NSString*)[numbers objectAtIndex:0] integerValue];
        NSInteger Y = [(NSString*)[numbers objectAtIndex:1] integerValue] / 1000;

        for (NSInteger x=0; x <= MIN(N,Y/10); x++) {
            NSInteger y = Y-N-9*x;
            NSInteger z = 5*N-Y+5*x;
            if (y>=0 && z>=0 && y%4==0 && z%4==0) {
                [StdIO printf:@"%ld %ld %ld", x, y/4, z/4];
                return 0;
            }
        }
        [StdIO printf:@"-1 -1 -1"];
    }
    return 0;
}

ポイント

本質部はC言語によるロジック部であり，Objective-C ならではの特徴は特にないコードになってしまいました。

第 9 問: ABC 049 C - Daydream

幅優先探索による解法

初めて解いたときは，「後ろから走査すると早い」ということに気づかず，次のように幅優先探索で解きました。

@interface NSMutableArray (Extension)
-(id)shift;
@end

@implementation NSMutableArray (Extension)
-(id)shift
{
    if ([self count] > 0) {
        id first = [self objectAtIndex:0];
        [self removeObjectAtIndex:0];
        return first;
    } else {
        return nil;
    }
}
@end

int main() {
    @autoreleasepool {
        NSString *S = [StdIO stringFromStdIn];
        NSUInteger length = [S length];
        NSArray *words = @[@"dream", @"erase", @"eraser", @"dreamer"];
        NSMutableArray *candidates = [NSMutableArray arrayWithObject:@0]; // 切断に成功している位置の候補を格納するキュー
        NSNumber *candidate;
        while ((candidate = [candidates shift])) { // 先頭候補を取り出し
            NSUInteger currentIndex = [candidate unsignedIntegerValue]; 
            for (NSString *word in words) {
                NSUInteger size = [word length];
                NSUInteger nextIndex = currentIndex + size;
                if (nextIndex <= length) {
                    NSString *prefix = [S substringWithRange:NSMakeRange(currentIndex, size)];
                    if ([prefix isEqualToString:word]) {
                        if (nextIndex == length) { // ちょうど末尾にたどり着いたら終了
                            [StdIO printf:@"YES"];
                            return 0;
                        } else {
                            [candidates addObject:@(nextIndex)];
                        }
                    }
                }
            }
        }
        [StdIO printf:@"NO"];
    }
    return 0;
}

ポイント

NSMutableArray をキューとして使うため，「先頭要素を削除しつつその要素を返す」ための -shift というメソッドをカテゴリで定義しています。
文字列比較は -isEqualToString: で行います。
NSMakeRange(<location>, <length>) で生成した NSRange の値を -substringWithRange: に与えることで部分文字列を取り出します。
NSArray などのコレクションに対してプリミティブ型を直接格納することはできないので，@0 や @(nextIndex) のようにすることで NSNumber オブジェクトへボクシングしています。

後ろから走査する解法

後ろから走査するとキューを使わなくて済むのでより簡単でした。

int main() {
    @autoreleasepool {
        NSString *S = [StdIO stringFromStdIn];
        NSInteger length = [S length];
        NSArray *words = @[@"dream", @"erase", @"eraser", @"dreamer"];
        NSInteger currentIndex = length;
        while (currentIndex > 0) {
            BOOL found = false;
            for (NSString *word in words) {
                NSInteger size = [word length];
                NSInteger nextIndex = currentIndex - size;
                if (nextIndex >= 0) {
                    NSString *suffix = [S substringWithRange:NSMakeRange(nextIndex, size)];
                    if ([suffix isEqualToString:word]) {
                        if (nextIndex == 0) { // ちょうど先頭にたどり着いたら終了
                            [StdIO printf:@"YES"];
                            return 0;
                        } else {
                            found = YES;
                            currentIndex = nextIndex;
                            break;
                        }
                    }
                }
            }
            if (!found) {
                [StdIO printf:@"NO"];
                return 0;
            }
        }
    }
    return 0;
}

第 10 問: ABC 086 C - Traveling

旅行プランの各行程における時空上の点 $(t,x,y)$ を表すクラスを用意し，$(t_1,x_1,y_1)$ から $(t_2,x_2,y_2)$ へ遷移可能かどうかを判定するメソッドを定義します。$\Delta t = t_2-t_1$，$\Delta x = |x_2-x_1| + |y_2-y_1|$ とおくと，$\Delta t\geq \Delta x$ ならばとりあえず目的地に直行し，余り時間 $\Delta t - \Delta x$ をそのあたりでウロウロして過ごせば OK です。余り時間が偶数ならば余り時間をキリよく消化できます。

@interface TripPoint : NSObject
{
    NSInteger _t;
    NSInteger _x;
    NSInteger _y;
}
@property NSInteger t;
@property NSInteger x;
@property NSInteger y;
-(instancetype)initWithT:(NSInteger)t x:(NSInteger)x y:(NSInteger)y;
-(instancetype)initWithLine:(NSString*)line;
-(NSInteger)distanceFrom:(TripPoint*)point;
-(NSInteger)timeFrom:(TripPoint*)point;
-(BOOL)isReachableFrom:(TripPoint*)point;
@end

@implementation TripPoint
@synthesize t = _t;
@synthesize x = _x;
@synthesize y = _y;
-(instancetype)initWithT:(NSInteger)t x:(NSInteger)x y:(NSInteger)y
{
    if (self = [super init]) {
        self.t = t;
        self.x = x;
        self.y = y;
    }
    return self;
}
-(instancetype)initWithLine:(NSString*)line;
{
    if (self = [super init]) {
        NSArray *numbers = [line componentsSeparatedByString:@" "];
        self.t = [(NSString*)[numbers objectAtIndex:0] integerValue];
        self.x = [(NSString*)[numbers objectAtIndex:1] integerValue];
        self.y = [(NSString*)[numbers objectAtIndex:2] integerValue];
    }
    return self;
}
-(NSInteger)distanceFrom:(TripPoint*)point
{
    return ABS(self.x - point.x) + ABS(self.y - point.y);
}
-(NSInteger)timeFrom:(TripPoint*)point
{
    return self.t - point.t;
}
-(BOOL)isReachableFrom:(TripPoint*)point
{
    NSInteger time = [self timeFrom:point];
    NSInteger distance = [self distanceFrom:point];
    return (time >= distance) && ((time-distance)%2 == 0);
}
@end

int main() {
    @autoreleasepool {
        NSArray *lines = [[StdIO stringFromStdIn] componentsSeparatedByString:@"\n"];
        NSInteger N = [(NSString*)[lines objectAtIndex:0] integerValue];
        TripPoint *currentPoint = [[[TripPoint alloc] initWithT:0 x:0 y:0] autorelease];
        for (NSInteger i=1; i<=N; i++) {
            NSString *line = [lines objectAtIndex:i];
            TripPoint *nextPoint = [[[TripPoint alloc] initWithLine:line] autorelease];
            if ([nextPoint isReachableFrom:currentPoint]) {
                currentPoint = nextPoint;
            } else {
                [StdIO printf:@"No"];
                return 0;
            }
        }
        [StdIO printf:@"Yes"];
    }
    return 0;
}

ポイント

クラスにおけるプロパティ定義は可能です。ただし，AtCoder の Objective-C では，アンダースコア付きインスタンス変数を @interface 側に明示定義し，かつ @implementation 側で明示的に @synthesize することが必要です。
ABS(x) マクロは Foundation.h を #import していれば使えます。

Author And Source

この問題について(AtCoder に登録したら解くべき精選過去問 10 問を Objective-C で解いてみた), 我々は、より多くの情報をここで見つけました https://qiita.com/doraTeX/items/4a347691dec400c41183

著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。

Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .

C++ifstreamストリームでTXTファイルを読むと文字化けします

Java各種ファイル形式の内容を読み込む