AtCoder Beginner Contest168に参加しました。
AtCoder記事を全然書けていませんでした。
が、競技自体は今のところ無欠席です。時々冷えつつも順調にレートは上がっています。
今回の結果
強い人は２０回くらいで水色・青色に行っているのがちょっと悔しいですね……
復習
A問題
if文が多くてタイプミスが不安でしたが一発でACです。
B問題
実はちょっと手こずりました。文字列への追加でs.at(i)……を使ってしまってエラーを吐き、？？？となっていました。push_backを使いましょう。しかもタイプミスでWAするという……
C問題
「余弦定理」を使いました。doubleの桁数が不安でしたが、えいやっと提出したら通ってしまった感じ。後から調べてみると10の300乗まで表現できるそうなので、問題文の精度条件に対しては十分余裕がありますね。
D問題
BFSできない……！ でも「これはBFSっぽい」という感覚は得るに至りました。
snukeさんのコードを写経しました。書いてあることはなんとなくわかるぞ、という感じです。研鑽を積みましょう。
E問題
A/Bで管理すればうまく数えられるかな……？ という微かなひらめきはありましたが実装できませんでした。
今後やること
このまま続けて参加していけば、茶色コーダーにはなれそうです。
数ヶ月前からずっと言っていますが、そろそろ典型的なアルゴリズムを抑えていきたい。BFS・DFS・数え上げ、あたりの過去類題を解けるようにしたいと思います。
この手の問題を時間内に安定的に解いて、緑パフォを目指します。
「星を継ぐもの」を読みました。
「星を継ぐもの」を読みました。（※ネタバレをします）
この本を手にとった理由はタイトルがかっこ良かったからです……！
が、面白さのあまり最後まで一気読みでした。私の中で、2020年５月度の買ってよかった小説1位に躍り出ました。
「月で見つかった死体」というキャッチーな出来事に対して、「この人物が死んだのは五万年前」「当時の人間は宇宙船を持っていない」ことや、じゃあ彼は宇宙人なのか、という推定に対して「その生物学的特徴は全く地球人と同じ」など、不可解な状況がどんどん積み上がっていき、ミステリーを読んでいるみたいに興味と好奇心を引き付けられます。
そういった謎に対して、科学技術を駆使して少しずつ迫っていく中盤の展開は、科学に興味のある私にはとても魅力的でした。
死体と一緒に見つかった「日記帳」を解読したり、死体の分析から体の組成、住んでいた場所の特徴を特定したり、ちょっとずつ事実を積み上げていきながら、「なぜ死体がそこにあったのか？」にまつわるストーリーを解明していきます。
「月のクレーターから見つかった物質は核反応によって生成するもの」という事実から「月で核戦争が起こった」ことが明らかになるシーンがちょうど本の半分あたりから来て、ここから一気に物語が加速していく感じがしました。
著者はコンピューターのセールスマンだったそうですが、これが処女作ということでとても驚きです。私も科学技術には関心のあるほうですが、ここまでリアル感を持って（本当に科学考証が正しいのか私は判断できないのですが……）書けるのがとてもうやましいと感じます。
古い小説だと思って読んでいましたが、全然古さを感じません。それどころか現代よりもずっと新しい物語のように思えます。
この本を読んでSF小説への関心がものすごく高まりました。
ちょっと毛色が違いますが、英語の先生におすすめされたこともあって「ニューロマンサー」を読んでみようと思います。
こういう面白い小説を読むと、創作意欲がとても刺激されます。もっと面白い小説を読みたいです……！
「猫の地球儀」を読み返したい気持ちになりました。
「挫折した本」と「読み切った本」
数学と物理の勉強は楽しく、そのおかげでいくらでも外出自粛ができそうです。ライフイベントが停滞しないか心配になるほど。
その中で気づいたことは、私はあまり賢い人間ではなさそう、ということです。いろいろ興味のある本を買ってみたのですが、わからないところ多々あり、読みきれなかった本がたくさんあります。
「これを読んだよ！」という情報は巷にあふれていますが「これは読みきれなかった」という情報は秘匿されがちです。うまくいかなかった研究結果が論文にならないのと同じです。そういう失敗事例こそ、公にして共有してほしいと思っています。
と、いうわけで、私の最近の「挫折した本」と「読み切った本」を書いていきます。
自分の知識レベルがはっきりと現れてしまう恐ろしい記事です……！
挫折した本
「数値流体力学」
部署異動に伴って、流体を取り扱い始めました。仕事をする中で、流体の理解には、かなりマニアックな数値解析やモデリング知識が必要と感じて手に取った本です。
大学で流体を専攻していた同期の「乱流には手を出さない方がいい」という忠告を押し切っての挑戦でしたが、案の定乱流のモデリングでつまづきました。乱流怖い……輸送方程式ってなに……？
もっとわかりやすい副読書を探し中です。
流行りに乗って始めたものの飽きた、という駄目なパターンです。これも５０ページくらいまでで止まっていたかも……確か購入したのは去年でしたでしょうか。
ただ、「事後確率」「事前確率」「メールのソート」について、機械学習の初歩の初歩はぼんやりと頭に残っているので、読んだ意味はあったかなと思います。繰り返し挑戦したい一冊です。
ただ、実利を考えるならKaggleでデータ分析をごりごりやったほうが良さそうなので、手を付けるならそっちからかな、とも思っています（kaggleスタートブックも買って積んでいます）。
「オペレーティングシステム」「Webを支える技術」
有名なGoogleのお医者さんに触発されて買ってしまった本です。あのブログでは、さらっと読みこなしてしまった感じがありますが、初学者にはなかなか頭に入ってきません。
すぐに読み切るのは難しそうなので、目下競プロを楽しくやりながら、きっかけを見つけて再挑戦したいです。
これも５０〜１００ページくらいで止まった記憶があります。そのあたりに「死の谷」的な何かがありそうです。
「大学教養 線形代数」
線形代数はいまだに面白さがよくわかっていません……FFTとかを実装する段になればわかってくるのかも。理工系大学卒で線形代数をよくわかっていないのはお恥ずかしい限りです……ただ、今後数学を勉強していく上で必ず参照したいところが出てくると感じています。手元において繰り返し読んでいきます。
読み切った本
「高校数学でわかる流体力学」
安定のブルーバックスシリーズです。完全流体についての議論は、この本のお陰でかなり自信を持ってわかったと言えるようになりました。
「流れの数値解析入門」
こちらは少々実践的な本。「渦法」のアルゴリズムについて知りたいと思って購入し、実際に圧力場を求めるプログラムを組んでみたりしました。
が、最後までエラーを修正しきれませんでした……実用的なコードを組むためには、知識だけでなく、忍耐力と根気が必要だと痛感しました。
自分の「実装力」の低さを痛感させられ、いろいろ学びのある本でした。何かを作るために必要なのは、何よりもまず強い意思です。
なんとか読めそうな本
「道具としてのフーリエ解析」
直感的なイメージを重視した、とてもわかりやすい本です、この本のお陰で、式を見ながらですがフーリエ級数展開からDFTまでの計算ができるようになりました。
前半の半分でフーリエ級数~DFT・ラプラス変換を、後半では応用編としてFFTを取り扱います。
前半は読み終わったので、これから応用編に取り掛かります。以前競プロで挫折したFFT問題にリベンジできそう。とても読むのが楽しみな本です。
「『集合と位相』をなぜ学ぶのか」
理論としての数学には馴染みがなかったので、その足がかりとなる知識がほしいと購入しました。SNS情報によると、ストーリー仕立てで易しい読み物、とのことで油断していました。実際に読んでみると、定理の証明の議論についていけなかったり、見慣れない定義に戸惑ったりと思うように進みません。
ただ、ゆっくりと読んでいけば十分理解できる内容なので、気長に読んでいこうと思います。
微積の基礎も復習していって、最終的には「無限級数の足し算と積分の入れ替え」や「フーリエ級数の収束」といった議論を丁寧に追えるようにしたいと思っています。
まとめ
あれこれ手を出しましたが、そのうちのひとつだけでもものにするのは大変です。こういう雑多な勉強が許されるのは学生の頃だけだよなあ、とは思いながら、趣味だからとちょこちょこ続けています。
ただ、もしも仕事として役立てるなら、分野を絞って注力しないとどれも中途半端に終わりそうです。もう少し自分の興味を絞りながら、かつ楽しんでできるようなところを模索していきます。ストイックにいくのも良いですが、なによりも続けることが大事かなと思っています。
AtCoder Beginner Contest 161に参加しました。
[今回の戦績]
Rate404の茶パフォ、A〜Cの三完でした。
[所感]
A〜Cについてはかなり安定的に回答ができるようになってきました。ようやく、D問題からのアルゴリズム知識と実装力を問われる問題にも挑戦できる準備が整ってきたと感じます。
今回のD問題は、以前も見たことのある桁DPのようです。
以前見かけたことのと類似の問題なので、解けるようになっておきたかったですが、初見ですぐ理解して使いこなせるようになることはやはり難しいです。
[今後やること]
直近のABCのD問題を復習します。
パナコン以降も全コンテストに参加してきましたが、自力で回答できたD問題はまだありません。解説動画を見ながらコーディングして、アルゴリズムとその実装力を身に着けていきます。以前とやることは変わっていません。
劇的に学習スピードが上がるような手法があれば、そっちを採用していきたいですが。
目下、ABC-157/160のグラフ問題、ABC-161の桁DP問題を、解説を見ながら実装していきます。
[その他]
プログラミング学習を2019年11月から始めて5ヶ月経ちました。ようやく、当初の自分が想像していた「アルゴリズムの実装」に取り掛かれるくらいの知識を身につけられました。
またひとステップ高い壁と思いますが、楽しんで継続していこうと思います。
パナソニックプログラミングコンテスト2020に参加しました。
初めての緑パフォでした……！
そのおかげで、レートは＋68と過去一番の伸びとなりました。
ABCは、そこそこ安定的にC問題まで解けるようになってきました。
【今回の結果】
A〜Cの三完です。D問題は問題文の意味さえ理解できず未着手でした。
解説動画を見てみると再帰を使ったDFSのよう。コードは短くシンプルですが、私には読めません……D問題の読解を今週の課題としたいと思います。
再帰わからん……！
【所感】
簡単な問題を正確に解けるようになり、一発AC(もちろんテストケースは試す)が出せるようになりました。以前より慣れてきたと感じます。時間をかけたのだから当然ですけど……
やるべきことは今までと変わらないはず、と思っています。
問題を解き、できなかったところの復習を繰り返します。目的はコーディング慣れとアルゴリズムの知識習得です。「これはワーシャルフロイド……！」などと言えるようになりたいと思います。いつだったか、グラフをマスターしたいと言っていましたが手をつけていませんね……
昨年から少しずつ勉強を初めて気づいたこととして、私は新しいことをその場で理解して使いこなせるようなふうには生まれついてないようです。何度か繰り返し同じ課題にあたり、抜けていたところを補填し、しばらく経って苦労を忘れたころにはいつのまにか解けるようになっている、そんな傾向があります。
自分の成長特性（自作用語）をモニタリングする機会として、AtCoderはちょうどいいかもしれません。
【その他】
もっと実応用に近いプログラミングに関心があります。
例えばkaggleのデータ分析、openform（つづりが違う気がする）なんかを利用した流体の数値解析、あとは何だったっけ……？ ともかく興味の先はいろいろあるので、時間の許す限りいろいろつまみ食いしていこうと思います。
数学関連で「集合と位相をなぜ学ぶのか」が面白そうでした。導入に熱伝導方程式の解法が来ているあたり、私の理解度とぴったり一致しています。これ大学の一年生向けの本としておすすめされている……大学数学難しいです。
ブログはサボっていましたが、競プロは続けています。年内茶色コーダー（あわよくば緑）を目指して頑張ります。
あ、あと全く関係ない話ですけど、婚活もしないと……でも婚活という用語と、あのハートマークとキラキラエフェクトだらけの広告がとても苦手であまり踏み入むのをためらっています。なんといいますか、真面目に勉強しているふりをして、人生のメイン課題をサボっているのかも……と思うことがよくあります。
ぼちぼちやっていきます。
AtCoder Beginner Contest 154に参加しました。
今回の戦績
ようやく茶色ラインが見えました……！
先週は、ABCの過去問を144くらいまで辿って解いていました。そのおかげか、A〜Cがさくっと解け、TLEしながらもDまで余裕を持って解くことができました。
できなかった問題
https://atcoder.jp/contests/abc154/tasks/abc154_e
E問題です。「桁DP」と呼ばれる問題だそう。E問題になるととたんに解答の検討もつかなくなります。解説動画をみても理解ができなかったので、その前知識をきちんと付けることが今週の課題です。
今後の目標
AtCoderエスティメーターによると、茶色コーダーになるには1300程度のパフォーマンスを出す必要があるようです。1300がどの程度かを過去のコンテスト記録から見てみると、だいたい6000人中2000〜1000番目程度、難易度的にはDPが実装できる程度のよう。
DPを使いこなせると次の一歩が踏み出せるかなと感じていて、今週はDPの問題を集中的に解いていきます。
https://atcoder.jp/contests/dp
AtCoder Beginner Contest 153に参加しました。
今回は無念の三完でした……！
５５００人中５０００人がD問題まで解くという比較的簡単なコンテストだったようです。
レート変化
パフォーマンスは前回１７０→今回９０と非常に落ちていました。絶対評価でなく「周りの人が解けない問題を、周りの人より早く解ける」ということで評価されます。
自分が参加しているのは「競技」プログラミングなんだ、ということにようやく思い至った感じです。スピードと技術……！ 私はスピードよりもデータ処理手法の概念と実装に関心があるので、早く解くことよりも、他の人が解けない問題を多く、という方向に注力していきたいです。「いもす法」とか「FFT」とか使いこなしたいぜ、という願望があります。
ざらっと全部の問題を見てみると、E問題は正解者が１０００人ほどしかいません。DPを使えるかどうかが一つの区切りようです。ということで、DPへの関心が非常に高まったコンテストでした。
パフォーマンスは落ちましたが、ひとまずレートは＋３されました。
今回解けなかった問題
https://atcoder.jp/contests/abc153/tasks/abc153_e
D問題です。頑張ればできたかもしれないけどC問題に時間をかけすぎました……！
再帰を利用する典型的な問題だったようです。解説を見たらとても短くシンプルに解答していてすごいなと思いました。
類似の問題に当たったときは、数字の小さなほうから具体例を調べ、答えが再帰関数ｆを使った漸化式で表せないかチェックしたほうが良さそうです。
Atcoderの講座では難しくて飛ばしていた再帰ですが、今読むと役に立つツールとして利用できるかも、と思えるので、多少はコーディング慣れしてきた感じはあります。
また、D問題が簡単だったのでE問題もやってみました。こちらは方針も立たないので、動画解説を見ながら解答しました。理解できていない部分はありますが、DPは各種束縛条件に対して最小値or最大値をテーブルに記録していく手法だというところまではわかりました
DP表を埋めていく過程をイメージしながら実装できるようになりたいですね……！
まとめ
競技プログラミングは相対評価の厳しい世界です（当たり前でした）。
私としては、FFTやDPといった手法を自由自在に使いこなしたい欲求があるので、ひとまず早問きは意識せず、自分に解けない問題に挑んで新しい武器を手に入れることに主眼をおいていきたいです。
