Paizaのスキルチェックで再帰を使ったらランタイムエラーになった話

2021-09-08技術,プログラミング言語

Paizaというところでスキルチェックというものがあります。そこの問題で回答に再帰を使ったらエラーが出たので、その話を書いておきます。

Paizaのスキルチェックとは

Paizaスキルチェックとはpaiza株式会社が提供するプログラミングのスキルチェックのサービスです。いくつかの難易度に分かれた問題を解くことで、スキルを評価してくれます。言語もいろいろあるので、好みの言語でチェックができます。

ログイン | ITエンジニア向け転職・就活・学習サービス【paiza】

ログイン画面です。｜ITエンジニア・プログラマ向け総合求職・学習サイト【paiza】

https://paiza.jp/challenges

paiza社はスキルチェックだけでなく、プログラミングの学習から転職支援までやっており、このスキルチェックである程度の評価を得ると、スカウトが来るというのが売りになっています。

自分の場合、某人力質問サービスにこのスキルチェックに関連してテストケースでエラーになるがどうしたら良いのか？といった質問があり、その回答のために登録しました。

このスキルチェックではお題に沿ってプログラムを実際に書いて実行することで、その結果が正解と一致するかで評価します。それをテストケースと呼んでいます。入力例と正解のセットがあり、ユーザが書いたコードを動かした結果がそれと一致するかで判定しているようです。
問題は入力を与えると出力されるプログラムになっており、その出力を正解と比較するので、途中で余計なものを出力するとエラー扱い＝不正解になります。

テストケースは問題によりますが10個程度あり、そのうち2〜3個は提出前にチェックできます。ただ、その入力例として掲載されているもの以外の入力サンプルは公開されていません。そのため、入力例として公開されているものではプログラムが正常に動いても、非公開部分のテストケースでエラーになることがあります。

上に書いた質問者の方も、公開分は通ったものの、その先のテストケースでエラーが出て、どうしたら良いのか分からなかったのかと思います。
と言うのも、入力サンプルも非公開ですが、その実行結果はOK/NGと処理時間だけが公開され、どんなエラーが出たのかは利用者には分からない仕組みになっています。

失敗すると「再チャレンジして高得点を目指しましょう」と出てきますが、そもそも再チャレンジしようにも、何が問題だったのかが分からない仕様になっています。問題を見直して、どこかでミスしてないかを確認した上で、自分でありそうな入力サンプルを作って試してみるしかありません。質問者の方はどんなサンプルを作れば良いかが分からなかったようです。
正直に言えば、入力サンプルが非公開なのでスキルチェックでどういうものをチェックしているのか分かりません。ですので、一般論として境界値のチェックをしましょうとか回答するしかないのですが、実際のところはなんとも言えません。

余談ですが、再チャレンジして高得点を目指せとか言いつつ、評価に使われるのは最初の一回目のチェックだけなので、再チャレンジしても評価は上がりません。と言うより、失敗した時点で評価が下がります。
下がった評価は再チャレンジしても上がらないので、別のスキルチェックの問題を正解するしかありません。

再帰でエラーが出る

今までもケアレスミスとかで初回クリアできずに失敗扱いのものがいくつかあります。大体がケアレスミスなので問題文かコードをよく見直せばなんとかなりました。例えば、コピペしてコード直し忘れたりとか。
が、どうしてもダメだったのが「B079:相性チェック」の問題。

スペース区切りで名前を2つ入力すると、それを数字に置き換えて計算して相性を出力すると言うものです。まあ、再帰の例題みたいな問題だったのでサクッと再帰を使ったコードを書いたのですが、10テストケースの最後の3つがランタイムエラーになりました。

一応、文字列が長い時はちょっとやばいかと思ったので事前に数百文字のコードを入れてみたのですが、そちらは正常に実行できます。まあ、本当に計算できているかは面倒なので確認していませんが、少なくともランタイムエラーにはなりません。このテスト環境は paizaが提供しているpaiza.ioというブラウザでコーディングとテスト実行ができるサービスを利用しています。

右端に実行処理時間が出力されていますが、それがテスト7に比べてだいぶ多いのが分かります。つまり、処理時間がかかっているということは、おそらく長い文字列を入力に使っていると推測できます。

実際のコードを出すことはできないので、計算部分を除いたフローがわかるようなレベルの抜粋を掲載しておきます。

# 相性の計算
def calc_affinity_sub(numbers):
    # 数列のサイズを取得
    numbers_size = len(numbers)
    
    # サイズが2なら足したものを返す
    if numbers_size == 2:
        num = numbers[0] + numbers[1]
        if num > 101:
            num = num - 101
        return num
    else:
        # 中略
        return calc_affinity_sub(new_numbers)

# 相性を計算
def calc_affinity(name1, name2):
    # 中略
    # 相性の計算    
    return calc_affinity_sub(number_list)

# 名前を取得
items = input().split()
name1 = items[0]
name2 = items[1]

# 2パターンで相性を計算
result1 = calc_affinity(name1, name2)
result2 = calc_affinity(name2, name1)

# 大きい方を出力
if result1 >= result2:
    print(result1)
else:
    print(result2)

適当に長い文字列を入力にしてもランタイムエラーが起きないのでちょっとお手上げです。エラーメッセージとかが出ればヒントになるのですが、結果のOK/NGしか出てきません。

仕方ないので非再帰版を作って実行したところ、これは通りました。元の再帰版を手直ししているので最適化していませんが、そこはご愛嬌ということで。

# 相性の計算
def calc_affinity_sub(numbers):
    # 数列のサイズを取得
    numbers_size = len(numbers)

    # 数列サイズが2になるまで繰り返す
    while numbers_size != 2:
        new_numbers = []
        # 中略            
        numbers = new_numbers
        numbers_size = len(numbers)
    
    # 計算結果を返す
    num = numbers[0] + numbers[1]
    return num

# 相性を計算
def calc_affinity(name1, name2):
    # 中略  
    # 相性の計算
    return calc_affinity_sub(number_list)

# 名前を取得
items = input().split()
name1 = items[0]
name2 = items[1]

# 2パターンで相性を計算
result1 = calc_affinity(name1, name2)
result2 = calc_affinity(name2, name1)

# 大きい方を出力
if result1 >= result2:
    print(result1)
else:
    print(result2)

基本ロジックは変えていないので、違いはアルゴリズムに再帰を使っているかどうか。情報を出してくれないので推測になりますが、おそらく長い文字列が入力された結果、メモリ不足にでもなったのかもしれません。

テスト環境ではエラーにはならなかったのですが、こちらの想像以上に入力文字列が長かったか、実行環境のメモリ制約がきついかのどちらかかと思います。一応、入力パラメータの条件としては、2つの文字列それぞれ1000文字までとなっています。

再帰は使わない方が良いかも

他の言語で試してないので、Python3だけなのか他も同様かは分かりません。ただ、再帰を使うとランタイムエラーになる可能性がありそうです。制限時間内でやり直しができるのであれば良いのですが、一度提出したらそれで評価が決まってしまうのでリスクは避けた方が良いかと思います。

今回の場合、2つの文字列の長さの和をnとすると、n!の関数呼び出しが発生するので、nの最大値2000ということを考えると、そりゃ再帰なんて使っちゃダメということになるとは思います。

実際問題、アルゴリズムのお勉強で再帰は大体学ぶかと思います。が、実際のコーディングで再帰を使ったことなんてあまりありません。と言うより皆無かもしれません。上でサクッと書き換えたように再帰を使わなくてもなんとかなるし、その方が効率が良いので。
そう言う意味では実践的なのかもしれません。

ご参考：難易度について

スキルチェックの問題の難易度はS/A/B/C/Dの5段階あります。自分は面倒なのでBまでしかやってない上に、上述の通り失敗扱いなので、評価ランクCです。そのため、あまり説得力がないかもしれませんが、各難易度がどんなものかの目安を書いておきます。

ランクD

プログラミングというか、なんと言うか。

入力を与えられたら、それになんらかの計算をして、出力するという問題になっています。

例えば、mmをcmに換算する、とか。言語によりますが2〜3行でできるような簡単なものです。コメントの入れ具合とか、コードのまとめ具合にもよりますが、10行程度でしょうか。

ランクC

多少はロジックが入ってきます。条件分岐とかループも必須になります。

与えられた入力を元に計算した上で、判定をして、その結果を出力するような問題になっています。使うものもランクDは入出力と四則演算くらいでしたが、文字列操作とかも必要になってきます。目安としては20〜30行程度になります。

9/9補足

ランクDくらいならば単純な計算の問題が多く、公開されているテストケースが全て動けば大体全て通るかと思います。ただ、ランクCくらいになると「意地悪」なテストケースが出てくる様に感じるので、ちゃんとテストケースを想定して公開されているサンプル以外の入力も試しておいた方が良いです。自分もサッと動いて安心して見落としでエラーになってしまったことが何回かあります。本当の見落としも一回ありましたけど。
実際、テストのスキルはこういう「意地悪」なテストケースをどれだけ作れるかが問われます。このスキルチェックでは一発で合格を出せないといけないですが、実際の現場では必ずしもそうでもありません。
もちろん、スラスラと一発で動くコードが書けるに越したことはありませんが、ちゃんとポイントを抑えたテストケースを作り、それが通るように直していけば良いだけなので、競技プログラミングみたいに早く動くコードが動けば良いというわけではありません。
実際、自社や協力会社問わず、テストケース書かせると正しい正常系しか出してこない人がいますが、正しい正常系とエラーになる正常系と、異常系の3パターンを出してこないと困ります。