質問

正直、自分のコードはそんなに悪くないと思うのですが......。これは私が考え出した5番目のバージョンで、今のところベストだと思います......。しかし、foo.barのコンソールでテストを実行すると、"Time limit exceeded"と表示されます。

もっと速くする方法はないでしょうか？今のところ途方に暮れています......。

これがREADMEです。

キュー・トゥ・ドゥ

LAMBCHOPドゥームズデイを破壊するための準備はほぼ整った。 しかし、基本システムを保護するセキュリティ・チェックポイントが LAMBCHOPが問題になりそうだ。あなたは、1つを取ることができました アラームを作動させることなくダウンさせることができ、素晴らしいです。ただし ラムダ司令官の助手として、あなたはチェックポイントが つまり、あなたの妨害工作は、自動審査されることになります。 を騙さない限り、発覚して正体がばれる。 自動審査システム

このシステムを騙すには、同じものを返すプログラムを書く必要があります。 警備員が持っているはずのセキュリティチェックサムを 作業員全員をチェックする。幸いなことに、ラムダ司令官は 効率性を追求するあまり、何時間も並ぶことは許されない。 チェックポイントの警備員は、通過率を早くする方法を見つけました。 通ってくる労働者を一人一人チェックする代わりに、警備員は その代わり、並んでいる全員のセキュリティIDを確認し、その後 列が再び埋まるのを待つ。そして、その列が再び埋まるのを待つ。 今度は最後の一人を残して、また列を作る。続けて このように、毎回もう一人ずつ抜けていくのですが、その度に チェックした人のセキュリティIDを記録して、一人分飛ばすまで。 その時点で、すべての作業者のIDをXORします。 チェックサムを作成し、ランチに出かける。幸いなことに 作業員は整然とした性格なので、常に番号順に並びます。 を隙間なく並べる。

例えば、列の先頭の作業員のIDが0であり、セキュリティの チェックポイントの列は3人なので、次のような流れになります。 0 1 2 / 3 4 / 5 6 / 7 8 ここで、警備員のXOR (^) チェックサムは次のようになります。 0^1^2^3^4^6 == 2.

同様に、最初のワーカーのIDが17で、チェックポイントに4つの ワーカーの場合、以下のような処理になります。17 18 19 20 / 21 22 23 / 24 25 26 / 27 28 29 / 30 31 32 これは、チェックサムを生成します。 17^18^19^20^21^22^23^25^26^29 == 14.

すべてのワーカーID（最初のワーカーを含む）は、0から チェックポイントの行は常に最低でも 1ワーカーの長さです。

この情報を使って、次のような関数 answer(start, length) を書いてください。 と同じものを出力することで、セキュリティチェックポイントの欠落をカバーします。 のチェックサムは、昼食前に警備員が通常提出するものです。あなたには、ちょうど 最初にチェックされる作業員のIDを見つけるのに十分な時間があります。 (開始)とラインの長さ(長さ)は、自動化される前のものです。 そのため、あなたのプログラムは、適切なチェックサムを生成する必要があります。 この2つの値だけです。

言語

Pythonのソリューションを提供する場合は、solution.pyを編集します。 を編集してください。

テストケース

入力 (int) start = 0 (int) length = 3 出力。 (int) 2

入力です。 (int) start = 17 (int) length = 4 出力。 (int) 14

verify [file] を使って、あなたの解決策をテストし、その結果を確認します。このとき コードの編集が終わったら、submit [ファイル] でコードを送信します。 の答えです。テストケースに合格すると、その解答は削除されます。 をホームフォルダから削除してください。

そして私の解答。

def answer(start, length):
    f = 0
    r = 0
    while f < length:
        for i in range(start, (start+length) - f):
            r ^= i
        f += 1
        start = range(start, start+length)[-1] + 1
    return r

解決方法は？

ヒント1

XOR 5^6^7^8 は XOR(1^2^3^4^5^6^7^8)^(1^2^3^4) と同じです。

つまり、最初のn個の自然数のxorとなる関数を見つけることに集中し、その関数を使って、任意の範囲の整数のxorを求めることができるのです。

ヒント2

最初のn個の自然数のxorを求めるには、2進法表現を考える。

000
001
010
011
100
101
110
111

1つのビット位置に集中して、すべての数値のxorを計算したときに得られるパターンを考えてみてください。