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

@drken さんの名記事

* [AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067)

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

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

* [百花繚乱！なないろ言語で競技プログラミングをする資料まとめ](https://qiita.com/drken/items/6edb1c0542d4c3b7179c)

# 制限事項

AtCoder での Objective-C には，[前記事](https://qiita.com/doraTeX/items/b5f094f68f7a7007f806)に挙げた様々な制約があります。その制約下で頑張ることを目指します。

* [Objective-C で AtCoder に参加する際の苦労](https://qiita.com/doraTeX/items/b5f094f68f7a7007f806)

# 準備：標準入出力クラス

[前記事](https://qiita.com/doraTeX/items/b5f094f68f7a7007f806)で[述べた](https://qiita.com/doraTeX/items/b5f094f68f7a7007f806#%E6%A8%99%E6%BA%96%E5%85%A5%E5%87%BA%E5%8A%9B--nsfilehandle)ように，Objective-C での標準入出力はとても面倒です。C言語標準の `scanf` や `printf` を使えばよいのですが，それではもはや「Objective-C で解いた」とは言えなくなってしまいます。そこで，面倒な標準入出力をラップした次のクラスを用意しておきます。

```objc
#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](https://atcoder.jp/contests/abc086/tasks/abc086_a)

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

```objc
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](https://atcoder.jp/contests/abc081/tasks/abc081_a) 

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

```objc
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](https://atcoder.jp/contests/abc081/tasks/abc081_b)

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

```objc
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](https://atcoder.jp/contests/abc087/tasks/abc087_b)

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

```objc
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}$ の個数となりますので，

```math
\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}$ の個数，すなわち

```math
\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\}
```

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

```objc
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](https://atcoder.jp/contests/abc083/tasks/abc083_b) 

```objc
@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](https://atcoder.jp/contests/abc088/tasks/abc088_b)

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

```objc
@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](https://atcoder.jp/contests/abc085/tasks/abc085_b)

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

```objc

@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](https://atcoder.jp/contests/abc085/tasks/abc085_c)

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

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

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

```objc
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](https://atcoder.jp/contests/abc049/tasks/arc065_a)

## 幅優先探索による解法

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

```objc
@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` オブジェクトへボクシングしています。

## 後ろから走査する解法

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

```objc
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](https://atcoder.jp/contests/abc086/tasks/arc089_a)

旅行プランの各行程における時空上の点 $(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 です。余り時間が偶数ならば余り時間をキリよく消化できます。

```objc
@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` していれば使えます。