AtCoder始めてみて3ヶ月での知見を簡単にまとめておく
自己紹介
- 工業高等専門学校専攻科卒(本科は情報工学科だった)
- 卒研はアルゴリズム系の研究室で数値計算してた
- 現在開発系の会社でバイト中
- 記事執筆時点ではレート563の茶色
入茶したタイミングで記事を書きたいと思ったが少し時間が経ってしまった。
取り組み
現状としては、土曜21時のABCに参加するくらいで、それ以外の取り組みは特にしていない。
先日鉄則本を購入したのでこれを機に少しずつ勉強していきたい。
言語
Pythonを使用。
理由はなんか個人的な趣味のプログラムを作るときや、
とりあえずなんか作業を自動化させるか、
というときとかの言語はなんでもいいってなったときに、
一番使っている言語だから。
AtCoderの中ではC++の次？ぐらいに使われている言語みたいだし特に問題なさそう。
環境
VSCodeでコーディング、DevContainerを使用して、
Dockerのコンテナ上でプログラムの動作チェックをしている。
参考にしたリンク
スニペット
VSCodeのスニペット機能を用い、よく使う記述を一発で出せるようにした。
これをやるかやらないかで結構実装時間は変わると思う。
本当は色々記入しているが使っているのは一部だけなのでその部分を抜粋したものを以下に示す
長いので折りたたみ
一部は生成AIに記述してもらっている。(titleとかdescriptionとか)
{
"atcoder": {
"prefix": "hdr",
"body": [
"import sys",
"def rI(): return int(sys.stdin.readline().rstrip())",
"def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))",
"def rS(): return sys.stdin.readline().rstrip()",
"def rLS(): return list(sys.stdin.readline().rstrip().split())",
"def err(*args): print(*args, file=sys.stderr)",
"",
"def main():",
" N = rI()",
" N, M = rLI()",
" S = rS()",
" $0",
" print(\"Yes\")",
" print(\"No\")",
" print()",
"if __name__ == '__main__':",
" main()",
""
]
},
"for i in range(N)": {
"prefix": "for i range",
"body": [
"for ${1:i} in range(${2:N}):\n\t${0:pass}"
],
"description": "指定された範囲内で繰り返し処理を行うためのforループを生成します。"
},
"Print Bool as Yes/No": {
"prefix": "yn",
"body": [
"print(\"Yes\" if ${1:ans} else \"No\")\n$0"
],
"description": "ansがTrueなら\"Yes\"、Falseなら\"No\"を出力する"
},
"Python defaultdict": {
"prefix": "dd0",
"body": [
"from collections import defaultdict",
"${1:d} = defaultdict(lambda: 0)\n$0"
],
"description": "defaultdictを使用して変数を定義します"
},
"Python Read Integer": {
"prefix": "rdi",
"body": [
"${1:N} = rI()\n$0"
],
"description": "整数を読み込む"
},
"Python Unpack 2 Variables": {
"prefix": "rdi2",
"body": [
"${2:N}, ${3:M} = rLI()\n$0"
],
"description": "rLIを使用して2つの変数を読み込む"
},
"Python Unpack 3 Variables": {
"prefix": "rdi3",
"body": [
"${2:a}, ${3:b}, ${4:c} = rLI()\n$0"
],
"description": "rLIを使用して3つの変数を読み込む"
},
"Python Read List of Integers": {
"prefix": "rdli",
"body": [
"${1:A} = rLI()\n$0"
],
"description": "スペース区切りの整数リストを読み込む"
},
"Python Create Matrix with rLI": {
"prefix": "rdia",
"body": [
"${1:A} = [rLI() for _ in range(${2:N})]\n$0"
],
"description": "rLIを使用して行列を作成する"
},
"Python Read String": {
"prefix": "rds",
"body": [
"${1:s} = rS()\n$0"
],
"description": "文字列を読み込む"
},
"Python Read List of Strings": {
"prefix": "rdls",
"body": [
"${1:strings} = rLS()\n$0"
],
"description": "スペース区切りの文字列リストを読み込む"
},
}
参考にしたリンク
各コンテストごとの感想
今まで参加してきたコンテストについて軽く感想を書いておく。
少し時間が経ったものとかでうろ覚えなところはあるのかもしれないがそこはご容赦を。
ABC343
初めての参加でとくに環境も整備できていない状態で参加。
ブラウザとVSCodeを往復しながらなんとか3完。
D問題にも取り掛かってみたがギリギリ解けず。
連想配列を使う発想は合ってたが詰めきれなかった。
ABC344
この回から前述のDocker環境を用いて参加
ABは普通に解けるもCで沼って時間切れ。
Setを使う発想まではできたものの、全部計算することはしなかった謎。
そして適当にやりすぎてTLE出しまくっている。
ABC345
Cがギリギリ解けた。
同じ文字があると与えられた文字列を出力できるということを終了約20分前に気づき、なんとかAC
ABC346
Cが20分で解けたがBが解けなかった。
Bをやるか諦めてDをやろうか、どっちつかずになり、無惨に散って行った。
ABC347
今回もCを解けなかった。
指定の範囲に収まる条件をうまく見いだせなかった。
ABC348
Cが17分で解け、初の緑perfを獲得。
DとEが理解を受け付けず、Fがなんか行ける気がしたので取り掛かってみたが、実らず。
ABC349
16分半でC問題までをACしたあと、
D以降の問題を読んで解ける気がしなかったので離脱。
ABC350
今回も3完。
Dはグラフを使うという発想に至らずひたすら沼る。
ABC351
3完。
Dは幅優先探索すればいいという発想に至るのが終了まであと7-8分前後といったタイミング。
流石に遅すぎない？
そしてギリギリ入茶せず。
ABC352
この回によってレート400を超え、無事入茶。
13分で3完。
Dも頑張ってみるが実らず。
ABC353
久々にCが解けなかった
10**8を超える組み合わせの数だけ引くという発想はできたものの、
2分探索でうまく数え上げられないか悪戦苦闘。
うまくいかずに時間切れ。
尺取り法っていうのこの問題の解説をみて知った。
ABC354
安定の3完
D問題の4x2分割して考えることはいけたが、
コードにうまく落とし込むことはできなかった。
ABC355
この前解けなかったB問題の名前と同じ問題だったから戦慄したが普通にACできたので安心。
そしてCも時間がかかったがAC。
しかしDの壁を超えることはできない。
ここも尺取り法ですか…
振り返り
とりあえずABC343-355までの感想をまとめてみて感じたことは、
D問題を解けるようにしたいこと、
尺取り法などの典型アルゴリズムをある程度身につけることである。
冒頭に述べた鉄則本を読み込んで、D以降の問題を解けるようにしたい。