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

DPがわからん！

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

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

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

o-treetree.hatenablog.com

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

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

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者:渡部有隆,Ozy(協力),秋葉拓哉(協力)
発売日: 2015/01/30
メディア: 単行本（ソフトカバー）

解く問題は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を含む。

2020-05-24

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

2020-05-23

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

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

参考

operator==,!=,<,<=,>,>=(std::pair) - cppreference.com

2020-05-21

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

AtCoder C++ プログラミング

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はデフォルトでは昇順でソートする。これを降順にするには

関数オブジェクトを使う greater - cpprefjp C++日本語リファレンス

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;
});

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

おしまい

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

参考

std::sort - cppreference.com