2021/04/01 - Lru Room

概略

社会人二年目になったので, 日記でも付けていこうと思い至った次第.

何かしらコンテンツがないとつまらなさそうなので, その日解いた競プロコードとかを上げたり, その日学んだこととかを書くかも. 日記で溜まってきたらそのうち技術記事としてまとめよう.

誰?

どっかの会社でインフラもフロントもサーバも触ってるよくわからんエンジニアさん.

ステータス
書ける	C++, Ruby, TypeScript, Pythonとか
好き	Rust, Haskellとか
使える	kubernetes, React, Railsとか
呟ける	@kilattoeruru
投げれる	github/KL-Lru
解ける	AtCoder/kilattoeruru

プログラミング言語の話

今まで触った言語とちょっと思ったりしたことを書き残すだけ

C

なんだかんだで最初に触った言語. ポインタが山とか言いつつも他にも罠だらけできっちり理解しないとすぐSegmentation Faultになるイメージがある.

こいつをやってたおかげでC++でもたまにCチックな記述をしてしまって, (これこっちの方がいいのでは?)となるケースがよくある.

特にこれと言って何かに使用したりしたこともないので, 多分組込系とかに行かないならほぼ触れないんじゃないかと思っている. とか言っていたら配属された研究室の産物がCでデバックするのに役に立ったりもした.

普通に開発するならC++の方が絶対良い.

C++

競プロにハマった時から触りだした言語. vector等standard libraryがモリモリ使えるしクソほど動作が速いので, 多少雑なアルゴリズムでも競プロを通せたりするので競プロerならやっていて損はない.

C++って何がいいのかいうと, Cよりちょっと遅くなったけどスマートポインタでポインタをいい感じに出来たり, クラスとかが作れたりする感じで諸々がいい感じになってて爆速で動く物. という認識

インターン先でも研究用途でも利用した言語. ライブラリなしで書けと言われたら一番こいつが書ける.

HTML + CSS + jQuery

最初期の自分のウェブサイト作った物がこの構成だった. (残骸が残っている) github.com

今は自分のサイトはGolangのginフレームワークとかで作った物が動いてはいるが, 忙しくなってしまって何も手を付けられてないうちにRustのactix-webとかが気になってきて放置してしまっている.

HTML + CSSが書ければReactのtsx, jsxを書くのに少し親近感が湧く. ウェブの全ての基礎なのでやっておくべき. 基本ではあるけど一度は触れておいた方がよい.

なおjQueryはテンプレート拡充でしか使ってないので, 実質的にHTMLをコンポーネント化してたようなものかと今になって見返すとちょっと思った.

Java

コードが長い!!というのが第一印象. 多分唯一ゲームを作った言語. Swingを使ってチェスを作ったり, UNOのエミュレータを作ったりしていた.

長いし, 慣れないとクラス構成に悩んでるうちに時間がなくなる. 長いし.

カプセル化は必要に応じて必要だとは思うけれど別にクラスじゃなくても良いなと思える部分が多く, 全てをクラスにするJavaはあんまり好きになれなかった.

Python

2系は知らん. 3系を使っておけ. 大体のことが楽にさっとは書ける. 趣味のクローリングや, 一部研究とかで利用した.

機械学習もできる. が, simulated annealingとかヒューリスティックアルゴリズムとかはC++で書いた方が速いと個人的には思っている.

後pandas等はただCSVを読むためだけに利用してはならない. 行列演算とかをしないなら遅い

Haskell

Haskellはいいぞ. 言うことがそれしかない. 関数型言語ではじめに触れたのがこれだったと記憶している. Schemeは記憶にはない. ないということにする.

純粋関数型だけあって, かっちりと全てをかみ合わせなければならない. 値は必要になるまで評価されない. 関数のカリー化. 再帰処理の鬼.

Haskellが美しいと言われる所以を一度やると実感することが出来るので, 必ず一度は触れておけと思っている. なぜ必修じゃないのかよくわかってない.

Go

gin Frameworkを使うのに触った言語. それなりに速くてそれなりにライブラリがある, ということで人気らしいが, 速さを求めるならC++とかRustを書けば良いし, ライブラリの多さで言うならRubyやPythonに軍配が上がるので, どっちつかずの器用貧乏なのでは...?というのを少し感じてしまって以来触ろうともしていない.

まぁGoにはGoの良さがあるのだろうけど, 自分にはよくわからなかった.

Ruby

社会人になってから触り始めた言語. Railsは割と偉大だった. 大体全てをやってくれる. (たまにこないだのライセンス騒ぎとかあるが)

割と, というのは触ってると欠点が見えてくるし, やはり動的型付け言語は所詮動的型付け言語だな, というくらい. Ruby3.0から型アノテーションが出来るようになったので改善されると期待している. (RBS自体は2系からも使えるのだけども, 2系だとSorbetの方しか知らなかった.)

ファイルの取扱は地獄. 100MBとかuploadしようものなら30秒くらい固まる. 素直にクラウドに直で投げろ. それもこれも全てRubyが遅いのが悪い.

TypeScript

半年前くらいから頑張りだした言語. やっぱり型がないとバグを生み出すという自信がドンドンついている.

そしてwebpackの設定はもうわからん. アレは人の手で書くものじゃないんじゃないかと思っている.

型演算は楽しいので良いのだが, 型があっていても完全に動作する保証はないのがこいつの悪いところ. クラスとかを作るとクラスのふりをした謎オブジェクトがクラスのみ可のメソッドに忍び込んで滅ぼしに来る. 多分完全片付けのいい感じのフロント言語が出てきたら切ると思う. 今はこいつがなんだかんだフロントの中では安全な方だと思っている.

anyは許さん. JavaScriptに帰れ. IEも許さん. 土に帰れ

Rust

最近一番熱いと思ってる言語. 安全にしたC++, という印象がある. 他の言語にはあまり見ない, 「変数のライフタイム」とかいう概念が存在したり, 失敗する可能性がある物は成功したかどうかチェックするまで値が使用出来ないようにも出来, 変数は基本immutableで代入は値のmoveを表す等, バグが極力起きないような言語になっている. null safeだし.

更にはこいつ, 関数型チックに書くことが出来る. Haskellと並ぶくらい好き. 更にはこいつのweb frameworkがベンチマークで2位を獲得していて, やるしかねぇの状態, これもやっておけ言語.

てな感じで

今日の競プロ

400点くらいはさくっと解けるようになりたいよなぁとランダム選択で.

今日は ABC188D Snuke Prime

使い放題に入るか個別のサービスを取るかの問題.

各区間の最小料金を取ってその期間分掛けるだけで完了.

$O(N \log N)$

submit result / github

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
int main(){
  ll n, c;
  cin >> n >> c;
  // 区間のコストを計算しやすいように並べ替えつつ保持する
  priority_queue<pl, vector<pl>, greater<pl>> q;
  for(int i=0; i<n; i++){
    ll ai, bi, ci;
    cin >> ai >> bi >> ci;
    q.push({ai, ci});
    q.push({bi+1, -ci});
  }
  
  // 区間コストを前から計算していく
  ll cost = 0, buf = 1;
  ll ans = 0;
  while(!q.empty()){
    ll day, ci;
    tie(day, ci) = q.top();
    ans += min(c, cost) * (day - buf);
    while(!q.empty() && q.top().first == day){cost += q.top().second; q.pop();}
    buf = day;
  }
  cout << ans << endl;
}