ICFPC 2024 参加記
ICFPC 2024にソロ参加したので、その記録です。
かなり久しぶりの参加でした。とんでもなく面白かったです。
参加前
コンテストページに Endoさんが写ってたりしたのもあって、個人的に期待値が高まってました。
全体の方針
特定の種目を極めるのも楽しそうでしたが、今回は全体の順位を上げることを目的にして、その時点で順位の低い種目に随時取り組むという戦法でやりました。
ソースコードは、全てPython(SageMath)で、jupyter notebook上で実行しながらやりました。
Communication channel
コンテストでは、データを POST してCult of the Bound Variableとコミュニケーションをとる必要がありました。ネットの知識がないので、実はここで詰みかけました。
とりあえず、何も分からないので、以下をchat GPTに投げました。
次の説明文を参考に、http postをするためのpythonの関数を実装してください。
[ ここに問題文の一部を貼り付けました。 ]
返ってきたpythonコードは以下の通り。
import requests
def send_post_request():
url = 'https://boundvariable.space/communicate'
payload = {'ICFP': 'S\'%4%}).$%8'} # Assuming this is the payload format
headers = {'Authorization': 'Your_Authorization_Header'}
try:
response = requests.post(url, json=payload, headers=headers)
response.raise_for_status() # Raise an exception for bad status codes
# Print the response or do something with it
print(response.text)
except requests.exceptions.RequestException as e:
print(f"Error: {e}")
# 実際のリクエストの送信
send_post_request()
しかし、これだと全然ダメなようで、色々と試行錯誤した結果、ようやく次のコードで成功しました。
import requests
def send_post_request(mes):
url = 'https://boundvariable.space/communicate'
payload = {'ICFP': mes } # Assuming this is the payload format
headers = {'Authorization': 'Bearer [...実際にはここにAutherization keyを入力している..]'}
try:
response = requests.post(url, data = mes, headers=headers)
response.raise_for_status() # Raise an exception for bad status codes
# Print the response or do something with it
return response.text
except requests.exceptions.RequestException as e:
print(f"Error: {e}")
Hello
Helloは、最初なかなか満点を取る方法がわからず焦りました。
language_test は、echoで解いてもらおうとすると、断られるので、少しだけコードをいじってechoで解いてもらうという、裏技（？）で乗り越えました。
lambdaman
visualizerをchat GPTに作ってもらい小さい盤面は手で解きました。
大きい盤面は、頑張って一つ解を作って、icfpc言語で圧縮しました。
上位があまりにも文字数が少ないことに気づいて、DURL列をいい感じに生成して、盤面全体を動き尽くす考えてましたが、うまくいかず。乱数も考えましたが、コードの上限的に無理っぽいと判断しました。
spaceship
ケースによって、かなり個性が分かれており、統一的に記述するのも難しそうなので、大変でした。ルールベースで、アドホックになんとかしました。TSPソルバーがあればかなり便利そうなので、ネットから探しましたが、適切なのが見つけられませんでした。
3d
最初（説明を読むのが面倒だったため）Time Warpを使わずに書いてましたが、ちゃんと説明を読むと、実はめっちゃ重要な機能だったので、後でループは全てTime Warpを使う形に書き直しました。最終的には3d9まで解きました。
最後に送ったのは多分次です。（3d5のコードはなぜか紛失した）
mes = """solve 3d1
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . > . > . > S . . . .
. . . ^ . . . . 1 . . . . .
. . . . . . . A # . . . . .
. . . ^ . . . < . - . . . .
. . . 1 > . * . . . . . . .
. . . . . . . . . v . . . .
. . . . . 3 @ 2 . . . . . .
. . . . . . 3 . 2 @ 5 . . .
. . . . . . . . . 3 . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
"""
print( string_communication2(mes) )
mes = """solve 3d2
. 1 . A . -1 . A . . .
A - . % . = . * S . .
A > . > . > . > . > S
"""
print( string_communication2(mes) )
mes = """solve 3d3
. . . 1 . A . 1 . .
. A A + . / . = S 0
1 = S . . . . . A =
. . . A . A . -1 = S
. . 1 - . / . = S .
"""
print( string_communication2(mes) )
mes = """solve 3d4
. . . . . . . . . . . . . . . . . .
. . A . . . . . . . . . . . . . . .
. 1 + . . . . . . . . . . . . . . .
. . . > . . . . . . . . . . . . . .
. B = 2 @ 3 . . . . . . . . . . . .
. . S . 2 . . . . . . . . . . . . .
. . B . . . . . . . . . . . . . . .
. 1 + . . . . . . . . . . . . . . .
. . . > . . . . . . . . . . . . . .
. A = 2 @ 3 . . . . . . . . . . . .
. . S . 2 . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
"""
print( string_communication2(mes) )
mes = """solve 3d6
. . . . . . . A .
. . . . . . 1 = S
. 2 > . > . + . .
A = A % . . . . .
. . . . . 5 @ 2 .
A / 0 = S . 3 . .
. S . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
"""
print( string_communication2(mes) )
mes = """solve 3d7
. . . 10 . . . . . . . . . . . . . .
. . . / . > . . . . . . . . . . . .
. . ^ . . 4 @ -3 . . . . . . . . . .
. . . . . . 4 . . . . . . . . . . .
. . ^ 10 . 0 . 10 . . . . . . . . . .
. . A % . + . * . > . . . . . . . .
. . v . . . . . . 5 @ 2 . . . . . .
. . . . A = . . . . 4 . . . . . . .
. . v . . . . . . . . . . . . . . .
. . . . A / S . . . . . . . . . . .
. 0 = S . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
"""
print( string_communication2(mes) )
mes = """solve 3d8
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 0 * . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . + S . . . . . . . .
. . . . . . . . . . . . . ^ . . . . . . . . . .
. . . . . . . . < . < . < . . . . . . . . . . .
. . . . A . . / . > . . . ^ . . . . . . . . . .
. . . . v . ^ . . 4 @ -5 . 2 > . + . . . . . . .
. . . . . . . . . . 5 . . v . . . . . . . . . .
. . . . v . ^ . . . < . < . . 3 @ 2 . . . . . .
. . . . . . . . . v . . . v . . 5 . . . . . . .
. . . . v . ^ . . . . 0 . . . . . . . . . . . .
. . . . . > . > . % . + . * . > . . . . . . . .
. . . . . 0 = . . . . . . . . 5 @ 2 . . . . . .
. . . . . . . . . . A = . . . . 5 . . . . . . .
. . . . . 1 + . . . . . . . . . . . . . . . . .
. . . . . . . . . . -3 @ 16 . . . . . . . . . . .
. . . . . -10 @ 11 . . . 3 . . . . . . . . . . .
. . . . . . 2 . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
"""
print( string_communication2(mes) )
mes = """solve 3d9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . 0 . . . . . 1 . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . * S . . > . = S . . . . . . . . . . . . .
. . . . . . . . . . . . . . ^ . . . ^ . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . < . < . < . < . < . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . ^ . . . . . . . . . . .
. . . . . . . . . . . . A . 10 . 2 . 3 . . < 1 > . . . . . . . . . . . .
. . . . . . . . . . . 0 # . % . * . - . + . > . . . . . . . . . . . . .
. . . . . . . . . . . . . v . . . . . . . . 1 @ 2 . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . 0 = . . 6 . . . . . . . . . . . .
. . . . . . . . . . . . . v 10 . . . . . S . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . / . > . > . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 7 @ 6 . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . 6 . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
"""
print( string_communication2(mes) )
efficiency
変換器を作って多少読みやすくしてから解読しました。SATはSAT solverに投げました。
最終結果
総合順位は30位でした。自分ではソロ参加の割にかなりいい順位がとれたと思っています。
ネットワーク、エンコード、ヒュリスティック的な最適化、esoteric language、リバースエンジニアリング、数独、など色々な要素の詰まった、本当に楽しい問題でした。
競プロ練習記録（ABC189、ABC190など）
ABC190に参加した。その前に練習で ABC189もやっておいた。ABCトーナメントに参加するのが主要な動機。練習自体には、多少慣れた以上はあまり意味がなかったが、python のTLE対策に関してはいくらか知見を得た。
コードテストについて
実行時間的に間に合うかどうか微妙な時は高速化する必要がある。その場合、
- 闇雲に高速化する。
- コードテストでパフォーマンスをチェックしながら確認する。
の二通りの選択肢がある。最悪ケースが簡単に作れる場合は迷わずに 2. の選択肢を選ぶが、そうでない場合は 2. ができるように入力を作るのが億劫で 1. で無理やり何とかしてみようとすることが多かった。
しかし、そんなに億劫がる必要はない気もする。
例えば、今回最初にTLEした
Submission #19812154 - AtCoder Beginner Contest 190
の場合、入力部分は
N,M = map(int, input().split()) edges = [[] for _ in range(N)] for _ in range(M): a,b = map(int,input().split()) a-=1 b-=1 edges[a].append(b) edges[b].append(a) K = int(input()) cs = [int(s)-1 for s in input().split()]
となる。これを大きな入力についてテストしようとすると、例えば
if 0: N,M = map(int, input().split()) edges = [[] for _ in range(N)] for _ in range(M): a,b = map(int,input().split()) a-=1 b-=1 edges[a].append(b) edges[b].append(a) K = int(input()) cs = [int(s)-1 for s in input().split()] if 1: N,M = 10**5, 10**5 edges = [[] for _ in range(N)] for i in range(M): a,b = i,(i+1)%N edges[a].append(b) edges[b].append(a) K = 17 cs = [s**3 for s in range(K)]
となるが、コピーペーストで被る部分の多さを考えると、実は大した労力ではなさそうだ(５分もあれば十分？)。
結論：TLEチェック用の入力を自作するのは実はそこまで手間がかからない。闇雲に高速化を試みるより、はるかにまし。
入出力について
import sys input = lambda: sys.stdin.readline().rstrip()
とするだけで爆速になる。早速、atcoder-toolsの 「# Failed to predict input format」部分に追加した。
PyPy3で提出
atcodertools/common/language/.py の PYTHON部分で該当箇所を、 submission_lang_pattern=re.compile("^PyPy3.*"),
に書き換えた。これで、atcoder-tools submit したときにPyPy3で提出してくれるようになった。
消費時間
全体では６〜８時間ぐらい使ったように思う。しかし、今回のABC練習は基本的にABCトーナメントをより楽しむためのもので、レート向上を目指したものではない。TLE原因の調査などはレート向上を目的としたものなので、だいたい３時間ぐらいをレート向上のための消費時間として計上するのが妥当か。このあたりはルール曖昧だが。
今回の消費時間：3時間
今年の消費時間：17時間
競プロ練習記録(キーエンス プログラミング コンテスト 2021)
キーエンス プログラミング コンテスト 2021に参加した。
ARC級コンテストはおそらく レート期待値<現在のレート なので、参加するのはレート的に損だと思ったが、折角なので参加した。
また、コンテスト前に、E - Wandering TKHS (まだ途中)を考えたり、環境整備したりした。
結果
ABCD の4完で238位レーティング：2534→2503 (-31)
- A,B ・・・特になし
- C・・・落ち着いてできなかった。途中で勘違いに気付いた時に小手先の修正だけで何とかしようとして余計に被害を広げてしまった。そんなときこそ落ち着くのが大事。
- D・・・今回はたまたま思いついたが・・・。若干運任せなところがある。
E問題について
解説を読んで完全に理解したが、この方針を確実に思いつくプロセスを確立できていない。
方針を思いつくための方針論を、後日考察したい。
TODO
- E - Wandering TKHS の研究
-
E - Greedy Ant の研究
消費時間
今回の消費時間：3時間
今年の消費時間：14時間
競プロ練習記録（簡単めの問題、実装なし）
前回の練習 で典型力が足りないと考えたため、問題をたくさん見てみることにした。
やったこと
AtCoder Problems 上でdifficulty 1200 〜1999 の 2018年の問題（全部で40問強ぐらい）を、一問5分程度を目安に頭の中で方針だけ考えるということを、何日かに分けて行った。
結果
難易度1200〜1599の問題については成果なし。5分以内に思いついた問題がほとんどで、苦労した問題はなし。
難易度1600〜1999では、短時間では方針が浮かばなかった問題は次の1問だった。
- C - String Coloring これは、半分全列挙が想定解。列の長さが36というだけで指数関数時間アルゴリズムを方針から外してしまった。
あと、間違えてしまったのは次の二問。
まとめ
苦労したARC111のB問題が diffiiculty1300 ほどなので、その点数帯の問題をたくさん当たれば、苦手がつぶせると期待したが、その当ては外れてしまった。
ただし、頭を慣らすには良さそうなので同様の作業をコンテスト直前にするのはありかもしれない。
おそらく見逃している典型がまだまだあると思うが、割合的には少ないだろうし、発見するのにも時間がかかる。この方向性は辞めてもっと考察が重い問題を練習した方が効率が良さそう。
今回の消費時間：5時間ぐらい
今年の消費時間：11時間ぐらい
あと、ACLライブラリを見てみたり、segment treeに関する理解を深めるなどもしたが、これは競プロ本位の勉強じゃないので、上の時間にはノーカウントとした。
競プロ練習記録(ARC111)
ARC111のA~Eで練習。
各問題について
A
特になし。
B
カードを辺と思う発想はなかった。もう少し知識を広げて、典型と感じれる範囲を増やした方がいいかも。
C
特になし。
D
前回の反省でpythonの再帰を使うべきじゃないと書いたのに、この問題ではむしろ再帰を使わないと厳しかった。
E
解説を見るに、floor_sum を知らないと厳しい問題っぽい。知識が不足している。
総合的な反省点
- 考えてる途中、割とぼーっとしがち。集中し続けることの難しさを痛感する。
- 十分に方針を固めてから実装しないと、かえって時間がかかる。
- 典型力(?)が足りていない。大量に問題を見た方が良さそう。
- ACLは、確認しておいた方が良さそう。
今回の消費時間：約3時間
今年の消費時間：約6時間
集中力が足りてない。今回の練習効率はあまり良くなかった。
競プロ練習記録（ABC187、環境整備など）
開催してたABC187で録画しながら練習した。
Eで詰まったので途中で切り上げて、録画の分析。
観察したこと
- テストや提出をするための作業に一問60〜90秒ほど使っている。これは、コンテスト時間の10％ほどを占めうるので、自動化するメリットはそれなりに大きそう。
- ケアレスミスによるタイムロスは想像以上に大きい。思った以上に確実性を優先した方が良さそう。
- pythonで再帰は絶対ダメ。スタックを使う。
環境の整備
上記を踏まえ、環境を整備した。具体的にはatcoder-toolsをインストール。
~/.atcodertools.tomlを作成し、以下のようにした。
[codestyle]
indent_type='space' # 'tab' or 'space'
indent_width=4
#template_file='~/my_template.cpp'
workspace_dir='~/atcoder-workspace/'
lang='python' # Check README.md for the supported languages.
#code_generator_file="~/custom_code_generator.py"
[postprocess]
exec_on_each_problem_dir='clang-format -i ./*.cpp'
exec_on_contest_dir='touch CMakeLists.txt'
[etc]
download_without_login=false
parallel_download=false
save_no_session_cache=false
in_example_format="in_{}.txt"
out_example_format="out_{}.txt"
また、バグがあってsubmit出来なかったので
に従い、修正。
以上の作業で動くようになった。
今回の消費時間は全部で3時間ほど。
2021年の競技プログラミングの目標
最近は、惰性で競技プログラミングをしていてあまり良くないなと思ったので、今年は目標を立てることにしました。
目標
今年の目標は
「出来るだけ少ない消費時間でAtCoder赤になる」
とします。
消費時間というのはコンテスト参加時間や練習、解説を読むなど、レートを上げるための作業全般に使う時間とします。
現状
私は、5~10年ほど前は割と熱心にやってましたが、最近は全然です。
私の現在のレートは2534で、2800から赤コーダーなので、あと300弱上げる必要があります。
これがどの程度の難易度かはあまり検討がついていません。
アクティブユーザのみのランキングでは、私は現在264位で、144位からが赤なので人数的には半分ほどですが果たして。
目標の詳細
とりあえず、競プロ（Heuristics系のコンテストを除く）に使った時間は大まかにでも記録しておこうと思っています。
目標としては出来れば50時間以内で達成したいです。
150時間以上は絶対に使わないようにします（150時間使っても赤コーダーになれなかった場合は、その時点で諦める）。
