2021/04/05

日記

概略

今日は珍しく早朝に目が覚めて朝から焼肉を決めた. そのせいかパワーが高かった気がする.

そろそろ技術記事も書こうかなと思いつ何を書いたらいいやら, GKEのdeploymentの構成方法みたいなの書いたら需要あるのかな.

今日の競プロ

ランダム

今日はABC159E Dividing Chocolate

ホワイトチョコがk枚以下になるようにチョコを割っていく問題.

一見ムリでは? となるが, 制約がゆるい.

もし1列のみであれば, 左から取れるだけホワイトチョコの部分を取って貪欲に行くのが最適.

2列でも横に割れないなら貪欲が最適

Hが10と少なく, 割り方を全探索しても1024, これに対し, W方向1000を貪欲に解くとしても最大で1024 * 10 * 1000なので横方向の割り方を決めて貪欲にやっていきで間に合う.

O(2^H HW)

submit result

#include <bits/stdc++.h>
using namespace std;
int main(){
  int h, w, k;
  cin >> h >> w >> k;
  vector<vector<char>> s(h, vector<char>(w));
  // 文字を数値に直しておく
  for(auto &si: s) for(auto &sij: si) {cin >> sij; sij -= '0';}

  int hseplim = (1 << (h - 1));
  int ans = h + w;

  // W方向は割り方を全探索する
  for(uint pat = 0; pat < hseplim; pat++){
    bitset<10> bs(pat);
    int hsep = bs.count();
    
    vector<int> sep(hsep + 1, 0);
    int vsep = 0;
    bool b = false;
    for(int x=0; x<w; x++){
      vector<int> tsep(hsep + 1, 0);
      int curidx = 0;
      for(int y=0; y<h && !b; y++){
        if(s[y][x]) tsep[curidx]++;
        // 1列だけのカウントでkを超える場合その割方で条件達成不可なので飛ばす.
        if(tsep[curidx] > k) b = true;
        if(bs[y]) curidx++;
      }
      if(b) break;

      // 各区間のホワイトチョコの合計を計算しとく. ここでoverするならこの手前で割ったことにすればよい
      bool over = false;
      for(int i=0; i<=hsep; i++) if(sep[i] + tsep[i] > k) over = true;
      if(over) {vsep++;}
      for(int i=0; i<=hsep; i++) sep[i] = over ? tsep[i] : sep[i] + tsep[i];
    }
    if(b) continue;
    ans = min(ans, hsep + vsep);
  }
  cout << ans << endl;
}

2021/04/03

日記

概略

今日は親知らずをぶち抜いてきた. 麻酔をしていたとしても顎外れるんじゃないかと思うレベルで力技で抜かれるので普通にめっちゃ怖かった. そして謎の喪失感があると共に血が滲むのが止まっていない. 今日のご飯はinゼリーにしておこう...

そんなこんなで今日もあまり開発作業は出来ていない. まぁ安静にしてさっさと寝よう.

今日の競プロ

再びのランダム

今日はABC131E Friendships

最短距離が2になる頂点対数がkになるようなグラフを構築する.

連結グラフが条件なので, 各頂点に対して距離が1になるような頂点が少なくとも1つは存在する. 1つの頂点Xに全ての頂点を隣接させると, 頂点X以外の頂点は, 頂点Xへの距離が1となり, それ以外の頂点への距離が全て2になるようなグラフGが構築出来る. こいつが最短距離が2になる頂点対数最大のグラフ.

この時の最短距離が2になる頂点対数は, n-1個の頂点から2個選ぶ組み合わせ数に等しいので,

{}_{n-1} \mathrm{C}_{2} = \frac{(n-1)(n-2)}{2}

kがこれより大きくなる場合は条件に合うグラフが構築出来ない. kがこれ以下の場合はグラフGの任意の最短距離が2である頂点対の間に辺を追加することで, 最短距離が2である頂点対を1つずつ減らしていくことが出来る. k = 0の場合は完全グラフを書けばよい.

以上からグラフGを作ってから, 最短距離が2になる頂点対数がkになるまで辺をいい感じに足せば終わり

O(N^2)

submit result

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n, k;
  cin >> n >> k;
  int mx = (n - 1)*(n - 2) / 2;
  int diff = mx - k;

  // 可能な頂点対数を超えていたら-1
  if(diff < 0) {
    cout << -1 << endl;
    return 0;
  }

  // グラフGを作るのに必要な辺数n - 1 + 最短距離2の頂点対数をkに減らすのに必要になる本数
  cout << n - 1 + mx - k << endl;

  // 頂点Nを頂点X扱いとしてグラフGを作る
  for(int i=1; i<n; i++) cout << i << " " << n << endl;

  // 最短距離2の頂点対数をkまで減らす
  int cnt = 0;
  for(int i=1; i<n && cnt<diff; i++){
    for(int j=i+1; j<n && cnt<diff; j++){
      cout << i << " " << j << endl;
      cnt++;
    }
  }
}

2021/04/02

日記

概略

新卒の方々が入ってきてフレッシュさを感じつつ仕事の増加を感じる日々になってきた. 去年自分はあんなにまでフレッシュだったのだろうか?

そんなこんなで今日は時間がなかったので数カ月ぶりに弁当というものを買って食べたが, 1分半でカツカレーが出来る技術力ってすごいよなぁとかいいつつ全然足りないのを感じる. やはり大量に食べる人間だと自炊のほうが多少コスパは良いのだろうか. 全然足りないので結局お菓子をつまみながらこれを書いている. チーズとワインも開けちゃう.

今日の競プロ

ランダム選択で

今日は ABC167E Colorful Blocks

1列でn個のブロックのm色での塗り方で同色が隣り合うところがk組以下になるような並べ方.

x組ピッタリ隣り合うところが同色になる物が出来るパターン数は, 各々が左隣と色の異なるようにn-i個のブロックをm色で塗る塗り方の総数に, どこが組みになるかの組み合わせ数を掛けた物と同じ.

各々が左隣と色の異なるようにn-x個のブロックをm色で塗る塗り方は左端がm色, それ以外は左隣の1色を除くm-1色から選べばよいので,

M \times (M - 1)^{n - x - 1}

どこが組になるのかの組み合わせ数は, ブロックとブロックの隙間の数n-1からx個選ぶ組み合わせ数と同じなので,

{}_{n-1} \mathrm{C}_x = \frac{(n-1)!}{x!(n-x-1)!}

modが素数指定なのでモジュラ逆数が使える.

\frac{(n-1)!}{x!(n-x-1)!} = (n-1)! \times (x)!^{-1} \times (n-x-1)!^{-1}

ここまで分かれば 0 \leq x \leq k の範囲を計算して合算するだけ.

O(N \log MOD + K \log N)

submit result

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

// mod計算utils
template <typename Head>
ll modprod(Head head){return head;}
template <typename Head, typename... Tail>
ll modprod(Head head, Tail... tail) {
  return (head * modprod(tail...)) % MOD;
}

template <typename Head>
ll modsum(Head head){return head;}
template <typename Head, typename... Tail>
ll modsum(Head head, Tail... tail) {
  return (head + modsum(tail...)) % MOD;
}

ll modpow(ll x, ll p) {
  ll a = 1;
  while(p > 0) {
    if(p % 2 == 1) a = modprod(a, x);
    x = modprod(x, x);
    p /= 2;
  }
  return a;
}

ll modinv(ll x){
  return modpow(x, MOD-2);
}

int main(){
  ll n, m, k;
  cin >> n >> m >> k;

  // 階乗とその逆数を計算しておく
  vector<ll> fact(n+1), invfact(n+1);
  fact[0] = 1; invfact[0] = 1;
  for(int i=1; i<=n; i++) {
    fact[i] = modprod(i, fact[i-1]);
    invfact[i] = modinv(fact[i]);
  }

  ll ans = 0;
  for(int i=0; i<=k; i++) {
    // 計算式通りの計算をするだけ
    ll pat = modprod(m, modpow(m-1, n-i-1), fact[n - 1], invfact[i], invfact[n - i - 1]);
    ans = modsum(ans, pat);
  }
  cout << ans << endl;
}

2021/04/01

日記

概略

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

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

誰?

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

ステータス
書ける 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;
}