実績解除：AtCoder黄色になった
黄タッチです。２度目。
競技プログラミングは自分のコンディションをどう調整するかで何百位も順位がズレる競技でした。それに気付くのに1年かかった。
前回の黄色タッチは翌日のARCですぐさま落ちたので記事を書く隙がありませんでした。今回は何週間かは黄色でいられそうなので色変記事を書いています。
自己紹介
大学４年生になりました。電子情報系の何かを専攻している大学生です。中学生の頃にhspに触れていました。中学・高校は動画編集とかをやっていました。ちゃんとプログラミングを始めたのは大学でPythonに触れてからです。
灰・茶・緑・水色・青になるまでにやったこと
水difficulty埋め、青difficulty埋めとかEDPC埋めをして、なんやかんやで青になった覚えがあります。
黄色になるまでにやったこと
黄difficultyは半分くらい埋めました。難しいから全部埋めるのは大変。メンタルとパフォーマンスの関係を意識すること、負けない立ち回りを覚えることをやっていたと思います。
精進について
青入りから比べて700ACほど増えているらしいです。RPSはほぼ倍に。
Streakはがんばって続けていた頃もありましたが今はあんまり意識していません。
1年前くらいからちょっと競プロ熱が引いてきていて、1ヶ月で100ACしていた頃に比べると全然精進していません。たまに精進するときは落とせない問題（水〜青difficulty）と、解きたい問題（黄〜difficulty）の両方を練習していました。黄色になることを考えると、水〜青レベルの問題に時間かかってしまうのは致命的なのでそこを押さえにかかったというところがあります。あと単純にそこまで難しくないから解いてて楽しいっていうこと......
入青以降新しく覚えたアルゴリズムについて
ほとんど変わっていないはずです。
・Suffix Array（あまり使っていない）
・LCP Array（あまり使っていない）
・最大流（大人気アルゴリズム）
・最小費用流（むずかしいね）
・遅延評価セグメント木（何が載るのかあまり理解していない）
・FMT（重い。これが出てくる問題だいたい実装が重い。）
・高速アダマール変換（なにこれ）
・Sparse Table（セグ木だと定数倍がきついときに使う）
・ Trie（使ってない）
・エラトステネスの篩（高速素因数分解付き）
メンタルとパフォーマンスの関係
自分の悪癖の１つに反芻思考というのがあって、自分の中の心配事を隙さえあれば思い出してエネルギーやメモリを消耗するものです。
心配事があるときに頭脳競技に挑むと頭にもやがかかったような気分になり何も見えず、焦り、ひどいパフォーマンスを出してレートが落ちるということが多々ありました。見返してみると、このようなとき平常時より２色か３色分パフォーマンスが落ちています。
これに気付いてからはコンテスト前までに課題やらバイトやらの面倒事は極力済ませておくようになり、いくらかパフォーマンスが安定するようになりました。
メンタルについて考える中で、心配事が次文のパフォーマンスにどの程度影響するかを手軽に診断できるテストを考えました。経験則なのでエビデンスはないです。
ちょっとやってみますか？
心配事テスト
期限のある仕事や、用事、課題や研究などについて思い出してみましょう。
いくつあるでしょうか。ひとつひとつ思い出します。
期限や用事の詳細について思い出してみてください。
思い出すのにかかった時間が短いほど、脳の中で思い出しやすい位置にその記憶が置かれていることになります。これが頭脳競技においての思考を妨害すると考えます。
・瞬時に思い出した。（影響 大）
・１〜２秒かけて思い出した。（影響 中）
・なかなか思い出せない（影響 低）
影響 大のものを自分から遠ざける
瞬時に思い出せてしまったものの影響を抑える方法についてもいくらか考えたことがあります。基本的には外部メモリを使うのが良いです。以下は例です。
・ポストイットなどに心配事や用事を書いておき、「ここに書いておいた」ということだけ覚えておく
・心配事や用事の数だけを覚えておき、必要になったら数から内容を引き出して思い出すようにする
また、マインドフルネスなどの瞑想技法も有効です。マインドフルネスは事象に対して評価をしないので、ストレスの大きい反芻思考の影響を抑える効果があると言われています。
どんな記事にも終わりはある
自分の中のもう1人をおだてて問題を解かせる。
AtCoder Beginner Contest 213 反省
？
結果を鑑みて
1500 26:25
241位。Fが解けそうで解けず、とは言え早解きだったのでレートが上がって黄色になった。
A - Bitwise Exclusive Or
A xor B をやる。A問題にしてはやや難しめらしい。
B - Booby Prize
ブービー賞ってそういうのなんだ〜って言いながら書いてた。ブービー賞に関する知識がなかったので直感的な正当性証明ができず、少し見直しに時間をかけて提出。
C - Reorder Cards
坐圧っぽいので、坐圧しようとしたが１次元の坐圧ライブラリしか持っていない。
直観的に縦横は分離して１次元が２つという状況に置き直して良いということがわかったが、証明はなんだか生えなかったので順位表を見た。爆速で通している人たちがいたので恐らく合っているだろうと思って提出。
D - Takahashi Tour
木のDFSやるだけ系か、と思った。経路長がどうもそんなに長くないっぽい？（経路をそのまま出力させることから）というところからサンプルを見ながら考えてみると、オイラーツアーそのものだった。
オイラーツアーは非再帰でかけるのでてきとうに書いて通した。それなりの順位だったと思う。
E - Stronger Takahashi
まあ最短経路系の問題だろうと思った。パンチは2*2マスを縮約して道1マスにする行為かなと思った。いろいろ考えてたら、パンチを2*2マスの自由なマスにワープする操作と捉え直すことができた。この操作ができるかどうかは、一回訪れたマスに２度訪れることが適切かどうかを考えると良さそうで、それを思うとパンチをワープと読み替えることが肯定できる。そうするとワープは今いるマスからチェビシェフ距離2以下のマスから四隅がかけた位置に移動できると言えることになる。定数倍が気になるが、最大ケースを試しているとうまくいくのでOK。
この時点で100位くらい。落ち着いてFに進んだ。
F - Common Prefixes
Suffix Array感、LCP配列感がある。
考えると、LCP配列でmin(lcp[0], lcp[1], ..., lcp[i]) + min(lcp[1], lcp[2], ..., lcp[i]) + ... + min(lcp[i], lcp[i + 1], ... lcp[N - 1] + N - i が答え。これを求めるのに大変難儀した。
これは遅延評価セグメント木で解けるのでは？と１時間くらいガチャガチャやっていたが、どうもchmin更新とRSQが同時にできるのはSegment Tree Beatsらしい。モノイドチェックの必要性を感じた......
その後BITで寄与を管理しながら計算しようと思ったがうまくいかず終了。
これはどうも優先度付きキューのスタック芸みたいなので解けるっぽい。こういうの一回こどふぉで見たんだよなあ......
G - Connectivity 2
あんまりみてない。
H - Stroll
あんまりみてない。
総括
順位表見ながら動くいつものムーブをしていたので、今回は飛ばさずいくことになった。ムーブ自体は最近安定している。あとで気付いたことだが、自分のSAはちょっと遅いので整備しなきゃなーと思う。
G, HはどうもARCの中ボス難易度くらいの問題っぽいのでここいらの典型はしっかり押さえていきたい。adhocはABCには出にくそうなのでおいおいその対策もしようね。
Beginner Contest？知らない子ですね。
高域知能検査CAMS第11回を受けた ポエム
話題の(言うほど話題ではない)IQテストを受けてきました。
自己理解について書いたつもりですが、マジでキモいポエムになっていると思うので、読むなら自己責任において行って欲しいです。
結果
これは一体、、、？ pic.twitter.com/HcwKcYjK9p
— woLgniK (@nadekuc) 2021年7月31日
IQ 137.5 (sd 15) だそうです。
たぶん正規分布なので計算すると上位0.6%くらいらしい。
感想
問題について
知っていたことですが、CAMSは行列推理だけでした。検査開始から10分くらいは本当に何もわからなかったけれど、ぐっと睨んでいると何かが見えてきたりこなかったりして解けるというものでした。問題は難しいものもそうでないものもあり半分くらいしか自信を持って解けなかったですが、多種多様なトリックが使われており面白かったです。
慣れや練習のできる問題群だとは思いました。トリックの引き出しのバイアスをテストに合わせることが可能そう。CAMS自体は何回かやるとスコアが上がるものらしいので。（だいたいのテストはそうだとおもうが）
自己理解について
IQが20違うと話が通じなくなるという俗説がある。これは興味分野と知識の分布のバイアスのズレによるものだろうと解釈できる。IQと興味分野・知識の傾向には因果関係があるとは言わないが恐らくは相関関係があると思われるから。
今回はただ1回の検査であってしかも行列推理のみからなっていたことを考えると、自分が必ずしも高知能だから話が通じないのだとは言えないが、思い返せば心当たりは結構ある。そもそも競技プログラミングなんてものをやっているのは奇人・変人ばかりだし、twitterなんてやってるのも精神異常者とオタクだけなわけだし、IQテストなんてのをわざわざ受けに行くのも......
理系学生のご多分に漏れず、自分のコミュニケーション能力に難があるのは承知しているが、今回の結果はそれを良くも悪くも肯定するものになった。きっと自分は無意識下でよりコミュニケーションを諦めやすくなると思う。
人生の中で出会い、友人と呼べるようになる人間は多くて1000人程度だと思う。ロビン・ダンバーによれば、人数として友人関係を同時に維持できるのは100〜200人までらしい。話が合うかどうかを(自分のIQ-10)以上のIQを持つかとして定義した場合、その存在割合は3%であることを思うとあまりにも人間関係の構築が厳しい。これほぼ家族しかいないじゃん。
首くくることにならないといいけど！
まとめ
- IQ 137.5 (sd 15)
- ただの変人から自分のことを高知能だと思っている変人になった
- コミュニケーションが無理
今気付いたのですが、どうも自分は読者を自分自身に設定している文とそれ以外にも設定している文とでは文体が異なるようですね。（前者は〜だ、〜である調で、後者は〜です、〜ます調になっているように思います。）
AtCoder Beginner Contest 212 反省
8問制ABCだ！後ろに黄橙の問題が増えました（？）
結果を鑑みて
2100 96:11
Eまでそれなりのペースだったはずだが、周りが結構速くて相対的にはそんなに速くなかった。G通らなかったら冷えてたかも！ぴえ〜
A - Alloy
if文をせこせこ書く。
B - Weak Password
ふつうにやる。コーナーがないかちゃんと調べた。
C - Min Difference
AとBを出身の配列がわかるようにして混ぜて、ソートする。
そうすると隣り合った別配列どうしの2要素の差の最小値が答えとみて問題がない。
最近、隣り合う要素・頂点の関係を利用した数え上げ法が少し見えるようになってきたのでここまではすぐに見えた。
見えたものの、証明してみても抜けがあるかもしれないと少し怖かったので丁寧にサンプルを合わせてから通した。
このとき、サンプル合わせに加えて順位表も見て情報を得ようとしてみたが、今回はあまり参考にならなかった。
D - Querying Multiset
クエリ先読み系かなと直感したが、ちゃんと読むとただの優先度付きキューの問題だった。
解けたので順位表を見ると100位ちょっとだった。さっさと解いて行った気がしていたので100位は切れると思っていたが......
E - Safety Journey
少し難儀した。愚直に遷移させてdpすると重すぎるし、ダブリングでもなさそう。
ちゃんと考えると余事象的に遷移を扱えばよいだけだった。全体の方針としては普通の数え上げで、途中途中の部分問題が余事象数え上げだったりすると見えるのに時間がかかる。
この時点で150位ちょっと？まあレートは落ちないだろうと思って安心して進むことができた。
なお、Eを解いた時点でFは問題だけ読んであった。
F - Greedy Takahashi
なんかDAGだったらDAG上ダブリングだな〜とか思っていた。なんだかよくわからんし順位表見ても全然解かれてない上にGの方が解かれていたのでGを見に行った。
G - Power Pair
かなり難儀した。最初はPの約数列挙をしようとしていた。（Pは素数です！）
約数列挙して、それぞれの循環の長さとかを計算したりして約数系包除しようとしていた。
だいたい正しいのだが、このときは x^n mod PはxとPが互いに素なら常に循環の長さ(位数)がP-1になると思っていた。
いろいろ実験するとそうでないことがわかって、位数という語を知り、位数にP-1の約数しか現れないことを悟った。P-1がフェルマー小定理と関わっている数字であることもわかっていた。
ここからさらに難航して残り20分になろうというあたりで原始根という語を知った。原始根を利用して「なぜ位数がP-1の倍数になるのか」に説明をつけられる気がして実験してみると、やっと残り10分というところで法則を見つけることができた。
なんとかこのままACできた。
公式解説にはさらっと原始根を利用したとんでもない式変形が載っているが、見つけた法則というのはつまるところこれだった。ひょっとしてこれも典型考察なのか......
H - Nim Counting
ちらっと見て包除かなあとか思ったけどKの値が奇妙すぎて？？？となった。すぐ見るのやめた。
総括
F飛ばしてGに行ったムーブだけでレートを手に入れたようなもの。結構ムーブはよかった。高度典型の知識不足がやはり目立つ。ARC・AGCでの勝率の低さはそこにありそう。黄〜橙埋めをやろうね。
そろそろ黄色に戻れるかな？（戻る、といっても黄色だったのはマジで1日だけだしほぼ青の住人......）
AtCoder Beginner Contest 211 反省
今月の橙パフォです......
結果を鑑みて
2100 78:13
70位となった。Eまでそれなりに良いペースで解き続け、Fの重実装をバグらせず通すことができた。よかった......。直前のバチャではぐちゃぐちゃだった。
A - Blood Pressure
血圧。こんなのあるんだ〜という感じ。
見るからにコーナーケースなしなのでふつうにやった。
B - Cycle Hit
setの比較をした。
C - chokudai
耳dpをする。ほぼこれと同じ問題が典型90で出ていたはず。
とはいえこのレベルのdp数え上げもABC-Cに置かれるようになったか。
いつもならこのへんで順位表を見ているが、今回は見ていない。
D - Number of Shortest paths
BFSの遷移に場合の数を持たせた。第一感でこの解法を思いつくことができた。証明はしていないが、確かBFSは visited だけ管理できれば暫定距離の比較なしに距離更新をしていいというのがあったはずで、この更新順にのっとれば場合の数も遷移できよう......くらいに思っていた。
証明: AC
このあたりで順位表を見るとだいたい60位くらいで、安心して進むことができた。
E - Red Polyomino
第一感として、上からbitDPしていくというのがあった。しかしながら、連結性の情報をどう持たせるかが難儀だった。
始点を適当に決めてDFSするような形で構築を試みると、各状態から遷移は3方向しかないから実は愚直が答えじゃん！（嘘）というひらめきをして構築のコードを書いた。
ぎっちり書いた後、本当は各状態からの遷移方向は3通りどころではないということにサンプルを見て気づいた。仕方がないので枝刈りしながら遷移方向を増やすと、案外高速だった。
（本当はサンプルにヒントがあって、最大ケースの答えは60000通りしかない。枝刈りをちゃんとやれば高速）
これを通した時点で50位くらいだったかも。結構余裕を持って進むことができた。
F - Rectilinear Polygons
サンプルを見ないとなかなかイメージが難しかったりして、矩形に分解しまくってimosとかか？などと思ったりした。imosになる気がしたのはなんとなく半開区間っぽいクエリだったから。
あながち間違いではなくて、結果的にはBITを用いたインラインなimosだった。
各頂点が領域の始端か終端かをイベントソート+BITなどで判定できる。具体的には、y座標の昇順で見てその中でまたx座標の昇順に見て、頂点がすでに+1領域に含まれるならその頂点は-1とする。そうでないなら+1、というふうに。
頂点の寄与が+1か-1かがまるで偶奇のようにすぱっと決まって、それでimosができるのがなかなかきれいだった。バグらせなくてよかった〜
総括
とりあえず研究に人生を破壊された結果溶かした100近くのレートをほとんど回収することができた。よかった。今回のムーブはまあそれなり。勘が良かったのでムーブに左右されるような感じにはならなかった。
AtCoder Beginner Contest 210 反省
久しぶりにちゃんと出た。いろいろ忙しかったので......(と言いながらこの前tourist出しして-60した！！！)
結果を鑑みて
1500(5) 119:40
509位となった。Dまでは良かったが、Eで解法ガチャをミスって破滅してしまった。何とか通したがえらいペナつけてしまった。
A - Cabbages
キャベツやさん！？
入力が多くて嫌だけど普通にif文で解けた。
B - Bouzu Mekuri
中学生のころ、教室にあった百人一首のやつで坊主めくりしてた......
前から見るだけ。
C - Colorful Candies
エ、区間種類数クエリっていつぞやのF問題で出なかったか？と思ってびっくりしたが、固定区間長なのでふつうにやるだけだった。
この時点での順位はまあ良好だった。
D - National Railway
なんとなくMSTぽいなと思ったが、全点被覆ではないのでただの最短経路だった。
左右で累積max、それを上下に累積maxしてやれば良いことに気付いた。実装自体はしんどかったが似た処理を4回書いただけだったのでバグらず通せた。
この時点で150位くらいで、焦らず進むことができた。
E - Ring MST
最初、これをグラフではなく整数論の問題だと直観した。これは半分当たりで半分ハズレだった。整数論だと考えると自然とgcdを利用する方法が生えるが、ここで誤解があった。
N=6のときにa=2の辺は0-2-4で2本しか張れないと思っていて、この解法だと約数系包除のような面倒くさいことをして計算しなければならなくなる。散々ペナをつけ、残り15分というところで過ちに気付いた。
グラフの問題として考えると、MST構築の貪欲性が鍵となる。常にコストの小さい辺を繋げれば良いので、コスト最小の辺でN - gcd(N, a)本繋ぐと問題が縮小してN = gcd(N, a)のときの同様の問題を解けば良くなる。再帰でACした。
かなり暗礁に乗り上げたような感じだったが、これはちょっと見た瞬間に解法が生えてほしかった...... 約数+グラフ系の問題は約数包除もそうだけどあまり得意じゃないかも。類題をあまり解いてこなかったせいか。
F - Coprime Solitaire
2-SATっぽいとは思ったが、辺の数が多いのでどうしたものかと思っていたらコンテストが終わった。
総括
復習が結構たまってきた。夏休みに入れば時間もあると思うので（研究はしない！w）しっかりとレートを戻していきたい。まずは鈍った勘を何とかしよう！
AtCoder Beginner Contest 207 反省
バカみたいな難易度配置のコンテストだったので一応温まったっぽい。
今日はちょっと頭ぽわぽわ気味だった。実装・立ち回りは今月中では一番悪いかもしれない。
結果を鑑みて
1100 58:15
295位となった。Cで手こずり、Dを捨てたり捨てきれなかったりして時間を浪費、脳死添字バグでEを解くのに時間をかけ、実装力のなさでFを落とした。奇跡的に冷えずに済んだ感じ。先週よりは忙しくないはずだが、実装・ムーブのミスが多く、危うく冷えるところだった。
A - Repression
ソートした。
B - Hydrate
可能かどうかを場合分け→二分探索？と踏んだ。
可能かどうかの条件が面倒そう、漏れが出そうに見えて犯罪二分探索するかちゃんと条件考えるか逡巡した。この時間がまず無駄だった。
結局、犯罪二分探索をした。上界を10^100で始めて、結果が10^100なら-1、それ以外になるなら二分探索の結果を出力することとした。どうせ答えは大きくともlonglongに収まるだろうと思うので、これで十分である。操作回数の自明な上界を見積もろうともしたが、これもなんだか面倒に感じてやめた。
今回は変数が4つあったので直観が働きにくかったのかもしれない。
少し時間かかって次の問題へ進んだ。
C - Many Segments
全部閉区間にしちゃおう！と思って、開区間なら内側へ1だけ縮めるのをして、サンプル1が合わなくて10分首をかしげていた。
よくサンプルの説明を読むと、これでは不十分なことに気付いて全体10倍して同様の処理を行なって通した。
この時点で600位くらいだった気がする。かなしい。
D - Congruence Points
問題読む前に順位表からヤバそうな雰囲気を察して、Eを先に読んだ。
この問題に似ていることを思い出し、平行移動不変量である重心座標系を使おうと思った。そこから何故か線形計算量で解けないかとか考えたり誤差を気にしたりして全然実装しなかった。
N≦100なのだし、「円上 格子点」でググったりもして解けそうなオーラもあったが、Fも解けそうな見た目をしていたためFに挑戦して夢破れてしまった。
E - Mod i
まあ二乗のdpが許されているのでそれをするのだが、遷移先の前計算がないと余計なlogが乗ったりしてまずpython系では通らない。
遷移の前計算はmod i 固定で累積和の剰余が同じ数になるものをまとめることによってできる。ここでsetやsortを使う必要はなく、基数ソートで足りる。もっと言えば、実際にソートする必要はなくて剰余ごとに1つのindexを格納するテーブルさえ持てば実装可能で、これは定数倍も小さい。
ここまで進んだはいいが、そのあとのdpで添字ミス（最後に空部分列を追加することを容認してしまっていた。）に気付かずに首傾げてえらい時間経ってしまった。
通した後順位を見てみると200位くらいで、DもFもパッと見取れそうな見た目していたので両方考えつつF重視で行こうとした。
F - Tree Patrolling
次数だけみればいいのかと思ったが、包除原理の計算量がでかすぎるので不適。であれば素直に木dpで、制約などからどうせ二乗の木dpだろと思って、三本の二次元dpテーブルをはやせばいいというところまではすぐに辿り着いた。
しかし、遷移が頭の中でぐちゃぐちゃになって結局解けなかった。
総括
復習は今度やることにしたい。今週もなんだかんだコンテスト練習をしていなかったのがムーブに現れてしまった。どこか自分のレートに対して他人事でふわふわした感情のまま取り組んでいたり、Cで手こずった後に明確に焦りを感じたのにも関わらずリフレッシュに時間を使わなかったのもよくなかった。
コンテスト練習をしないとムーブとリカバリーの勘が鈍るっぽい。典型90のおかげか、解法の勘はよかった。いつでも落ち着いて挑めるようになりたいね。
