AtCoderで入水したのでこれまでのことを振り返る

2023年11月12日

11/11の「トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)にて、自身最高となるパフォ2,161を達成。

Highestを更新、入水をすることができた。

ぎゃーす！再入水しました！
Qlitreさんのトヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)での成績：290位
パフォーマンス：2161相当
レーティング：1181→1326 (+145) :)
Highestを更新しました！#AtCoder https://t.co/BazHxgnKbl
— QLITRE (@kuri_tter) November 11, 2023

Xのポストで「再入水」と書いている。

実は9/23のサントリープログラミングコンテストの時点で一度入水をしていた。

グラフを見ればわかる通り、次回にすぐに緑に落ちてしまった。

入水をしたので、このタイミングで入水記事を書いてもよかった。

だけど、まごまごしているうちに、緑に落ちてしまったので、書くべきタイミングを失ってしまった。

いや、確かに入水をした事実はあるので、入水記事を書くべき資格はあった。だけど気持ちの問題があった。

「入水しました！でも今は緑に落ちました」では少し決まりが悪い。記事を書くテンションもなんか下がる、これは確かにある。

このことから何を学んだかというと、色変をしたら速攻で記事を書くべきだ、ということだ。

気持ちがホットなうちに記事は書いておきたい。記事を書いた後に色落ちをするのと、色落ちをしてから記事を書くのでは、気持ちの上で圧倒的な違いがある。

というわけで、またいつ色落ちするかは分からないものの、少なくとも今は水色、ということを噛みしめながら、これまでのことを振り返りたい。

緑になってからの精進

前回入緑した際にエントリを書いていた。

https://www.qlitre-dialy.ink/post/became-green-coder-look-back-my-study

このエントリを書いたのが5月のことだったので、約半年で入水できたことになる。

振り返るとあまり特別なことはしてこなかったように思う。

緑になった時点で鉄則本は一周をしていた。そこから、新しく覚えたアルゴリズムはほとんどなかった。

では何をやっていたかというと、以下の２点が中心的だった。

コンテストに毎週出る
過去に解いた問題を解く

これだけだった。

入水するための能力としては、D問題まではコンスタントに解ける、E問題も解けることがある、くらいのレンジだと思っている。

緑になった時点でＤ問題までは解ける実力はあると思っていたので、そこからは打率を上げていくことが大事だと思っていた。

復習のツールとしてはAnkiを使うのがおススメ。

https://apps.ankiweb.net/

ご存知の方も多いかと思うが、ChatGPTに紹介をしてもらった。こんなアプリである。

Ankiは記憶を助けるためのフラッシュカードベースの学習ツールです。このアプリは、繰り返しのスペースを使って、効率的な学習方法を提供します。ユーザーはカスタムフラッシュカードを作成し、学習したい情報を入力することができます。Ankiはこれらのカードを一定の間隔で表示し、時間の経過と共に間隔を広げます。これにより、長期記憶に情報が定着しやすくなります。
Ankiの主な特徴は以下の通りです：
スペースドリピーティション：学習効率を最大化するために、忘れやすい情報は頻繁に、覚えやすい情報は少なく表示されます。
カスタマイズ可能：テキスト、画像、音声など、様々な形式でカードをカスタマイズできます。
多言語対応：様々な言語でカードを作成でき、言語学習にも適しています。
同期機能：異なるデバイス間でカードと進捗状況を同期できます。
オープンソース：開発者やユーザーがアプリを改善するために自由に貢献できます。
Ankiは学生、言語学習者、専門家など、あらゆる人に役立つツールです。

学習効率を最大化するために、忘れやすい情報は頻繁に、覚えやすい情報は少なく表示される、というのが良い。

使い方は非常に簡易的で、以下のように問題リンクだけ貼ったカードを作る。

リンクに飛んで、問題を解く。Show Answerをクリックすると、問題を解いてどうだったかの選択肢が出る。

簡単だと思ったら、しばらく同じカードが出ない。

難しいと思ったらすぐに再学習できるように、というコントロールができる。

この学習方法を続けることで、「以前はできたけど身についてなかった」というようなこぼれを減らすことができる。

苦手な問題も繰り返すことで、解けるようになる。苦手意識がなくなることもある。

ChatGPTを使う

前回の入緑エントリでも公言をしているが、自分はコンテスト中にChatGPTを普通に使っている。

コンテストで生成AIを使うことに対する是非はあると思うが、この記事では是非については書かない。

緑になる直前くらいから使い始めて、実際に使ってみた感想やどのように使ってるかを書く。

使用モデル

課金しているので、GPT-4を使っている。

そのため以下の内容はGPT-4を使用していることが前提になる。

解けるレベルの問題について

検証等はしていない。かなり感覚的ではあるが列挙する。

C問題まではほぼ100％解ける
D問題は複雑な問題でなければ大体解ける
E,Fは典型的な問題であれば解ける

自分で解ける問題は自分で解いた方が圧倒的に早いし、正確性も高い。

C問題まではほぼ自力で解けると思ってるので、あまり使わないが、GPT-4なら恐らくほぼ100%解ける。

D問題は茶dfffから水diffまであり幅が広い。茶～緑前半の典型的なDP、BFS、DFSなどをするような問題は大体一発で解けるような気がする。

ただ、前処理が必要だったりするケースは多少のプロンプトを与えなければ厳しい。

E,Fは大体解けない。高度典型アルゴリズムを使えば解ける、みたいなタイプの問題は解けることもある。

実際に昨日のトヨタコンのF問題は「重み付きUnionFindを貼るだけ」という感想が終了後に飛び交っていた。

https://atcoder.jp/contests/abc328/tasks/abc328_f

こういう典型的な問題はChatGPTが得意とする分野である。実際にACが出来た。

使い方

以下は自分がどういう風に使っているかを書く。正直あまり新しい話はないと思う。

英語で使う

一般的にChatGPTは英語を解釈し、英語で思考した方が精度が高いと言われている。

そのため、自分も利用する際は英語でプロンプトを投げるようにしている。

英語の問題文を張り付けて、

Please solve this problem by python.

みたいに書く。これだけで結構良いコードが出てくる。レスポンスも圧倒的に日本語より速い。

ただし、自分は英語ができないので、読解に時間がかかるのと、対話ができない欠点がある。

in this sample case expect is ...
but your output is ...

間違ってる時はこんな風に指示をすると、正答になることもある。

バグの発見

なんかサンプルは通ってるけど、一部のテストケースでWAが出る、あるいはTLEになるみたいな場面で助言を聞く。

「ほとんど解けているはずなのに、なんか通らない」みたいな場面の最後の一押しを助けてくれることが多い。

こういう地味な補助も、レートの底上げにつながっている。

途中まで書いて、続きを書いてもらう

一発で答えが出ないときに良く使う手法。

なんとなくこういう方針だと思うんだけど、最後の詰めが分からんなあ…という時に使う。

最近だとこの問題でその手法を使った。

https://atcoder.jp/contests/abc324/tasks/abc324_d

長さNの数字をあらわす文字列が与えられて、並び替えた時に平方数となるようなものはいくつあるか？という問題。

この問題は普通にプロンプトを投げると以下のような順列全生成のアルゴリズムを提案してくる。

from itertools import permutations
from collections import Counter
import math


def count_square_permutations(S):
    # Count the frequency of each digit in the string
    digit_count = Counter(S)

    # Generate all unique permutations
    unique_permutations = set(permutations(S))

    # Check each permutation if it is a square number
    square_count = 0
    for perm in unique_permutations:
        # Convert tuple to integer
        num = int(''.join(perm))

        # Check if the number is a square
        if math.isqrt(num) ** 2 == num:
            square_count += 1

    return square_count

小さい入力では時間内に終わるが、Nは13まであるので、最大で6227020800まである。明らかにTLE。

発想を転換させて、平方数の数は13桁の中でもそんなに多くなさそう、という点に目を向ける。そこでプロンプトをこうする。

順列の生成は明らかに厳しい。以下のように平方数を事前に数え上げて判定したらどうだろうか。
```
def job():
    n = input()
    s = list(input())
    s.sort()
    # 最少の数字
    s.sort()
    min_s = int(''.join(s))
    # 最大の数字
    s.sort(reverse=True)
    max_s = int(''.join(s))
    squares = []
    # 事前に平方数のリストを作る
    for i in range(10 ** 7):
        num = i ** 2
        if min_s <= num <= max_s:
            squares.append(str(num))
        elif num > max_s:
            break

    # ここから続きを書いて
```

以下のような回答が来る。

def count_square_permutations_optimized(S):
    n = len(S)
    s_sorted = sorted(S)
    # 最少の数字
    min_s = int(''.join(s_sorted))
    # 最大の数字
    max_s = int(''.join(s_sorted[::-1]))
    squares = []
    # 事前に平方数のリストを作る
    for i in range(int(math.sqrt(max_s)) + 1):
        num = i ** 2
        if min_s <= num <= max_s:
            squares.append(str(num))

    # 平方数がSとして再配置できるかチェック
    count = 0
    for square in squares:
        if sorted(square) == s_sorted:
            count += 1

    return count

さっきよりもいい感じ。

だけど、これもちょっと間違っていて、4320という数字があったときに０が先頭に来る場合を考慮できていない。

そのことを伝えるとゼロパディングを行ってくれる。これでACになる。

import math


def count_square_permutations_optimized(S):
    n = len(S)
    s_sorted = sorted(S)
    # 最少の数字
    min_s = int(''.join(s_sorted))
    # 最大の数字
    max_s = int(''.join(s_sorted[::-1]))
    squares = []
    # 事前に平方数のリストを作る
    for i in range(int(math.sqrt(max_s)) + 1):
        num = i ** 2
        if min_s <= num <= max_s:
            square_str = str(num).zfill(n)  # 長さを N に合わせるために 0 を埋める
            squares.append(square_str)

    # 平方数がSとして再配置できるかチェック
    count = 0
    for square in squares:
        if sorted(square) == s_sorted:
            count += 1

    return count


n = int(input())
S = input()
print(count_square_permutations_optimized(S))

正直言って、「事前に平方数を前計算しておく」という方針に気づいた時点で、あまり使う意味がないかもしれない。

実際にコードを書かなくても、アイデアベースでこうしたらどうか…と伝えるのはよくやる。

「それは無理、それは良い考え」みたいに感想をくれる。

間違った実装に走る危険を低減してくれる。