@drken さんの名記事
にある精選10問を，Objective-C で解いてみました。
他の言語の記事はこちらにまとまっています。
制限事項
AtCoder での Objective-C には，前記事に挙げた様々な制約があります。その制約下で頑張ることを目指します。
準備：標準入出力クラス
前記事で述べたように，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していれば使えます。