aguuxのブログ

博士課程修了→メーカーという経路を辿っている人の日常

Atcoder緑になるまでやったことと、水色への戦略

0.はじめに

昨日のパナソニックプログラミングコンテストで無事緑になったった。何とか3月末までに緑という目標を前倒しで実現できた。

f:id:aguux:20200315122522p:plain

BとCでWA出た時は爆死が脳裏をよぎったけど、例外処理と精度の問題であると仮説を立てて修正しきれた時は成長を感じた。マジ危なかった

ということで成長記録を含めてやってきたこととこれからの戦略をメモ

まとめ

  • 緑になることが最終目標ならC問題までの早解きで十分対応可能
  • 水色が視野に入っているならアルゴリズムにも手を出していくべき
  • 爆死は減らそう。

1.スペック

  • 工学系博士。ただし計算機系ではない。毎日エッペンチューブを振っていた
  • 仕事も計算機系じゃない。もの作って壊してを繰り返している。
  • 使用言語はPython 昔はPHPとか触っていたけど今は全く触っていない
  • プログラミングの授業でforとかifとかは書ける

2.灰色→茶色でやったこと:コンテストに出る

灰色から茶色は特に詰まらなかった。一度だけAB問題でWA連発して爆死したこともあったけどその他は特に問題なく茶色になれた。

意識していたことは、AB問題を早く・確実に解くということだった。パナソニックプログラミングコンテストで見てみると、AB問題だけを大体20分で解けば600程度は出る。なので焦らず確実にBを解いて茶色のスコアを出して、あわよくばCを解いてパフォーマンスを上乗せするという戦略が有効だろうと思う。

3.茶色→緑でやったこと(前半):爆死を減らす

茶色に上がった後はグロービスなどで忙しくて三か月ほどプログラミングを触れなかった。そのあとにまた出始めた時に意識したのはとにかく爆死を減らすことだった。

茶色まで上がる時には爆死の定義は「ABでWA連発」だった。だけれど緑を目指す際、パフォーマンスの傾向を見ていると爆死の定義を一段上げて、「3完できないこと」ととして、とにかくC問題に慣れるようにした。

C問題の傾向としては、計算量を落とさないとTLEが出てしまうという問題構成が多かったと思うのでとにかく10^7回の計算量を意識するようにしていた。実際効果はあったようで茶色上がってから緑になるまでは爆死によるレート低下は特に無かった。

4.茶色→緑でやったこと(後半):アルゴリズムの勉強

茶色上位になるとC問題まで解いてもなかなか上がらなくなるので、D問題の打率を上げることでレートが増加する可能性を高めていった。

D問題の流れとして多いのは考察→アルゴリズムを選択→実装ということなのでここで蟻本などを見ながらDPとかをかじるようになった。実際緑になるだけならいらないかもしれないけど、あればより盤石になるだろうと判断して、出たD問題については解けないまでも考察するようにした。実際最近ではD問題に手も足も出ないということは少なくなった(時間内に解けるとは言っていない)

少なくとも自分が参加したコンテストだけはDまで見てみると決めてしまうのもいいかもしれない。

ついでに100点問題全部埋めもやって爆死の頻度を減らした。ただそこまでやる必要があったかは疑問。途中から虚無だったかも。

4.これから:緑→水色になるための道のり

 

aguux.hatenablog.com

 ここで書いたことをやっていけばいいかなと思う。

  • 数学的考察の強化→数解いて慣れる
  • アルゴリズムの知識強化→過去問
  • 実装力→写経
  • テストケース生成→なんか探す。たぶんネットに転がっているだろう。たぶん

具体的な行動としては300400点問題埋めかなぁ。200点は暇なときにでも。

アルゴリズムは過去の水色なりましたという投稿を見てそれを埋めていこう。

5.最後に

仕事にほぼ活きないのは分かっていたけれど、それでもAtcoderをやれた理由は「達成感がレーティングで目に見えて分かりやすいから」という点が大きかったと思う。

直接は活きないけれど学び方とか戦略は活きるって信じていられたこともでかい。プログラミングは直接は活きないけれど、目標を達成するための戦略の立て方と考えるとかなり汎用性は高そうじゃん?

99.今後の参考文献

AtCoder水色になりました - Qiita

ABC145-C

ABC145-C問題では環境の方で詰まっていたのでメモ

 

 

atcoder.jp

 

N!の経路の中で各経路が登場する回数が等しいことを踏まえて解けばいい

問題はそれぞれの距離を求めるときにnumpyを使おうとした時だった

Pycharmを最近入れたので何の気なしにimport numpyを使おうとしたらどうやらインストールされていないことに気が付いた

んでエラー通りにnumpyをインストールしようとしたVisual C++ビルドツールをインストールしろと。

間違えてVisual Studioをインストールしつつとかやっていたら1時間ほど経過してしまった。。。

pythonでの丸め処理に関するメモ(intと//の違い)

ABC精進中に詰まったのでメモ。

https://atcoder.jp/contests/abc146/tasks/abc146_c

 

切り捨て処理を書くときにint(A/B)と書いたら一問だけWA(Border_1)で出てしまい、inputとoutputを比較したら1だけ違った。

 

int(A/B)ではなく、A//Bと書くことで解決。

 

おそらくint処理の中で切り上げ処理が入ってしまったのだろうと推察。32bitとかそういう話になるのだろうけど、ちょっとどこに書いてあるかは分からないので省略

 

教訓としては、関数は正しく使えということかなぁ。切り捨てる目的でint使ったらそりゃだめだ。。。

ABC147 C問題 思考記録

atcoder.jp

 

C問題を一日一問解くということでまだ解けていないABC147の問題を解いてみた。

問題は正直者と不親切者がいて、

  • 正直者は常に本当のことを言っている
  • 不親切者は適当に言っている(証言が不確か=どちらでもいい)

という条件のもと、各々がいくつかの証言をしている。そのなかで正直者の最大人数を求めるという問題

 

1.どう解くか

正直者と不親切者の01で分けられることと、Nが15人であること、2^15が10^4程度であることを踏まえると、bit全探索で解けると考えたが、そこで実装に手間取った。

2.実装(証言の格納)

それぞれの証言の格納をどのようにすれば良いかということで、二次元の辞書式配列を使ってみた。

3.実装(証言の整合性チェック)

こっちは詰まったというよりも不親切者が完全に嘘つき(必ず逆のことを言う前提)で考えていたため、一度WAを吐いた。それ以外は全探索に関わるサイトを見ながらなんとか答えを出し切った。for構文が多重になったため、どの引数を使用するかでちょっと手間取った。

4.教訓

  • 01で分けられるものがあるものは計算量次第ではbit全探索を考慮する。
  • 問題文はよく読む(n回目)
  • これくらいの規模の問題から紙とペンを使ってフローチャートを書いた方が楽かもしれない。

5.参考にしたサイト

https://qiita.com/keroido/items/8744453a50d8c8b471c1

ABC158参戦と茶色→緑への戦略

相変わらず緑パフォーマンスは出るけどレーティングは茶色据え置き(798)。

f:id:aguux:20200308163645p:plain

※9月から12月はグロービスでそれどころじゃなかった。そのうちそっちも書きたいなぁ。

単調に増加する傾向は変わらないから将来的には緑に到達できるとは思うのだけれど、このままでは水色は遠いので、現状整理とやるべきことを考えてみる。

現状の目標

  • 三月中に緑コーダー
  • 年内に水色コーダー

最近の成績

  • A-C問題は30分以内にはACできる。
  • たまにWAが出る
  • Dは打率5割程度。

足りないことの自己分析と対応

問題を解く流れに沿って考えると、以下の四点に関してまだまだだと思う次第

  • 数学的な考察→数こなすことでパターン化していく。
  • アルゴリズムの知識→意識しないとどうにもつかないので
  • 実装力→写経とかで補っていく。おそらくやっていれば身につくので最優先ではない
  • 計算量に対する考え方→事前にワースト条件を自分で作って試せるような仕組みを作りたい。10^5の計算とかどうやって入力テキスト作ればいいかわかっていない。

この4点の中で優先度高い(意識しないと付かないもの)はアルゴリズムの知識、次いで計算量だと判断。

速さが足りない(早解き)という選択肢もあるだろうけど、将来的にどこかで限界は来ると思うので今回は思考の対象外とした。

アルゴリズムどうするよ

基礎知識が無い以上考えて書いて理解することが最良であると判断。以下4点を順不同でやっていくこととする。

  1. 蟻本眺める
  2. Atcoder C埋め(分からないものは解説と写経)
  3. Atcoder D埋め(分からないものは解説と写経)
  4. 参考サイトに出たアルゴリズムをゴリゴリ書けるようにする

終わりに

どうせ詰まるのなら将来的に水色を目指せるような悩み方をしたいなぁと思ったり思わなかったり。

参考サイト

atcoderで緑になるまでやったこと - Qiita

AtCoderで茶色から緑色に上がるには何を勉強すればよいか - テストステ論

AtCoderで水色になるまでにやったこと&あなたが緑色で停滞する3つの理由 - ホスフィンの日記

株価下落への対策

コロナウイルスがあり、株価が下落している。実際私が所有しているものも合わせて20万近く含み損抱えていて頭を抱えている。

そんな中でやれることとできることを考えてみた。

結論

  • 落ち着くまで寝て待つ
  • 買うとしたらVOOをちまちまと
  • ビジネスマンとしての基礎能力を上げるという方にシフト

この株価下落はいつまで続くか?

そもそもなんで株価が落ちたのかというと、コロナウイルスの蔓延による企業活動の停滞がきっかけだったはず。それを考えると終わるのはコロナウイルスの感染が終息するころであると考えられる。

 以下のサイトで春になれば感染が収まるかに関しての考察が出ていた。

www.newsweekjapan.jp

 他の疾病からの類推であれば、春になれば感染拡大が収まる可能性はあるが、推測でしか言えないという話である。もう一か月ほどは感染が継続するか終息するかに関して注視していく必要があると考えられる。もう一点大事な点としては、コロナウイルスが来年も発生するかどうかに関してである。これがインフルに加えて冬の恒例行事となるのであれば、それを織り込んで今後の動きを考えていく必要があるだろう。

 

騒動の今後に対して

上の話を踏まえると、「一般人にはウイルスの動きなんてどうなるかわからん」と結論づけられると思う。とするのであれば、いつ流行が終息するかなんて誰にも分らず、製薬企業の新薬開発待ちということになる。ということを考えると、まだまだ感染に関しては拡大する前提で投資戦略を考える必要があるだろう。

加えて大統領選挙など、ほかの値動き要因もあるから今後どうなるかはより一層混沌としているように思える

 

じゃあ投資はどうするか?

上記の話を踏まえて以下のように方針を立てる

  1. 現状持っている株→保有し続ける(配当狙い)
    そもそも配当狙いなんだから、下がったので売るというのは道理に合わない。よって保持し続ける。今の状況でもきっと10年持っていれば元は取れる。はず。忘れた感じで待とう。さらば俺の150万。今年の貯蓄で取り返す
  2. これから買う日本株→控える
    こんな状況で買う勇気はない。この騒動が落ち着いてオリンピックが終わったあたりで様子を見て購入するか再度考えていく。
  3. これから買う外国株→時期を分散して投資していく
    米国株は下落&円高で少々買ってもいいか?とも考えたりしている。具体的にはVOOあたりをちょいちょい買っていこうかなと。
  4. 投信→継続
    下がり始めで辞めたら積立投資の意味は無い。経済は10年後にはまた上向いているだろうと踏んで継続して積み立てる。

 

株のこと以外で何やるか

読書とかやっとく。メーカー勤めということでスキルアップが直接昇進には響かないが、今のうちにやっておくことで将来40年以上使えるようになるので、時間とお金は自分にメイン投資をしておく。

2020の目標

2020年も1/6くらい過ぎてしまったけれど年始に立てた目標の現状確認がてらメモ

  • 体重維持
    若干増え気味なので部屋の中でもできるタバタ式プランクとコメの量をちょっと減らすことで対応中。根本的には筋トレをしないと維持は難しいかもしれないので、プランクに慣れたらプランク+筋トレをする

  • Atcoder水色
    順調にレート増加中だけれど緑手前で足踏み。ABCのD問題までの打率を上げることでどこまでいけるか。動的計画法などは運が良ければ書けるけれどまだまだ描き切れていないので、アルゴリズムに関する勉強をしながら毎週のコンテストにできる限り出ていく所存。

  • TOEIC800→凍結
    全くできていない。とりあえず英会話系の本を買ったのでそちらをやっていく。というかそもそもTOEICをやる理由があまり無いので、英会話系の目標にシフトすべきなのかもしれない。

  • サブスク整理
    ほぼ済 NetflixとAmazonPrimeをどうすべきかというのが最後の課題

  • 投資
    がっつり始めた。方針としては「買ったら基本は売らない」というものを守りながら徐々に資金を投下中。6月以降はアパート借りたりするので、そこでの資金まで突っ込まないようにしつつ米国ETFなどにも手を出しつつちょっとずつでも買い進める。

  • 習慣の棚卸
    スマホ→読書への習慣シフトが難航中。。。いい方法ないかな。