Objective-C で AtCoder に参加する際の苦労
今まで競技プログラミングというものをやったことがなかったのですが，物は試しと今週 AtCoder の 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 の Objective-C でできることとできないこと
AtCoder のルールページの説明によると，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 のC問題において提出しようとした次のコードは，コンパイラとして Objective-C (Clang 3.8.0) を選択するとリンカーがエラーを起こしてしまいました。同じコードを C (Clang 3.8.0) に投げると通ります。
#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言語版
int a, b;
scanf("%d %d", &a, &b);
printf("%d", a+b);
Objective-C版
// 標準入力から文字列を取得
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 構文） → 使える
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 は使えます。
@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 といったオブジェクトリテラルは使えます。
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
NSArray *array;
NSDictionary *dictionary;
...
id element = array[0];
id value = dictionary[@"key"];
AtCoder Objective-C
NSArray *array;
NSDictionary *dictionary;
...
id element = [array objectAtIndex:0];
id value = [dictionary valueForKey:@"key"];
コレクションに対して添字でアクセスできないと，コーディングがかなり面倒になりますね……。例えば，次のようなケースでそれが顕著です。
Swift 版
var array = [1,2,3]
array[0] += 1
Modern Objective-C 版
NSMutableArray<NSNumber*> *array = [NSMutableArray arrayWithObjects:@1, @2, @3, nil];
array[0] = @(array[0].integerValue + 1);
AtCoder Objective-C 版
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
NSArray<NSNumber*> *array = @[@1, @2, @3];
NSInteger i = array[0].integerValue;
AtCoder Objective-C
NSArray *array = @[@1, @2, @3];
NSInteger i = ((NSNumber*)[array objectAtIndex:0]).integerValue;
NSRegularExpression → 使えない， NSRegularExpressionSearch → 検索のみ使える
MacOS X 10.6 Snow Leopard の API から登場した NSRegularExpression クラスは使えませんでした。ただし，文字列検索時のオプション NSRegularExpressionSearch は使えるので，正規表現にマッチする最初の部分文字列を得ることは一応可能です。
NSString *str = @"abc123def45678gh";
// 正規表現による文字列検索
NSRange digitRange = [str rangeOfString:@"\\d+" options:NSRegularExpressionSearch];
NSLog(@"%@", [str substringWithRange:digitRange]); // => "123"
しかし，正規表現による文字列置換はできないようでした。
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 で無事に通りました。
#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 の対象の省略 → 不可
上記の例において，アンダースコア付きインスタンス変数に対応づける
@synthesize value = _value;
は，Xcode の Modern Objective-C では
@synthesize value;
と省略できます。ですが AtCoder ではこれは不可でした（インスタンス変数名と同一ならば可）。
@synthesize 自体の省略 → 不可
Xcode の Modern Objective-C では，アンダースコア付きのものに対応させる @synthesize はそもそもそれ自体を省略できますが，AtCoder では不可でした。
アンダースコア付きインスタンス変数の定義自体の省略 → 不可
Xcode の Modern Objective-C では，アンダースコア付きのものに対応させる場合は，@property のみ書いておけば @synthesize のみならずインスタンス変数の定義自体を次のように省略できますが，この記法も AtCoder では不可でした。
@interface MyClass : NSObject
@property NSInteger value;
@end
@implementation MyClass
@end
@implementation 側でのインスタンス変数定義 → 不可
Xcode の Modern Objective-C では，外部に露出させる必要がないインスタンス変数は @implementation の側に書くことで隠蔽できますが，AtCoder では不可でした。
Class Extension → 定義はできるがインスタンス変数の定義不可
自作クラスに対して，追加で
@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 なら次のように書けます。
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 は使えます。
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 オブジェクトを要素に持つ単純な数の配列のソート
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 オブジェクトを要素に持つ配列のソート
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: が使えます。
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 を使ってみたところ，要素数が 105 くらいになってくると，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++ で書くのがよさそう，という当たり前の結論に至ってしまいました。
Author And Source
この問題について(Objective-C で AtCoder に参加する際の苦労), 我々は、より多くの情報をここで見つけました https://qiita.com/doraTeX/items/b5f094f68f7a7007f806著者帰属：元の著者の情報は、元の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 .