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

今まで競技プログラミングというものをやったことがなかったのですが，物は試しと今週 [AtCoder](https://atcoder.jp) の [ABC126](https://atcoder.jp/contests/abc126) に初参加してみました。（残念ながらジャッジトラブルで Unrated となってしまいましたが……）
言語としては，macOS アプリ開発で手に馴染んでいる Objective-C を選択しました。

## 今さら Objective-C? 今時なら Swift じゃないの？

その通りなんですが，AtCoder のサーバに搭載されている Swift は Swift 2.2 という化石のような古いバージョンです。現在の最新版である Swift 5.0 とでは，文法や標準ライブラリのAPIが大きく異なります。今さら Swift 2.2 時代の古い文法・ライブラリでコードを打ち込んでそれを体に覚えさせるのはいかがなものかと思いました。Objective-C も言語仕様の進化はありますが，基本的に上位互換な進化をしているので，旧時代の記法は現在でも有効です。

## 競技プログラミングなら C++ 一択でしょ？

それもその通りなんですが，個人的に C++ は馴染みが薄く，C言語系のオブジェクト指向言語としては Objective-C の方が手に馴染んでいます。それに，「C++ で競技プログラミングを始めてみました」では当たり前すぎて何の情報価値もなく，記事になりませんし……。

というわけで，今回は「**Objective-C で AtCoder でどこまで頑張れるか**」に挑戦してみました。

# コード例

* [AtCoder に登録したら解くべき精選過去問 10 問を Objective-C で解いてみた](https://qiita.com/doraTeX/items/4a347691dec400c41183)

# AtCoder の Objective-C でできることとできないこと

AtCoder の[ルールページの説明](https://atcoder.jp/contests/abc126/rules)によると，Objective-C のコンパイラとしては Clang 3.8.0 が次のオプションで動いています。

```
clang -O2 ./Main.m -o ./a.out -lobjc -lgnustep-base -I/usr/lib/gcc/x86_64-linux-gnu/4.8/include/ -I/usr/include/GNUstep -fconstant-string-class=NSConstantString
```

Xcode で Objective-C による通常の macOS アプリ開発をしているときと比べて，いろいろと制限があります。Objective-C の機能や標準ライブラリのうち，何が使えて何が使えないかを調べてみました。（印象としては，MacOS X 10.5 Leopard 時代の文法・ライブラリで時が止まっている感じでした。）

## `Foundation.h` → 使える

`#import <Foundation/Foundation.h>` が使えるので，`NSArray` や `NSDictionary` など Core Foundation の基本的なクラスが一通り使えます。

## `math.h` → 使えない？

AtCoder の Objective-C コンパイラでは，C言語標準ライブラリの `math.h` がなぜか使えない設定になっているようです。コンパイラオプションに `-lm` が付いていないからでしょうか。例えば，今回の [ABC126](https://atcoder.jp/contests/abc126) の[C問題](https://atcoder.jp/contests/abc126/tasks/abc126_c)において提出しようとした次のコードは，コンパイラとして `Objective-C (Clang 3.8.0)` を選択するとリンカーがエラーを起こしてしまいました。同じコードを `C (Clang 3.8.0)` に投げると通ります。

```objc
#include <stdio.h>
#include <math.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int main() {
    int N, K;
    scanf("%d %d", &N, &K);
    double result = MAX((1.0+N-K)/N, 0);
    for (int i=1; i<=MIN(K-1, N); i++) {
        double n = ceil(log2((double)K/i));
        result += 1.0/N * pow(0.5,n);
    }
    printf("%.12lf", result);
    return 0;
}
```

```:エラー
/usr/bin/ld: /tmp/Main-928ed0.o: undefined reference to symbol 'ceil@@GLIBC_2.2.5'
//lib/x86_64-linux-gnu/libm.so.6: error adding symbols: DSO missing from command line
clang-3.8: error: linker command failed with exit code 1 (use -v to see invocation)
```

# 標準入出力 → `NSFileHandle`

Objective-C はC言語の上位互換なので，C言語の `scanf` や `printf` といった標準入出力関数はそのまま使えます。しかし，それでは Objective-C で書いたことにあまりならない気がします。そこであえて Objective-C らしく `NSFileHandle` でやるとこんな感じでしょうか。

### C言語版

```c
int a, b;
scanf("%d %d", &a, &b);
printf("%d", a+b);
```

### Objective-C版

```objc
// 標準入力から文字列を取得
NSFileHandle *inputHandle = [NSFileHandle fileHandleWithStandardInput];
NSData *data = [inputHandle availableData];
NSMutableString *inputString = [NSMutableString string];
while ([data length] > 0) {
    [inputString appendString:[[NSString alloc] initWithData:data encoding:NSUTF8StringEncoding]];
    data = [inputHandle availableData];
}

// 取得した文字列をスペースで分割してそれぞれを整数に変換
NSArray *components = [inputString componentsSeparatedByString:@" "];
NSInteger a = [(NSString*)[components objectAtIndex:0] integerValue];
NSInteger b = [(NSString*)[components objectAtIndex:1] integerValue];

// 出力文字列を整形
NSString *outputString = [NSString stringWithFormat:@"%ld", a+b];

// 標準出力に出力
NSFileHandle *outputHandle = [NSFileHandle fileHandleWithStandardOutput];
[outputHandle writeData:[outputString dataUsingEncoding:NSUTF8StringEncoding]];
```

あ，圧倒的な長さッ……！(ﾟдﾟ) Objective-C らしさにこだわると，競技プログラミング的には不利になること間違いなさそうです。


## ARC (Automatic Reference Counting) → 無効

ARC は有効になっていません。オブジェクトのメモリ管理は自分でやる必要があります。`retain` や `release` など自分で管理するか，`@autoreleasepool { ... }` 内で `autorelease` によって `NSAutoReleasePool` に登録せねばなりません。

## Fast Enumeration （for-in 構文） → 使える

```objc
NSArray *array;
...
for (id obj in array) {
    ...
}
```

のような Fast Enumeration （for-in 構文）は使えます。

## Dot Notation → 使える

`[str UTF8String]` を `str.UTF8String` のように書ける Dot Notation は使えます。

## `new` → 使える

`NSObject` を継承したクラスにおいて，`[[MyClass alloc] init]` を `[MyClass new]` と短く書けるのは有効です。

## `instancetype` → 使える

プロトコルにおいて，それを実装する具体的なクラス名を特定せずにメソッドの返値の型を記述するときに便利な `instancetype` は使えます。

```objc
@protocol ConvenienceConstructor
+(instancetype)defaultObject;
@end

@interface MyClass : NSObject <ConvenienceConstructor>
@end
  
@implementation MyClass
+(instancetype)defaultObject
{
  return [[[MyClass alloc] init] autorelease];
}
@end 
```

## Object Literal → 使える

`@(...)` → `NSNumber`，`@[...]` → `NSArray`，`@{...}` → `NSDictionary` といったオブジェクトリテラルは使えます。

```objc
NSArray *array = @[@0, @1, @(3+4), @42LL];
NSDictionary *dictionary = @{@"key1": @10, @"key2": @(2.5+3.2)};
```

ただし，`@YES`，`@NO` によるBOOL値からの `NSNumber` 生成のリテラル記法は使えませんでした。`[NSNumber numberWithBool: YES]` のようにしてボクシングする必要があります。

## Object Subscripting → 使えない

`NSArray` や `NSDictionary` のコレクションに対して添字で要素にアクセスする Object Subscripting は使えませんでした。

### Modern Objective-C

```objc
NSArray *array;
NSDictionary *dictionary;
...
id element = array[0];
id value = dictionary[@"key"];
```

### AtCoder Objective-C

```objc
NSArray *array;
NSDictionary *dictionary;
...
id element = [array objectAtIndex:0];
id value = [dictionary valueForKey:@"key"];
```

コレクションに対して添字でアクセスできないと，コーディングがかなり面倒になりますね……。例えば，次のようなケースでそれが顕著です。

### Swift 版
```swift
var array = [1,2,3]
array[0] += 1
```


### Modern Objective-C 版

```objc
NSMutableArray<NSNumber*> *array = [NSMutableArray arrayWithObjects:@1, @2, @3, nil];
array[0] = @(array[0].integerValue + 1);
```

### AtCoder Objective-C 版
```objc
NSMutableArray *array = [NSMutableArray arrayWithObjects:@1, @2, @3, nil];
[array replaceObjectAtIndex:0 withObject:@([(NSNumber*)[array objectAtIndex:0] integerValue] + 1)];
```

タイプ数多い……(ﾟдﾟ)  可読性悪い……(´･ω･`)

## Lightweight Generics → 使えない

Object Subscripting が使えない以上，それよりずっと後の時代に登場したシンタックスである Lightweight Generics は，当然ながら使えませんでした。コレクションから要素を取り出すときは，プログラマの責任下で型をダウンキャストする必要があります。

### Modern Objective-C

```objc
NSArray<NSNumber*> *array = @[@1, @2, @3];
NSInteger i = array[0].integerValue;
```

### AtCoder Objective-C
```objc
NSArray *array = @[@1, @2, @3];
NSInteger i = ((NSNumber*)[array objectAtIndex:0]).integerValue;
```

## `NSRegularExpression` → 使えない， `NSRegularExpressionSearch` → 検索のみ使える

MacOS X 10.6 Snow Leopard の API から登場した `NSRegularExpression` クラスは使えませんでした。ただし，文字列検索時のオプション `NSRegularExpressionSearch` は使えるので，**正規表現にマッチする最初の部分文字列を得る**ことは一応可能です。

```objc
NSString *str = @"abc123def45678gh";
// 正規表現による文字列検索
NSRange digitRange = [str rangeOfString:@"\\d+" options:NSRegularExpressionSearch];
NSLog(@"%@", [str substringWithRange:digitRange]); // => "123"
```

しかし，正規表現による文字列置換はできないようでした。

```objc
NSString *str = @"abc123def45678gh";
// 正規表現による文字列置換
NSString *newStr = [str stringByReplacingOccurrencesOfString:@"\\d+"
                                                  withString:@"XXX"
                                                     options:NSRegularExpressionSearch
                                                       range:NSMakeRange(0, [str length])];
NSLog(@"%@", newStr);
```

この実行結果は，Xcode では `abcXXXdefXXXgh` となりましたが，AtCoder では元のまま `abc123def45678gh` となってしまいました。

## プロパティ → 制限付きで使える

クラス定義におけるプロパティは一応使えました。ただし制限があります。

### 別名プロパティを明示定義 → 使える

`@proprety`, `@synthesize` を用いる次のコードは，AtCoder で無事に通りました。

```objc
#import <Foundation/Foundation.h>

@interface MyClass : NSObject
{
    NSInteger _value;
}
@property NSInteger value;
-(NSString*)description;
@end

@implementation MyClass
@synthesize value = _value;
-(NSString*)description
{
    return [NSString stringWithFormat:@"value = %ld\n", self.value];
}
@end

int main() {
    @autoreleasepool {
        MyClass *obj = [[[MyClass alloc] init] autorelease];
        obj.value = 42;
        NSLog(@"%@", [obj description]); // => "value = 42"
    }
    return 0;
}
```

### アンダースコア付き `@synthesize` の対象の省略 → 不可

上記の例において，アンダースコア付きインスタンス変数に対応づける

```objc
@synthesize value = _value;
```

は，Xcode の Modern Objective-C では

```objc
@synthesize value;
```

と省略できます。ですが AtCoder ではこれは不可でした（インスタンス変数名と同一ならば可）。

### `@synthesize` 自体の省略 → 不可

Xcode の Modern Objective-C では，アンダースコア付きのものに対応させる `@synthesize` はそもそもそれ自体を省略できますが，AtCoder では不可でした。

### アンダースコア付きインスタンス変数の定義自体の省略 → 不可

Xcode の Modern Objective-C では，アンダースコア付きのものに対応させる場合は，`@property` のみ書いておけば `@synthesize` のみならずインスタンス変数の定義自体を次のように省略できますが，この記法も AtCoder では不可でした。

```objc
@interface MyClass : NSObject
@property NSInteger value;
@end

@implementation MyClass
@end
```

## `@implementation` 側でのインスタンス変数定義 → 不可

Xcode の Modern Objective-C では，外部に露出させる必要がないインスタンス変数は `@implementation` の側に書くことで隠蔽できますが，AtCoder では不可でした。

## Class Extension → 定義はできるがインスタンス変数の定義不可

自作クラスに対して，追加で

```objc
@interface MyClass ()
{
    NSInteger _value;
}
@property NSInteger value;
-(void)myMethod;
@end
```

のように，`()` 付きで `@interface` 宣言するのが Class Extension です。主に，外部から隠蔽したいインスタンス変数・プロパティ・メソッドを宣言するのに使われます。AtCoder では，Class Extension は定義できましたが，追加のインスタンス変数を宣言するのは不可でした。

## Blocks → 使えない

Blocks とはいわゆるクロージャです。ソート条件を直接記述したり，配列に対する map や filter といった処理に不可欠です。たとえば `(x,y)` の組の列を「第1条件として `x` の昇順でソート」「`x` が同じなら第2条件として `y` の昇順でソート」という処理は，Xcode の Modern Objective-C なら次のように書けます。

```objc
NSArray<NSArray<NSNumber*>*> *array = @[@[@8,@5], @[@5,@4], @[@5,@1], @[@5,@5], @[@5,@1]];

NSArray<NSArray<NSNumber*>*> *sortedArray = [array sortedArrayUsingComparator:^NSComparisonResult(NSArray<NSNumber*> *p, NSArray<NSNumber*> *q) {
  NSInteger a = p[0].integerValue;
  NSInteger b = p[1].integerValue;
  NSInteger c = q[0].integerValue;
  NSInteger d = q[1].integerValue;
  if (a < c) {
      return NSOrderedAscending;
  } else if (a > c) {
      return NSOrderedDescending;
  } else {
      if (b < d) {
          return NSOrderedAscending;
      } else if (b > d) {
          return NSOrderedDescending;
      } else {
          return NSOrderedSame;
      }
  }
}];

NSLog(@"%@", [sortedArray description]); // => ((5,1),(5,1),(5,4),(5,5),(8,5))
```

ですが AtCoder の Objective-C では Blocks が使えない設定になっているようです。Blocks が使えないと，コレクションの処理で毎回ループを回さなければならないなど，かなり不便となります。

```:エラー
./Main.m:7:58: error: blocks support disabled - compile with -fblocks or pick a deployment target that supports them
```

このエラーメッセージを見ると，コンパイルオプションに `-fblocks` を付ければ済む話のように見えます。そうであれば，付けて頂きたいものです……。

## Key-Value Coding → 使える

コレクションに対する集計や抽出に便利な Key-Value Coding は使えます。

```objc
NSArray *array = @[@1, @2, @3, @1, @2];

NSLog(@"%ld", [[array valueForKeyPath:@"@min.self"] integerValue]); // 最小値 => 1
NSLog(@"%ld", [[array valueForKeyPath:@"@max.self"] integerValue]); // 最大値 => 3
NSLog(@"%ld", [[array valueForKeyPath:@"@sum.self"] integerValue]); // 合計値 => 9
NSLog(@"%lf", [[array valueForKeyPath:@"@avg.self"] doubleValue]); //  平均値 => 1.800000
NSLog(@"%@", [[array valueForKeyPath:@"@distinctUnionOfObjects.self"] description]); // 重複除去 => (3, 1, 2)

NSArray *persons = @[@{@"name": @"Hoge", @"age": @20},
                     @{@"name": @"Fuga", @"age": @30},
                     @{@"name": @"Piyo", @"age": @45},
                     @{@"name": @"Foo", @"age": @30},
                     @{@"name": @"Bar", @"age": @18}];

NSLog(@"%@", [[persons valueForKeyPath:@"@unionOfObjects.name"] description]); // キー name の値を抽出 => (Hoge, Fuga, Piyo, Foo, Bar)
NSLog(@"%@", [[persons valueForKeyPath:@"@unionOfObjects.age"] description]); // キー age の値を抽出 => (20, 30, 45, 30, 18)
NSLog(@"%@", [[persons valueForKeyPath:@"@distinctUnionOfObjects.age"] description]); // キー age の値を重複除去して抽出 => (18, 45, 30, 20)

```

## `NSSortDescriptor` によるソート → 使える

Blocks が使えないので，`sortedArrayUsingComparator:` による `NSArray` のソートが使えません。代替法として，単純なケースであれば `NSSortDescriptor` が使えます。

### `NSNumber` オブジェクトを要素に持つ単純な数の配列のソート

```objc
NSArray *array = @[@1, @2, @3, @1, @2, @6, @5];
NSSortDescriptor *descriptor = [[NSSortDescriptor alloc] initWithKey:@"self" ascending:YES];
NSArray *sortedArray = [array sortedArrayUsingDescriptors: @[descriptor]]; // => (1,1,2,2,3,5,6)
```

### `NSDictionary` オブジェクトを要素に持つ配列のソート

```objc
NSArray *persons = @[@{@"name": @"Hoge", @"age": @20},
                     @{@"name": @"Fuga", @"age": @30},
                     @{@"name": @"Piyo", @"age": @45},
                     @{@"name": @"Foo", @"age": @30},
                     @{@"name": @"Bar", @"age": @18}];
NSSortDescriptor *descriptor = [[NSSortDescriptor alloc] initWithKey:@"age" ascending:YES];
NSArray *sortedArray = [persons sortedArrayUsingDescriptors: @[descriptor]];
// キー age の値でソート => ({age = 18; name = Bar; }, {age = 20; name = Hoge; }, {age = 30; name = Fuga; }, {age = 30; name = Foo; }, {age = 45; name = Piyo; })

```

より複雑なソート条件を記述したい場合は，`NSArray` の `-sortedArrayUsingFunction:context:` に関数ポインタを渡す必要があるでしょう。

## `NSPredicate` による抽出 → 使える

Blocks は使えませんが，簡単な抽出条件であれば，`NSPredicate` オブジェクトで条件を記述して抽出する `-filteredArrayUsingPredicate:` が使えます。

```objc
NSArray *array = @[@[@8,@-5], @[@-1,@4], @[@5,@1], @[@3,@1], @[@-5,@-1]];

NSPredicate *predicate = [NSPredicate predicateWithFormat: @"SELF[0] > 0 && SELF[1] > 0"];
NSArray *filteredArray = [array filteredArrayUsingPredicate:predicate];

NSLog(@"%@", [filteredArray description]);
// 第1成分と第2成分の両方が正の要素を抽出 => ((5,1),(3,1))

NSArray *persons = @[@{@"name": @"Hoge", @"age": @20},
                     @{@"name": @"Fuga", @"age": @30},
                     @{@"name": @"Piyo", @"age": @45},
                     @{@"name": @"Foo", @"age": @30},
                     @{@"name": @"Bar", @"age": @18}];
NSPredicate *predicate2 = [NSPredicate predicateWithFormat: @"age >= 25"];
NSArray *filteredPersons = [persons filteredArrayUsingPredicate:predicate2];

NSLog(@"%@", [filteredPersons description]);
// 25歳以上を抽出 =>  ({age = 30; name = Fuga; }, {age = 45; name = Piyo; }, {age = 30; name = Foo; })
```

# 実行速度はどうか？

競技プログラミングをする上で重要な関心事となる実行速度についてはどうでしょうか。Objective-C はC言語の上位互換なので，C言語部分についての実行速度はC言語と同じです。一方，C言語レイヤーの上にかぶさる Objective-C ならではのオブジェクトシステムは動的型付けで，メソッド呼び出しは動的なメッセージ送信によります。そのため，オブジェクトに対するメソッド呼び出しの部分はどうしても速度上ネックになります。巨大なサイズの `NSArray` の要素にアクセスしまくるようなことをすると，効率がかなり悪く，速度が目に見えて低下します。

AtCoder の過去問を解くのに `NSArray` を使ってみたところ，要素数が 10<sup>5</sup> くらいになってくると，`NSSortDescriptor` によるソートは遅すぎて `TLE` を頻発させる結果となりました。`NSArray` に対するクイックソートの処理を自前で書いたところ，速度は少し向上し，`TLE` を回避して `AC` される問題が増えました。それでも `TLE` になる場合は `NSArray` で処理するのを諦め，伝統的なC言語の配列で書き直してC言語標準の `qsort` で処理するよう置き換えるとうまくいきました。（それならはじめからC言語の配列を使っておけばよいわけですが……）

# 結論：Objective-C on AtCoder は茨の道！

Objective-C で AtCoder に挑戦するのは，

* Objective-C コンパイラが Modern Objective-C の文法にあまり対応していない（または有効化するオプションが切られている）。
* そのため，ただでさえ多くなりがちな Objective-C の記述量が，さらに長く冗長になる。
* 標準ライブラリが古く，新しめの API やクラスが使えない。
* `math.h` が使えない（？）
* Objective-C のオブジェクトに対するアクセスが遅い。

といった様々な障害があり，快適な環境とは言えません。やはり，競技プログラミングでオブジェクト指向なC言語が欲しいなら，素直に C++ で書くのがよさそう，という当たり前の結論に至ってしまいました。