41歳エンジニア、競プロを始める
daisuke-fukudaリンク集
daisuke-fukuda24歳に未経験からエンジニアになり、フルスタックのWEB系エンジニアを名乗ってはいるものの、実はずっと苦手意識があったアルゴリズムを鍛える事にした。
モチベーションは以下の通り。
- web系エンジニアとしての頭打ち感
- web系って、技術的には良くも悪くも枯れてきましたよね
- （自分的に）新しい事にチャレンジしたい
- AIは違うなぁ
- 多くはないが、募集要項でアルゴリズム関連について記載がある事がある
- 自分はアルゴリズム系は真面目に勉強してきてないのであまりできない
- 採用面接でネタにされる事はありますよね
- 実際に仕事でどれくらい使うかは置いておいて、、、、
- AIでできる事がどんどん増えている事に対する危機感
- 人間に最後に残るのは判断する事だと思っている
- 判断するためには、我が事として知っている、体験した事があるというのは強みになる
- 人間に最後に残るのは判断する事だと思っている
上記より、アルゴリズムに対して苦手意識がないくらいには勉強しようと思った。競プロにしたのは、自分の理解度を客観的に把握しやすいので。
daisuke-fukudaどのサービスを使うか
daisuke-fukuda国内だとAtCoderが人気ありそうだが
daisuke-fukuda
まあ色々ありそうだが、特にこだわりは無いのでAtCoderで。
daisuke-fukudaどこまで目指すのか
daisuke-fukuda- 苦手意識が無いレベル
- 採用面接で困らないレベル
- web系がメインである事は変わらないので、ごりごり業務で使うというイメージでは無い
- まあこれくらいはエンジニアとして常識ですよね、くらい
daisuke-fukuda
緑あれば大抵の企業でアルゴリズム力は十分。AtCoder的には決して上位ではないが、他社評価サイトなら最高評価。水色だと基礎的なアルゴリズム処理能力については疑いのないレベル。
ここらへんと思われる。緑 or 水色。
daisuke-fukuda緑
if、forはもちろん、それを組み合わせて2次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。
簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。
なんとなくイメージできる。ちょっと練習すればできそう。
水色
計算量に関する感覚が体に染みついており、複雑な処理でも苦もなく実装出来る
深さ優先探索や幅優先探索、順列の全列挙やパターンの全列挙などができる。そこから動的計画法やメモ化再帰などの計算量改善につなげることも多少出来る。
貪欲・DP・しゃくとり法・二分探索などの計算量を改善するテクニックをある程度使い分けることが出来る。
累積和やUnionFind(競プロ外ではDisjoint Set)などのデータ構造を使いこなすことが出来る。
ダイクストラ法やワーシャルフロイド法、クラスカル法などの、基本的なグラフアルゴリズムが扱える。木構造やグラフ構造に対して適切に処理を行うことが出来る。
一定以上の数学に関する素養がある。素数などの性質や、それを利用した素数判定や列挙、約数の列挙等、最小公倍数や最大公約数、組み合わせの計算など、競プロにありがちな典型数学問題に対処できる。
何を言っているかわからない。多分難しすぎる。
daisuke-fukuda募集要項系
atCodeのサイトなので、あえてアルゴリズムに強い人を探そうしている会社もありそうでピンキリ。
ざっと眺めた感じ
- 茶色
- エンジニアとして最低限のスキル
- 業務未経験だけどエンジニアとしての素養あり
- 緑
- アルゴリズム多少わかる（チョットワカルではない）
- 水色
- アルゴリズム好き、得意
- それ以上
- アルゴリズムチョットワカル
くらいの印象。
webエンジニアなら茶色でもええやろとも思えるが、さすがに業務経験は積んできているのでもう少しやりたい
daisuke-fukudaというわけで、茶色を目指す。
楽しかったら水色を目指すかもしれないが、今は茶色でOK
daisuke-fukudaいつやるか
daisuke-fukuda
コンテストにはたくさん参加しないと、Ratingがあがらない。定期的に参加し続ける必要がある。
daisuke-fukuda
AtCoder Beginner Contest というのが最初に参加するものだと思われる。
目安は土曜日夜9時から。
というわけで、少なくとも土曜日の夜をできるだけ毎週空けないといけない。大変だぁ。
daisuke-fukudaとりあえず土曜日の夜はスケジュールを抑えておく。
土曜日の夜って、バンド関連の予定や家の予定が入ったりするんだけどなぁ、、、みんなどうやって両立させているんだろうか
daisuke-fukuda練習どうするか。
この手のものは、時間ができたらやろうだと一生やらないので、毎日やる事にする。
どうやら過去問を解いたりするのが良いらしいので、一日一問をノルマとしてやっていく。時間足りなかったりしたらまた考える。
daisuke-fukuda自分は本が好きなので、書籍を購入した。まずはこれからやってみる
daisuke-fukuda言語何にする
daisuke-fukuda
daisuke-fukuda一般的には、C++、pythonがおすすめっぽい。
C++は全然やったことない、Pythonはたまーに書くけど本格的にはやった事ない。ので、今までの経験的にはどっちも微妙。
本格的にやるならどちらかが良さそうだが、言語が体に染み込んでいなくて脳みそのリソース取られるのが嫌なので、慣れてるやつにしたい。
というわけで、TypeScriptかなぁ、、、競技プログラミング的にはマイナーっぽそうだけど、、、
やってみたきつかったらまた考える。
daisuke-fukuda環境構築
daisuke-fukuda何はともあれユーザー登録
daisuke-fukudaチュートリアル
daisuke-fukudatypeScriptのローカル環境作る
バージョンは合わせておこう
daisuke-fukudanodenvが既に入ってたので18.16.1を入れる
$ nodenv install 18.16.1
$ nodenv local 18.16.1
$ node --version
v18.16.1
typescript
daisuke-fukudaJetBrain系を使ってるので、debug方法の設定をする
tsファイル作成して、Debugで実行できた事を確認。
daisuke-fukudaこちらを参考にざっとチートシート作成。
速度優先の普段見慣れない書き方も多いので、適宜調整。
daisuke-fukudaチュートリアル
daisuke-fukuda
何も考えずにやると、Copilotが答えを書いてしまう。練習にならないので、copilotは切る。
daisuke-fukudaあと、標準入力を受け付けてテストをローカルでやりたい（AtCoderの画面でやると遅いので、最終確認のみにしたい）
PHPStormだとよくわからんのでコンソールで
./node_modules/.bin/ts-node src/practice_1/index.ts
Control + D で終了
daisuke-fukuda
daisuke-fukuda第1回
daisuke-fukuda
CはchatGPTを使った。規約確認済
https://info.atcoder.jp/entry/llm-abc-rules-ja?_gl=1o2fvle_gaMTI5MzUyNTUzNS4xNzI3NTk2ODMx_ga_RC512FD18N*MTcyODEyOTU4OC41LjEuMTcyODEzNTY4Ny4wLjAuMA..
DもchatGPT使いつつ、大体プログラムはできたかな〜とういうところまではできたが、結果がInfinityになってdebug中に終了。
a, b は文法知っていて、標準入力/標準出力のお作法がわかればとけるので良いとして、
c、dはこういうデータを作れば良い、こういう流れで探せばよいというのはわかったので、、chatGPTに指示出しはできるし、読めばコードもだいたい分かる。
が、そらで書くことは練習しないと難しい。普段こういうプログラムを書いていないのだ、、、
daisuke-fukuda- 提出時に対象の問題間違え
- コピペミス
でCE、WAになったのでもったいなかった。まあここらへんは慣れれば解決すると思われる。
daisuke-fukuda最初はatCoderのコードテストで実行していたが、遅すぎるので途中でローカルデバッグに変えた。セットアップしておいて良かった。
daisuke-fukudachatGPT使いつつとけたとは言え、これではエンジニア同士で会話できるレベルでは無いので、先は長そうだ。
まずはCを安定してとける（そらで書ける）ようになろう
daisuke-fukuda解説動画
B問題は番兵を使う方法がある。
末尾に、あり得ない文字を追加しちゃう。なるほどー
daisuke-fukudajsだと、functionの中じゃないとreturnできなかったので、テンプレ更新しておく
daisuke-fukudaC問題
今回はnit全探索が使える。二進数でやる
なるほどー
daisuke-fukudaD問題
next_permitation
daisuke-fukudaテンプレ整備
daisuke-fukudaB問題
番兵法
daisuke-fukudajsで2進数を扱う 2進数を表現するには、0b で始める
toStringの引数でX進数を指定できる（当然文字列で返ってくるので、debug用途以外では使わなさそうだが）
> (10).toString(2)
'1010'
ビット論理積
左シフト
右シフト
よって、解答例のC++と同じノリで書くことができる。
daisuke-fukudaC問題の再帰で書く方法
こっちの方が汎用的なので、この機会に覚える。
daisuke-fukudachatGPTに聞いた。こういうイメージらしい。
(pos=0, a=0, b=0)
/ \
(pos=1, a=k[0], b=0) (pos=1, a=0, b=k[0])
/ \ / \
(pos=2, a=k[0]+k[1], b=0) (pos=2, a=k[0], b=k[1]) (pos=2, a=0, b=k[0]+k[1])
/ \ / \ / \
...
DFS（深さ優先探索）の概要理解
今回の問題だと、
- treeの深さがpos（今どの部署を計算しようとしているのか）
- 各nodeからは、グループA or グループB の二分岐になる
- 末端のnode（= posが最後まで行ったら）でグループへ割り振り完了
- 末端のnode同士で結果を比較する
ということをやれば良い。
posが増えたときはグループごとに人数をincrement、逆にposが減った時には人数を減らす処理をしてあげる必要がある。
daisuke-fukuda
daisuke-fukuda二進数のN桁目を取得する方法
1. 右シフトして1桁目を取得
num >> (n - 1 ) して、%2するか &1
> (0b1101 >> (4-1) ) & 1
1
> (0b1101 >> (3-1) ) & 1
1
> (0b1101 >> (2-1) ) & 1
0
> (0b1101 >> (1-1) ) & 1
1
> (0b1101 >> (4-1) ) % 2
1
> (0b1101 >> (3-1) ) % 2
1
> (0b1101 >> (2-1) ) % 2
0
> (0b1101 >> (1-1) ) % 2
1
2. ビットマスク
N桁目だけ1で他は0の二進数は、2 ** (N-1) で表せる。
Nが3なら、10進数の4、二進数の100
これと、対象の二進数とビット演算（積)をとれば、その桁が1かどうか判定できる（N桁目以外はビットマスクが0なので、論理積も絶対に0になる。
> 0b1101 & (2 ** (4-1))
8
> 0b1101 & (2 ** (3-1))
4
> 0b1101 & (2 ** (2-1))
0
3. 文字列
二進数を文字列にして、N文字目（右から数える）で取得
> (0b1101).toString(2).substr(-1, 1)
'1'
> (0b1101).toString(2).substr(-2, 1)
'0'
> (0b1101).toString(2).substr(-3, 1)
'1'
> (0b1101).toString(2).substr(-4, 1)
'1'
3が人間には直感的だが、文字列操作なので1, 2と比べるとパフォーマンスは悪い。
というわけで、1になれると良さそう。
daisuke-fukuda// ■2進数N桁目の値を取得する
function getNthBit(target: number, n: number): number {
return (target >> (n-1)) & 1
}
D問題
daisuke-fukuda順列のループ
jsにはnext_permutation が無いので、自前で作る。
ようはこんな感じでdfsすれば良い
daisuke-fukuda順列のfunction作成
配列の破壊的変更があってわかりにくい、、、
depthはLenthから始まってdecrementしていくサンプルが多かったが、わかりにくいので0始まりとした。
daisuke-fukuda作成した順列に対して、bit全探索（照射のスタートが2通りなので）を実行すれば、全組み合わせの計算ができる。bit全探索はC問題と同じ。
あとは時間計算を入れれば良い。
daisuke-fukuda
復習終わり
daisuke-fukudaabc375
daisuke-fukudaAとBはAC
CとDは正解は出るけど、TLE。
前回は全網羅で良かったが、今回は計算量をいい感じにするアルゴリズムが必要だった。
AとBが前回よりスムーズにできたからか、パフォーマンスは前回より良かった。
daisuke-fukudaA
雑に
for (let i = 0; i < s.length; i++) {
でループしたが、i < s.length - 2 で良かった。
daisuke-fukudaB
最初と最後の原点は、配列に追加する方法でも良い。お好みで。
daisuke-fukudaC
問題には明記されてないが、90度回転させているというのが指示。（これがわかっていなかった。）
↑のコードだと、Nを使った3重ループなので、O(N^3）になっている。
回転
座標の右から、あるいは下からというのは、N-x+1（+1は座標が1始まりの場合）という書き方がよく出てくる。（知らなかったが、、、言われてみればまあそう）
この事から、マス (y,N+1−x) の色をマス (x,y) というのが90度回転を表している事が、注意深く読めばわからなくも無い。
また、愚直に書いたプログラムをchatGPTに投げる事でも90度回転している事は教えてくれた。
さらに、問題タイトルの Spiral Rotation もヒントになっている。
結局何を指示しているのか
i 以上 N+1−i 以下 整数 x,y について 〜を行う とあるが、N+1−i は前述の通り、右（あるいは下）からの座標を示している。
- iが1
- xは一番左から一番右の範囲（つまり全部）
- yは一番上から一番下の範囲（つまり全部）
- iが2
- xは左から2番目から、右から2番目の範囲
- yは上から2番目から、下から2番目の範囲
- iが3
- xは左から3番目から、右から3番目の範囲
- yは上から3番目から、下から3番目の範囲
という事で、範囲をせばめながら、〜を行う事を指示している。
そして、行う事は前述の通り90度回転。
つまり、
この図でいうと、1の枠内全部を90度回転、次の2の枠内全部を90度回転… という指示になっている。
（実装時にdebugログを愚直に吐いていたので、注意深く観察すれば上記の挙動は解析する事が可能だったはず、、、）
計算量を工夫する
ここまでわかっても、愚直にプログラムを書いたのではO(N^3）でTLEなので、アルゴリズムの工夫が必要になる。
枠をせばめながらループするという指示に注目し、枠ごとの挙動を見直すと、
一番外側の枠は90度回転、2番目の枠は180度回転、3番目の枠は270度回転、4番目の枠は360度回転=回転無し、5番目の枠は450度回転=90度回転…
という結果になる
上記より、座標が何番目の枠になるかを取得すれば、自ずと何度回転すればよいのかがわかる。これは、座標のみで計算できるので、座標iとjの二重ループで済む。つまり、O(N^2）で済む。
（解説を見て、言われればなるほどだが、、、、）
後はこれを実装すればOK。
daisuke-fukuda実装
daisuke-fukudaD問題
i,j,kの三重ループで解くと計算量がO(N^3）になって、TLEになってしまうのはC問題と同じ。何かアルゴリズムを工夫しないといけない。
Si , Sj , Sk の3文字が回分という事は、Si == Sj である事までは気がつく事ができたが、そこから先のアルゴリズムが浮かばなかった。
（iのループが間違ってる）
正解（の1つ）は、英大文字からなる文字列 S より、対象の文字が26文字しか無いことに注目する。
Si と Sk の文字をMapで持っておいて、その組み合わせをカウントしていけば良い。適切なデータ構造に気がつけるか、という問題。
iを1から動かしていく時、最初にSkのMapを作る時にO(N)、iのループの中で、26文字それぞれでカウントすれば良いので、O(N26)
合計すると、O(N + N26) なので、O(2N) で済む。
あとは実装すればOK。
daisuke-fukuda
daisuke-fukudaE問題
450点だから難しそう、、、と思っていたが、ざっと解説聞いた限りだとDP（動的計画法）ができれば解けそうだった。
DPはそのうちやる、、、
daisuke-fukudaabc376
daisuke-fukuda
a,b,cは解けた。dは問題の意味すらわからず
daisuke-fukudaa問題
for分で回すだけなので特に無し
daisuke-fukudab問題
右回りか左回りの2通りしかないので、実際indexをずらしながら動かしてみていけるか、という方法でゴリ押しした。
計算量が心配だったが、今回の成約では問題なかった。
解説されていた方法としては、まずは円周をプログラムで扱いやすいように直線として解釈する。
そうすると、
- 起点（from）
- 目標（to）
- 動かさない方の手（通ってはいけない点）x
の位置関係のパターンとして整理できる。
6パターンなのでこれでゴリ押ししても良いが、欲しいデータはfromとtoの間の距離なので、fromとtoを交換しても成り立つ。よって3パターン。
距離の計算は、
fromとtoの間にxが無いパターンだとto-from 、
xがあるパターンだと n（要素数） - ( t- s) で計算できる
というわけでプログラムだとこう
ちなみに array[index % 要素数] で、循環する場合の配列座標を出せるので便利との事。
daisuke-fukudac問題
こちらの解説の、貪欲法で解くことができた。
動画解説では2分探索で説明していたので、こちらのバージョンも実装してみる。
TSの2分探索はざっとこんな感じだが、
今回の問題だと、OKとNGの境目を出したいので、ちょっと変わる。
jsのsortは何も指定しないと文字列sortなので注意。
daisuke-fukudaD問題
まず問題の意味が全然わからなかった。動画を見て理解。
この手のものは、BFS（幅優先探索）で解くとよいらしい。
幅優先探索についてはそのうちやる
daisuke-fukudaabc377
abcは解けた。Dは問題の意味があまりわからず。
何回かやって、これくらいが今の実力値として安定してる。
daisuke-fukudaA問題
3文字なので6パターン列挙でOK。
sortしてABCか判定する場合、jsで文字列をsortするには一旦配列にする必要がある
string.split("").sort().join("");
B問題
8*8マスしかないので、ループでゴリ押しでOK。
ちなみに、ある値で初期化された配列をjsでかっこよく書くのは意外と難しい。 Objectがカラムとハマったりしそうなので、普通にfor文でゴリ押しする事にする。
daisuke-fukudaC問題
Setを使って判定するという考え方はすんなり出来たが、プログラムでハマった。
Nが10^9 で、N*N を計算する時に桁溢れしてしまった => BigInt使う
SetのkeyをObjectにしたが、同値判定ではなくで同参照で判定されてしまう => keyをStringにして扱った
Customクラスを作成してhash関数を自作する方がきれいだが、競プロではめんどすぎるのでざっとstring化しちゃった方が早そう。
daisuke-fukudaD問題
[L,R]は閉区間。（L、Rを含む） ← 今回はこっち。
(L,R)は開区間。(L、Rを含まない）
尺取法で解く。