おはやし日記

プログラミングと旅行と,その他諸々について書いています。

DP(動的計画法)でレーベンシュタイン距離(編集距離)問題を解くまでの過程メモ

昨日は最長増加部分列の問題を解きました

https://o-treetree.hatenablog.com/entry/DPL1D

今日は、AOJの編集距離の問題を解きます。

といっても、相変わらずDPテーブルは思いつかなかったので検索してわかりやすかった解説を紹介する感じです。

参考にするのはこちら→編集距離(レーベンシュタイン距離)の求め方 - 具体例で学ぶ数学。ググってQiitaとか見たりしましたがこのサイトの説明が最も直感的でわかりやすかったです。

では、やっていきましょう。

問題

2つの文字列 $S,T$ の編集距離(レーベンシュタイン距離)を求めよ。

レーベンシュタイン距離 - Wikipedia

挿入、削除、置換の各操作のコストはいずれも $1$ とする。

続きを読む

DP(動的計画法)で最長増加部分列(LIS)問題を解くまでの過程メモ

なんか連載みたいになってんな

前回はDPでナップザック問題を解きました。

AOJでその次にあった最長増加部分列を解きました。

というか、解けなかったので検索して最長増加部分列(LIS)の長さを求める - Qiitaを見てなるほど〜ってなったのを自分なりにまとめ直したものです。

問題

$N$ 項の数列 $a_0, a_1, \cdots , a_{N-1}$ が与えられたとき、最長増加部分列の長さを求めよ。

(最長増加部分列がなんぞやということについては本家問題ページを読んでください)

制約

  • $1 \le N \le 100000$
  • $0 \le a_i \le 10^{9}$
続きを読む

DP(動的計画法)でナップザック問題を解くまでの過程メモ

0-1 ナップザック問題

この0-1ナップザック問題が解けたので動的計画法初心者がその思考過程を記録しておく。

その後、簡単な書き換えによって一般ナップザック問題(命名: おはやし)が解けたので追記している。

先にコイン問題

前段階としてコイン問題(何種類かのコインでN円払うときの最小支払い枚数を求める)をやった。

動的計画法むずかしい……って人は先にこっち↑を読むと良いかもしれない。保証はしかねるが。

0-1ナップザック問題へ

今回もAOJにお世話になる。提出先は0-1 ナップザック問題である。

問題

容量 $ W $ のナップザックがあり、品物が $ N $ 種類、それぞれ1個ずつある。

品物 $ i (1\le i \le N)$ は、それぞれ価値 $ v_i $ 、重さ $ w_i $ を持っている。重さの合計が容量 $ W $ を超えない範囲で品物をナップザックに入れ、ナップザックに入った品物の価値の合計を最大にしたときその最大値を求めよ

(それぞれの品物について「入れる or 入れない」なので「0-1ナップザック問題」というらしいですhttps://www.morikita.co.jp/data/mkj/081022mkj.pdfのp.88)

制約

  • $1 ≤ N ≤ 100$
  • $1 ≤ v_i, w_i ≤ 1,000$
  • $1 ≤ W ≤ 10,000$
続きを読む

DP(動的計画法)でコイン問題を解くまでの過程メモ

これは、https://o-treetree.hatenablog.com/entry/DPL1B(明日投稿)の前段階の記事です。動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)で「コイン問題」を解いていますが、DPとはなんぞや、みたいなところには触れておらず、解説を見ながらとりあえず解けるまでの初心者の思考をメモしたものです。

DPがわからん!

最近暇なので(無職で外出自粛)競技プログラミングAtCoderをやっています。先日AOJにも登録しました。

BFSとかDFSは一応わかったのですが、頻出のDPがわからんので勉強しようと思いました。

↓BFSとかDFSができるようになった記事

o-treetree.hatenablog.com

o-treetree.hatenablog.com

さて、いろいろ検索しましたが、一番わかりやすかったのはこちら。GoogleBooksで立ち読みできました。(今後見られなくなるかも、知らんけど。買いましょう。)

一応アマゾンのリンクも貼っておきます。アフィ登録してないから僕には一銭も入らんのですけどね。

解く問題はAOJのコイン問題です。といっても有名問題なのでいろんなところで(?)見かけます。

上記の本はAOJの開発者が書いてるのでAOJの問題と本の内容がリンクしてます。というわけでコイン問題の直接の解説が書いてあって助かりました。

問題

額面 $ c_1, c_2, \cdots ,c_M $ 円の $ M $ 種類のコインで $ N $ 円を払うとき、最小の枚数は何枚か

制約

  • $1 ≤ N ≤ 50,000$
  • $1 ≤ M ≤ 20$
  • $1 ≤ c_i ≤ 10,000 (1 \le i \le M)$
  • 額面はすべて異なり、必ず1を含む。
続きを読む

Automateで現在地取得 [Location get]

Automate で現在地を取得する方法についてまとめました。

環境 : Android 9.0, Automate Version 1.23.1

llamalab.com

現在地取得

今回紹介するのは Location :: Location get ブロックです。

f:id:o-treetree:20200523095139j:plain

現在地の座標等を取得し変数に入れます。

このブロックを利用するにはGPSを有効にする必要があります。

Options オプション

Proceed

いつ処理が進行するか

  • Maybe immediately - 新しく現在地の取得ができたら処理される
  • When change - 既知の現在地から、最小でもMinimum distanceだけ移動するまで処理が一時停止する。

Input arguments 入力引数

Location provider

位置情報取得の方法。詳しくはAndroid自体の仕様の話になると思うので検索してください。

Balanced:デフォルト / GPS / High accuracy / Low power / Network / No power / Passive

Maximum fix age

Maybe immediately オプションで利用。よくわからんがデフォルトのまま or 0 でよい。

Minimum distance

When change オプションで利用。ここで設定した距離 (m) 移動するまで処理が一時停止する

Output variables 出力変数

Location fix latitude

緯度を代入する変数

Location fix longitude

経度を代入する変数

Location fix altitude (m)

高度を代入する変数。ただし非常に不正確。高度情報が利用できない場合はnullが入る

Location fix bearing (º)

方位を代入する変数。方位情報が利用できない場合はnull

Location fix speed (m/s)

速度を代入する変数。速度情報が利用できない場合はnull

Location fix accuracy (m)

推定の精度情報を代入する変数。精度情報が利用できない場合はnull

Location fix timestamp

位置情報が取得された時のUNIXタイムスタンプを代入する変数。

Location fix provider

位置情報の取得方法。

使用例

dateFormat関数を利用しています。

Flow beginning{}
Location::Location get{
  Proceed : Maybe immediately
  Location provider : Balanced
  Maximum fix age = 0
  Location fix latitude : lat
  Location fix longitude : lng
  Location fix timestamp : ts
}
Interface::Dialog message{
  Title : 現在地
  Message = lat ++ "\n" ++ lng ++ "\n" ++ dateFormat(ts)
  Show_window : true
}

f:id:o-treetree:20200523095154j:plain

フローを起動すると

f:id:o-treetree:20200523095228j:plain

このように表示されます。

o-treetree.hatenablog.com

vector<pair>のソートの覚書き [C++]

なんとなくpairをソートしてみたら面白かったのでメモする。

pairにも大小関係があるのでソートできる

マクロばっかで申し訳ないがとりあえず昇順ソート

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define all(v) (v).begin(), (v).end()

vector<pii> vp;

void vpii(){
  vp.pb(mp(1,2));
  vp.pb(mp(2,3));
  vp.pb(mp(1,3));
  vp.pb(mp(2,5));
  vp.pb(mp(3,1));
  vp.pb(mp(1,2));
  vp.pb(mp(2,2));
  vp.pb(mp(2,4));
  vp.pb(mp(1,1));
  vp.pb(mp(3,2));
  vp.pb(mp(3,1));
}

int main(){
  vpii();

  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }

  cout<<"降順ソート\n";
  sort(all(vp));
  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }
}
1,2
2,3
1,3
2,5
3,1
1,2
2,2
2,4
1,1
3,2
3,1
昇順ソート
1,1
1,2
1,2
1,3
2,2
2,3
2,4
2,5
3,1
3,1
3,2

以後はmain関数のみ書き換えて提示する。

pairにも比較演算子が用意されているので単純にソートができる。

降順ソートは

int main(){
  vpii();

  cout<<"降順ソート\n";
  sort(all(vp), greater<pii>());
  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }
}
降順ソート
3,2
3,1
3,1
2,5
2,4
2,3
2,2
1,3
1,2
1,2
1,1

変なソート

first降順 second昇順

全体としてfirstを降順にしたいけどfirstが同じだったらその中ではsecond昇順になるようにソートする

ラムダ式で実装

int main(){
  vpii();

  cout<<"first降順 second昇順\n";
  sort(all(vp), [](pii a, pii b){
   return a.ff>b.ff || (a.ff==b.ff && a.ss<b.ss);
  });
  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }
}
first降順 second昇順
3,1
3,1
3,2
2,2
2,3
2,4
2,5
1,1
1,2
1,2
1,3

和の昇順 first昇順

全体としてfirst+secondの値で昇順ソート、和が等しければfirstを昇順に

int main(){
  vpii();

  cout<<"和の昇順 first昇順\n";
  sort(all(vp), [](pii a, pii b){
   return (a.ff+a.ss)<(b.ff+b.ss) || ((a.ff+a.ss)==(b.ff+b.ss) && a.ff<b.ff);
  });
  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }
}
和の昇順 first昇順
1,1
1,2
1,2
1,3
2,2
3,1
3,1
2,3
3,2
2,4
2,5

参考

AtCoder ABC138 C - Alchemist のわかりやすい解説

atcoder.jp

解説PDFわかりにくすぎてタイトルに「わかりやすい解説」って書いちゃった

問題概要

$N$ 項の数列 $ \{ v_1, v_2, v_3, \cdots , v_N \} $ がある。ここから2つの数字 $v_a, v_b$ を取り出して、その平均 $ \frac{v_a+v_b}{2} $ を戻す。

この操作を $N-1$ 回行うと数列の中身は1つになる。適切に操作を行って最後に残った数字を最大にしたとき、その最大値を求めよ

入力例2について

  • 初期数列 $\{500, 300, 200\}$
  • $300, 200$ を取り出して $(300+200)/2 = 250$ を戻す
  • $\{500, 250\}$ となる
  • $500, 250$ を取り出して $(500+250)/2 = 375$ を戻す
  • $\{375\}$ となる

このように操作して最後に $375$ が残るのが最適。

解法

数列の総和を、その数列の得点として考える。最終段階での数列の得点が最大になるようにすればいい。

1回の操作で数列の得点がどのように変化するかを考える。

取り出す数字を $y, z$ とし、操作前の得点 $P_{before}$ 、操作後の得点 $P_{after}$ を考えると

\begin{align} P_{after} &= P_{before} - (y + z) + \frac{y+z}{2} \cr &= P_{before} - \frac{y+z}{2} \end{align}

よって、毎回の操作で数列の得点は減少していく。その減少幅を最小にすれば良い。

つまり、取り出す数字 $y, z$ は数列のうち最小の2つを取れば良い。

数列を $ \{ v_1, v_2, \cdots ,x, y, z \} $ のように降順ソート済みとする( $v_1 \ge v_2 \ge v_3 \cdots x\ge y\ge z$ )。

ここで最後尾の $y,z$ を取り出してから、$(y+z)/2$ を最後尾に戻すと数列は

$$\{ v_1, v_2, \cdots ,x, \frac{y+z}{2} \} $$

となる。ここで $$x \ge y \ge \frac{y+z}{2} \ge z$$ であるから、新しくできた数列も降順ソート済みとなっている。

この操作を繰り返し、最後に初項に残った数字が求める答えである。

実装

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin>>N;
  vector<double> v(N);
  for(int i=0; i<N; i++){
    cin>>v[i];
  }

  sort(v.begin(), v.end(), greater<double>());

  while(v.size()>1){
    double y = v.back();
    v.pop_back();
    double z = v.back();
    v.pop_back();

    v.push_back((y+z)/2);
  }

  cout<<v.front()<<endl;
}

追記

Alchemist [AtCoder Beginner Contest 138 C] - はまやんはまやんはまやん を見て気づいたが、配列から「実際に取り出す」必要はなかった。昇順ソートで良いから、先頭からv[i+1] = (v[i]+v[i+1])/2としていけばよいのか。

ポイント

降順ソート

std::sortはデフォルトでは昇順でソートする。これを降順にするには

vector<int> v;
...
sort(v.begin(), v.end(), greater<int>());
vector<int> v;
...
sort(v.begin(), v.end(), [](int a, int b){
  return a > b;
});

関数オブジェクトを自作するという方法もあるそうだがちょっとわからんかったので省略。

おしまい

ラムダ式でソート順を操作するというところをメモしたかった。おしまい。

参考

プライバシーポリシー ・お問い合わせはこちら