くるのプログラミング記録

プログラミングの感想とか解説とか。

むしょくstreak3

競プロ

 Cは1時間もあったなら解けないといけなかった。うーん。
橙diff埋めは考察途中。


ゲーム

  • モンハン

 やっとクレジット観るとこまで。


その他

  • 遊んでいた。

 今日は殆ど何もしていない。明日からがんばりましょう。

そういえば、むしょくとは題打ってるけどかなりファッション無職なので、もし誰か見ていた人や勘違いさせてしまった人がいたら、ごめんなさい。

むしょくstreak2

競プロ

  • 橙diff 1問
  • 水diff以下をいくつか

漫画

  • 進撃 1-20巻

 早く追いつかねば


ゲーム

 2試合

  • モンハン

 今作面白い。皆進むの早すぎ。


その他

  • 病院に行った。
  • ニトリに行った。

 ソファを買いたいなと思いつつ、お金が安定するまで我慢......。

  • 自炊をした。

むしょくstreak1

競プロ

  • 橙diff 1問
  • 水diff以下をいくつか

漫画

 同じ映画4回観るのは初めてかも。



その他

  • 業務PCを返した。

 さようなら。

  • 自炊した。

 ポン酢でだし巻き卵を作ると美味しい。

  • まぐさんとdiscordしてた。

 エンジニアリングの話は楽しい。

業務2年目終わりメモ。

2年目が終わった。
webエンジニアになれているかというと......。
まあでも2年もあると自分のコンポーネントでわからないところほとんどないし仕事自体はやりやすいよね、って。



以下2年目までの技術スタック。



DB・データストア

cassandraはかなり触った。分かってない人が作った設計の負債のデカさがrdbよりやばくなると感じた。こわいこわい。
memcached, solrは殆どエアプ。一人で運用してって言われたら多分わからん。
後よくわからんnfsを業務で触っていた。今も謎のまま。

elastic search, oracleあたりを触ってみたいなと思っている。
あとdbとは違うけどkafkaもpulsarも触ったこと無いの結構危機感がある。3年目終わるときまでにはなんとか......。いやmqなくても済む設計が多いような良くないような......。
dbはかなり苦しんだ2年だった。busy100%で張り付いて死ぬみたいな経験はもう二度と味わいたくない。



言語

言語を並べるの不毛感あるね。
goは業務ですぐ書けって言われたら全然無理。
現状バックエンド書くならjavaが一番かなあという気持ち。
c++も今競プロしか使ってないからかなり苦しいかも。
bashを相対的に一番学んだ気がする。



フレームワーク
  • Spring Boot
  • Spock
  • Junit
  • Laravel
  • Fuel
  • Symfony
  • Next
  • React
  • Vue
  • ReactNative

バックエンドは現状Spring Boot一択みたいな気持ちがある。数年後には価値観変わってるのかな。
型のない言語を新規で使う意味がマジで感じれてないので(極端かも)、Railsとかやることはこの先もなさそう。
Spock, Symfonyあたりはフレームワークなのかはよくわからんけど、とりあえずここに入れた。
テストはJunitよりはgroovy使ってSpockで書くほうがいいかなって現状思っている。
フロントは業務でモダンなSPA使ったこと無いので全然わからん。
趣味だとnextが結構良いかなと感じている。
スマホアプリもふわっと触っただけ、絶対業務じゃ無理。
iosも泥も一回ずつ軽いものを作っただけ。




CI/CD
  • screwdriver
  • chef
  • ansible
  • code build / code deploy / code pipeline
  • github actions
  • jenkins
  • concourse

どれも使ってるだけなので、スタックに入れていいか微妙感。
terraform使ったこと無いけど、やばいのでどっかでやんないとなあ。
chefは出来ることなら触りたくない。



コンテナ・インスタンス
  • OpenStack
  • ec2
  • docker
  • ECS
  • pivotal cloud foundry

割と実機か普通のインスタンス稼働の運用が多かったのでコンテナ経験はめちゃめちゃ浅い。
k8sとか触ったことない。
かと言ってOpenStackも運用してるわけじゃなくて使ってるだけ、ユーザー側最高!
現状ecsが一番使いやすい感あるね。pcfもめちゃめちゃ便利だけど、運用してくれる人がいるなら......って感じがある。



ネットワーク

Kongはラッパー使ってるだけなのでエアプもエアプ。ネットワークは未だに黒魔術に感じている。マスタリングTCP/IPを読まないといけないのかな。
業務だと設定ポチポチしてただけが多い。vipつくってlbかましてAレコ張って、そこからエンドポイントキャッシュ効いた別のドメイン張って、ぐらいのシンプルなことまではできて、後はわかんないね。
趣味だと完全にAWSをぽちぽちするだけ。


ドキュメント
  • swagger
  • plant uml

コンフルで済ませちゃうことが多かった。
まあspring foxでコードから自動生成するswaggerは好き。逆に普通に書くswaggerはなんかコストと維持を考えると見合うのかなって気持ちが(人間はドキュメントを更新しないので)



ほか
  • DDD

 哲学な感じもするけど、やはり共通の文脈というのは大事で......。

 負荷試験もこの2年でめっちゃやった。未だにベストプラクティスはわからず。難しいね。

  • pt-online-schema-change

 クソ便利ツールなのだが、ちょっと怖いときがある。これもかなり多用した。

  • S3

 ストレージこれ以外使ったことない。静的フロントもこれで動くのいいよねえ。

  • prometheus

 ドレインするためにactuatorに使ってただけ。一回ホスティングしないとなあ。

  • splunk

 これも使ってただけなので、詳しいかというと......。

あとはgithubとか、流石に書く必要ないやつぐらい?たぶん。masterにpushしないぐらいにはgitが使えます!

なんかまだまだあると思うけど、思い出せるのはこれぐらい。









結局インフラ周りはひたすら使うだけだったので、詳しいことは分からんままなんだろうなあという感触が強い。


セキュリティ周りも割と社内システムに乗りまくってたので経験薄いなって感じはある。
クレデンシャルの扱いとかはまあ最低限として、例えばsidecar的な設計の認可システムを趣味開発に入れるとかやるのはちょっと腰が重い感じがある......。


パソコンのことはなにもわからないままだった。ubuntu > mac > windowsぐらいの好みがあるだけ。
osがなんで動いてるのかわからないまま、雰囲気でプログラミングをしている......。
vimも全然身につかなかった。シェルもawkで全部誤魔化している。
このへんできるとエンジニアっぽいよね。


graphQLとかgrpcも全然使わなかったな。まだxmlがはびこっている感じがする。フルでjsonになってるだけでかなりマシだなみたいなイメージがあるね......。


フロントのデザイン的なことはマジで業務でもやんなかなったので何もわからないまま。bootstrapが使えます!!!!


読んだ技術書。うーんまともに読み切ったものは少ない、積みがち......。
github.com







技術スタックや知識よりは、それ以外の考え方とかのほうがエンジニアリングする上では大事かもって気持ちになりつつはある。
まあでも手を動かせないぐらい知らないのはダサいみたいな価値観もあるので、知識は増やしていきたい。






この2年でバックエンドをもっとやっていきたいなという気持ちが固まった。ふわっとはしてるけど。
技術選定を自信持ってやれるようになりたいね。


数年後見返したときにこの頃は知識浅いなと思えますように。

2021目標メモ。

まず去年の目標から。
2020目標メモ。 - くるの競プロ記録

AtCoder
 タッチで終わっちゃったなあ。うーん。

・こどふぉ濃橙タッチ
 それどころか薄橙すら......。

・AtCoder800まで埋める
 800はきつすぎたので黄diffまで埋めた。妥協。

・ARC-Eまで埋める
 これ微妙に残ったまんま。残が橙赤diffでちょっと厳しい。

・yukicoder★3まで埋める
・こどふぉ2000以下とかでいいから数を埋める。
・マスターオブ場合の数/整数をやる
 どれも出来てないし取り組めていない。精進の絶対量が落ちてるねえ。

・システム設計意識してwebアプリをつくる
 業務だけどまあ出来たかな。今よりデカいシステム触りたい。

・今の会社をやめてもいいから仕事は続ける
 想像以上にエンジニアリングへのモチベは高くなった一年だったね。†未経験†感がちょっと減った気もする(?)

機械学習を復帰する
 むりだった。うーん当分はwebエンジニアかなあ。


ほかにやったこと
・OUPCwriter
 作問機会は増やせたので良かったね。

・年収++
 いやらしい話だけど、大事なのでまあ......。

Java
 2019はphpしか書いてこなかったけど2020はかなりJava書く機会があった。

・技術書。
 contents-memo/book.md at master · ningenMe/contents-memo · GitHub
 エリックエヴァンス読み終えれたのがよかった。少しずつでいいからやめずに色々読んでいきたいね。



2021目標
AtCoderレート2100
Codeforcesレート2100
AtCoder黄diff埋め維持
・ライブラリを増やす
・定期的な趣味開発
・技術書を読む
・資格をとる(応用情報かデスペ)

競技プログラミングは苦痛なくレート上げるにはかなりsaturationしていると感じている。悲しいね。
もっとやりこんだら上がるのかなあ。
橙になれる気は全然しない。競プロ自体は楽しいし黄色でいたい気持ちは強いのでまずはそこから。


エンジニアリングは年収駆動にならないようにしたいね。技術駆動であり続けたい。

社会人になってから賞とかもらえる機会が減った感があるので、モチベをいい感じにコントロールしないとなって。
小さなことをコツコツと。
コミットし続けねば。

競プロ駆動で開発している話。

adventar.org

この記事はCompetitive Programming (1) Advent Calendar 2020の23日目として書かれた記事です。

2023/05追記。

この記事で取り扱ってるwebsiteは下記のページにリプレイスしました。
https://ningenme.net/compro-category


はじめに

こんにちは。くるです。
atcoder.jp
競プロ駆動で開発している話をします。

概要

まずは成果物。

https://compro-category.ningenme.net/#/compro-category.ningenme.net

約1年ぐらい運用している自分用の精進記録webアプリについて話します。以下ポエムです。


なにをしているの?

自分が競技プログラミングで解いた問題をひたすら記録しています。
ラベルつけてある程度のジャンル分け、タグ付け。それと体感の点数をメモしています。
こんな感じ。



submission漁れば良くない?

全然それで事足りると思っています。まあ一応これ作ってるおかげでコンテスト中とかにジャンルから逆引きしたりはよくします。

それでレート上がってる?

あがってないんだな、それが……。
AtCoder青黄を波打った一年......。

開発する時間で精進したほうがよくない?

核心を突かれると、つらい。

ちゃんとジャンル分け出来てるの?

https://twitter.com/ningenMeの知識に依存しています。なので問題の本質の切り分けが下手だと雑なジャンル分けになりがち。まあそこらへんは見え方変わってくると時々修正したり。

意味ある?

楽しいので、ok。




こ こ か ら 本 題 。



システム構成図


ややこしいね。まずリポジトリが3つある。

- フロントエンド。s3上でvueで動いている。フロントって何ーって人はまあ、リンク先のブラウザで見てるものがフロントだと思ってもらえれば。s3って何?って人はawsクラウドストレージだと思ってもらえれば。vueって何?って人は......jsです!(雑)

- 文字通りapi。restです。apiって何ーって人はまあ、データ管理してるところだと思ってもらえれば。

- submission貯めてるだけのリポジトリ。本当にただの.cppがたくさんあるだけ。

フロントエンド

s3にvueのソースをビルドしたものを置いています。これだけで動くので簡単なアプリケーションなら一番楽に感じる。reactでも同じこと出来るよ。
今動いてるvueのソースはマジで書きなぐりなのでかなり汚い......(リファクタする意欲も失った)(動くのでok)

cloud front使ってhttpsでアクセスしてもらっています。このへんawsかなり楽で良い。ぽちぽちするだけ。証明書周りほぼノータッチ。
ドメインは昔から持っているので割愛(ドメイン取得はちょっと面倒だった記憶......)(気のせいかも)

バックエンド

ec2にjavaのアプリケーションをデプロイしています。spring bootで書いている。現状DDDやるなら一番好きなフレームワーク
フロントからapi-gateway越しにリクエストが来るのでいい感じにエンドポイントを用意している。api-gatewayもかなり使い勝手良いね。

エンドポイントはこれ。
https://ningenme.github.io/api-document/ningenme.github.io
spring fox使うとソースから自動でswagger作れるのでかなり楽。自分でyamlはもう書けない......。

あとdbは無難にmysql

CI/CD

フロントエンド / バックエンドはともに自動デプロイ。全部github actions。
chef, ansible, jenkins, code-deployとかいろいろ試したけど面倒さがだいたい上回るのでgithub actionsでシェル書くだけがなんだかんだ効率いいかなってなっている。怠惰趣味開発。
ちゃんとやるときは実機ならansibleがかなり好きなんだけどね。


submssionに関しては、いつもソースを記録用でgithubに残している。
こんな感じ(伝われ)

そのときにコードにアノテーションをつけて、pushしたときに自動でapiにデータ登録してくれるようにしている。
アノテーションはざっくりこんな感じ。

/**
 * @url https://hoge.com
 * @est 400
 */ 
int main() {
    return 0;
}

問題urlと体感点数を書いてpushすると、自動でdbに入る仕組み。パースはオレオレパースなので変なコード書いたらすぐ死ぬ......(運用で、カバー!)
問題登録時に、AtCoder, AOJ, Codeforces, yukicoderあたりなら問題名とかも勝手に拾うようにしている。そろそろTOKIも対応させたいね。

運用

だいたいこんな感じ。タグ付けがちょっと面倒だけど、問題振り返る機会になるので悪くはない。

用途

コンテスト中とか作問するときに、たまに逆引きで使う。
解いて意味あったなって思える問題だけ貯蓄してるので、虚無ばっかり埋めてることを実感する(悲しい)

さいごに

皮肉っぽくは書いたけどかなり自己満足度は高いです。問題を解いていく上でのモチベーションにつながると、楽しい。

ソースは全部公開しています。気になった方はぜひ。
github.com

OUPC2020 G. Construction Set 解説

問題条件を下記のように[1]-[4]とします。
[1]. どの要素も{\displaystyle 6}で割ったあまりは{\displaystyle 1}でない
[2]. どの相異なる{\displaystyle 2}つの要素も、{\displaystyle 1}で割ったあまりは等しい
[3]. どの要素も約数の個数は{\displaystyle 4}個である
[4]. どの相異なる{\displaystyle 2}つの要素も、最大公約数は{\displaystyle 1}である

まず[1]の条件で禁止される数は全て排除しましょう。

次に[2]の条件より、{\displaystyle 6}で割ったあまり{\displaystyle 0,2,3,4,5}に関してあまりを決め打ちして全探索を行いましょう。

以下その前提ですすめます。

まず[3]の条件より、集合の要素は全て次のいずれかです。

・ある素数{\displaystyle p}{\displaystyle 3}
・相異なる素数{\displaystyle p}{\displaystyle q}に対して{\displaystyle pq}

ここで[4]の条件より、集合内のどの{\displaystyle 2}要素も同じ素因数を持たないことがわかります。

よってある素数{\displaystyle p}{\displaystyle 3}乗に関しては貪欲に全て集合に加えて良いです。またここで含んだ素数{\displaystyle p}を持つ{\displaystyle pq}の形で書ける数に関してはこの時点で除外して問題ないです。

ここで{\displaystyle 5}以上の素数に関しては全て{\displaystyle p=6n+1}あるいは{\displaystyle p=6m-1}と書くことが出来ることを考慮して、場合分けを考えましょう。


{\displaystyle 6}で割った余りが{\displaystyle 0}のとき

加えられる数は、{\displaystyle 6}のみです。
集合の最大サイズは高々{\displaystyle 1}です。


{\displaystyle 6}で割った余りが{\displaystyle 2}のとき

加えられる数は、{\displaystyle 8}あるいは{\displaystyle 2p}(ここで{\displaystyle p}{\displaystyle p=6n+1}の形で書ける素数)のみです
ここで{\displaystyle 8}{\displaystyle 2q}は互いに素ではないので、集合の最大サイズは高々{\displaystyle 1}です。


{\displaystyle 6}で割った余りが{\displaystyle 3}のとき

加えられる数は、{\displaystyle 27}あるいは{\displaystyle 3p}(ここで{\displaystyle p}{\displaystyle p=6n+1}の形で書ける素数)あるいは{\displaystyle 3q}(ここで{\displaystyle q}{\displaystyle q=6m-1}の形で書ける素数)のみです
ここで{\displaystyle 27,3p,3q}はそれぞれ互いに素ではないので、集合の最大サイズは高々{\displaystyle 1}です。


{\displaystyle 6}で割った余りが{\displaystyle 4}のとき

加えられる数は、{\displaystyle 2q}(ここで{\displaystyle q}{\displaystyle q=6m-1}の形で書ける素数)のみです
集合の最大サイズは高々{\displaystyle 1}です。


{\displaystyle 6}で割った余りが5のとき

加えられる数は、{\displaystyle p^3}あるいは{\displaystyle pq}(ここで{\displaystyle p}{\displaystyle p=6n+1}の形で書ける素数{\displaystyle q}{\displaystyle q=6m-1}の形で書ける素数)のみです
{\displaystyle pq}の形で書ける数{\displaystyle p_1q_1,p_2q_2}に関しては、{\displaystyle p_1 \neq p_2}かつ{\displaystyle q_1 \neq q_2}ならば、両方選択することが出来ます。
すなわち{\displaystyle pq}の形で書ける素数に関して、素数を頂点としたグラフを考え頂点{\displaystyle p}と頂点{\displaystyle q}に辺を張ると、この問題は辺の張られたグラフから最大マッチングを考える問題になります。
また上記のグラフは{\displaystyle 2}部グラフになるため、最大マッチングが簡単に求まります。


よってこの問題が解けました。
計算量は素因数分解の際に{\displaystyle O(N \sqrt{A_{max}})} 、 二部マッチングの際に{\displaystyle O(N^2)}必要で、全体で {\displaystyle O(N \sqrt{A_{max}}+N^2)}となります。
素因数分解の際にポラード・ロー法などを用いることで、計算量をもう少し良くした解法もあります。