くれなゐの雑記

例を上げて 自分で手を動かして学習できる入門記事を多めに書いています

pushbulletをubuntu 16.04でインストールできなかった

タイトル通り いろんなサイトを見てもapt-getしようと書いているんだけどapt-getできず
リポジトリが違うのだろうか

今回は計算が終わったら通知するようなコマンドが欲しかったのでperlを使って代用する
以下の記事をみれば導入できた

qiita.com

Ubuntuでa start job is running for dev-desk-by ...とかでて起動が遅い

環境:VMware上のUbuntu 16.04

状態

VMware上でGPartedを使ってパーティションを変更したら起動中に「a start job is running for dev-disk-by…」とかでて起動に90秒以上かかる これはウザイ

原因

GPartedでパーティションを変更したきっかけにswapのUUIDが変わってしまっていたらしい

直し方

UUIDを元に戻す

sudo blkid

でswapのUUIDが出てくるので、それを

/etc/fstab

のそれらしいところに書き込む

C++の.at()で配列外参照(Out Of Range)を検出して配列外参照した時に0などを返すマクロ

結論

(競技用なのでマクロ小文字ですごめんなさい)
あとこれ本当にバグなく動くのかよくわかってないです

#define oorret 0
#define oor(x) [&](){try{x;} catch(const std::out_of_range& oor){return oorret;} return x;}()

使用例

.at(10000)という範囲外の部分を参照してますが、0を返しています。


gist4e9a649b1c983d0d7d755698c3f7b78c

続きを読む

priority_queueでclear()をする

競技とかで、priority_queueの中身をclear()したいけどメソッドがない
なので、以下のように書く

priority_queue<int> que;
...
que = priority_queue<int>();

これでもめんどくさいのでこうする

priority_queue<int> que;
...
que = decltype(que)();

以下みたいなの書いとくのもアリかもしれない

#define CLEAR(a) a = decltype(a)(); 

 

門松もどき

競技プログラミング

珍しく競技プログラミングの解説記事です

yukicoderの問題 非常に厳しい問題だった 問題はこちら
No.127 門松もどき - yukicoder

要約すると、左右左右と単調に大きくなりながら真ん中によっていく最長増加部分列問題みたいなやつ
とりあえず最長増加部分列の問題
は蟻本にあったので、そちらを見ると, dpを使っている。なるほどdpを使えば確かに解けそう

というわけで以下のようにdpを組む

  • dpL[l][r]: lから始まって(lが最小)rまでの範囲で、最大となる門松もどき
  • dpR[l][r]: rから始まって(rが最小)lまでの範囲で、最大となる門松もどき

1. l=rで幅が0の時, 門松もどきは1なのでこれで初期化

2.1. dpLは右に広げていくイメージで, 左が最小なのでlの値よりもrが小さければ, 広げる前と同じ.
逆のケースでは, 右から始まっているケースに, +1(lの分)を加えた値と比較して更新

2.2. dpRは左に広げていくイメージで, 右が最小なのでrの値よりもlが小さければ, 広げる前と同じ.
逆のケースでは, 左から始まるケースに, +1(rの分)を加えた値と比較して更新

式にするとこんな感じ



 {

  dpL[l][r] = \begin{cases}
      1 & (l=r)\\
      dpL[l][r-1] & (A_l \geq A_r) \\
      max(dpL[l][r-1], dpR[l+1][r]+1) & (otherwise)
  \end{cases} \\ \\

  dpR[l][r] = \begin{cases}
      1 & (l=r)\\
      dpR[l+1][r] & (A_l \leq A_r) \\
      max(dpR[l+1][r], dpL[l][r-1]+1) & (otherwise)
  \end{cases}

}

実装方法も少し困ったREP(l,N)REP(r,l)みたいな感じで更新しようとしてもまだ求めていない値を参照する形になってしまう
このdpは, 徐々に幅を広げていくイメージがあったので幅を徐々に広げていくようなdpにした

r = l+wとすると,
w = 0の時, l=rですべて1
w = 1の時はw=0の時の値を使用
w = 2の時はw=1の時の値を使用
のようにwとlを用いて更新するといい感じにdpできた
もしかするとlrではなくlwでdpをすると綺麗だったかもしれない

今回, dpL, dpRはそれぞれlやrから始まるdpにしているので, dpL[0][N]などを出力しても, 0から始まる門松もどきの最大値となり, たとえば正解が1から始まる門松もどきだったらWAになるので, すべてのdpL, dpRに関しての最大値を出力しなければならない.

以下にソースコード

gista5ab6cd749425ed74ea2

.pdfから.jpg等の画像ファイルにしたい

知り合いが困っていたので記事にする

Install

王道のImagemagickを使う
chocolateyが入っているなら

cinst imagemagick

で入ったはず
入ってないのならここからそれぞれの環境に合ったものを入れてください 多分windowsならmingwがいいかな
www.imagemagick.org

使い方

convert input.pdf output.jpg

これで終わり