2020-12-03

ABC179 F - Simplified Reversi

Atcoder

問題

解法

各行(列)の中で、最も左(上)側にある白マスの位置を効率よく管理する。

ax[i]:i行目で最も左側にある白マスの座標
ay[i]:i列目で最も上側にある白マスの座標

入力例1での説明。初期状態では、白マスはそれぞれ行列の右下端の置かれている。

f:id:tori114:20201203004812p:plain:w400

1つの目のクエリ(1,3)を処理する。3列目の白マスで最も上側にあるのは5行目なので、 2~4行目までの黒マスを白マスに変える。その後、白マスが置かれた1~4行目に対して、axを更新する。

f:id:tori114:20201203005943p:plain:w400

2つの目のクエリ(2,3)を処理する。3行目の白マスで最も上側にあるのは3列目なので、 1~2列目までの黒マスを白マスに変える。その後、白マスが置かれた1~2列目に対して、ayを更新する。

f:id:tori114:20201203005415p:plain:w400

3番目、4番目のクエリも同様に処理する f:id:tori114:20201203010030p:plain:w400 f:id:tori114:20201203005624p:plain:w400

全体の黒マスから白マスになった個数を引いていけばOK

コード

int op(int a, int b){
  return min(a,b);
}

int e(){
  return (int)(1e9);
}

int main() {
  ll n,q;
  cin >> n >> q;
  atcoder::segtree<int, op, e> ax(n+1),ay(n+1);
  ax.set(n,n);
  ay.set(n,n); 
  ll ans = (n-2)*(n-2);
  while(q--){
    int t,p;
    cin >> t >> p;
    if(t == 1){
      int r = ax.prod(p,n+1);
      ans-=r-2;
      ay.set(r, min(ay.get(r),p));
    }
    else{
      int r = ay.prod(p,n+1);
      ans-=r-2;
      ax.set(r, min(ax.get(r),p));
    }
  }
  cout<<ans<<endl;
  return 0;
}

2020-11-29

ABC183 F - Confluence

Atcoder

問題

atcoder.jp

解法

生徒の合流をUnionFind木で管理する。

各生徒の集合状態をmapで管理し、生徒たちが合流したときにmapをマージする。このとき、mapの小さいほうから大きいほうへマージすることで、マージに必要な計算量を抑えることができる。

「データ構造をマージする一般的なテク」と呼ばれるらしい。証明はこちら記事が参考になりました。データ構造をマージする一般的なテク

コード

struct UnionFind {
  vector< int > data;
  vector<map<int,int>> mp;
 
  UnionFind(int sz) {
    data.assign(sz, -1);
    mp.assign(sz, map<int,int>());
  }
  int root(int x) {
        if (data[x] < 0) return x;
        else return data[x] = root(data[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    for(auto it : mp[y]){
      mp[x][it.fi]+=it.se;
    }
    mp[y] = map<int,int>();
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }
 
  int size(int k) {
    return (-data[find(k)]);
  }
};

int main() {
  int n,q;
  cin >> n >> q;
  vi C(n);
  UnionFind tree(n);
  rep(i,n){
    cin >> C[i];
    C[i]--;
    tree.mp[i][C[i]]=1;
  }
  while(q--){
    int type,a,b;
    cin >> type >> a >> b;
    a--;b--;
    if(type == 1) tree.unite(a,b);
    else cout<<tree.mp[tree.find(a)][b]<<endl;
  }
  return 0;
}

2020-11-29

ARC109 C - Large RPS Tournament

Atcoder

問題

atcoder.jp

解法

メモ化しながら再帰的に解く。

s="RPS", k=4の例。トーナメント参加者の出す手は文字列sを周回して決まっていくため、同じパターンが出現する。 f:id:tori114:20201129160907p:plain テーブルを以下のように定義し、一度計算した値を格納していく。

dp[k][i] = f(dp[k-1][i],dp[k-1][i+2^(k-1)]);
//f(a,b):aとbがじゃんけんして勝った手

2^(k-1)の部分はkが大きい場合にオーバフローしてしまうので、modを取って前計算しておく。

コード

string s;
int n,k;
vector<vector<char>> dp;
vector<int> pow2;

bool comp(char a, char b){
  if(a == 'R') return (b == 'S');
  if(a == 'S') return (b == 'P');
  else return (b == 'R');
}

char f(char a, char b){
  if(comp(b,a)) return b;
  else return a;
}


char dfs(int k, int i){
  if(k == 0) return s[i];
  if(dp[k][i] != '?') return dp[k][i];
  char L = dfs(k-1,i);
  char R = dfs(k-1,(i+pow2[k-1])%n);
  return dp[k][i] = f(L,R);
}

int main() {
  cin >> n >> k;
  cin >> s;
  pow2.assign(n+1,1);
  rep(i,n)pow2[i+1]=pow2[i-1]*2%n;
  dp.assign(k+1,vector<char>(n+1,'?'));
  char ans = dfs(k,0);
  cout<<ans<<endl;
  return 0;
}

2019-03-16

Ubuntu16.04でRealSenseD435iを動かす

音楽系

友人に「せかいブログ更新しろよ〜」と言われたので、渋々記事を書いています。（ブログ向いてないかもしれない）

今回は、勢いに任せて買ってしまったRealSenseD435iをとりあえず動かすところまでやりたいと思います。

環境

Ubuntu 16.04
~~Macbook Pro Mojave 10.14~~

初めはMacで繋ごうとしていましたが、MacではRealsense-viewer内でD345iを認識できなかったので断念しました...

手順

ドキュメントの通りに必要なものを入れていきます。

サーバのpublickeyの登録

sudo apt-key adv --keyserver keys.gnupg.net --recv-key C8B3A55A6F3EFCDE || sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv-key C8B3A55A6F3EFCDE

レポジトリの登録

Ubuntu16.04

sudo add-apt-repository "deb http://realsense-hw-public.s3.amazonaws.com/Debian/apt-repo xenial main" -u

Ubuntu18.04

sudo add-apt-repository "deb http://realsense-hw-public.s3.amazonaws.com/Debian/apt-repo bionic main" -u

ライブラリのインストール

sudo apt-get install librealsense2-dkms
sudo apt-get install librealsense2-utils

PCにrealsenseを接続後、コマンドからviewerを起動

realsense-viewer

f:id:tori114:20190316221257p:plain

無事起動できました。次回以降、人物切り抜きに挑戦してみたいと思います。

2018-10-21

帰宅するとSpotifyのプレイリストをランダムで自動再生するシステムを構築してみる

音楽系

Pythonを用いてSpotifyのプレイリストを作成＆再生してみるの続き。

前回は、Spotifyのプレイリストを自動で作成＆再生するプログラムを作りました。しかしながら、プレイリスト再生の度にPCを起動して、そこからプログラムを実行するのは面倒です。そこで今回は

Amazon Web Service(AWS)
IFTTT

これらの２つのサービスを利用して、帰宅すると自動的に音楽を再生システム を実現します。

事前準備

先に、以下の2つのサービスのアカウント作成を済ませておきましょう。

AWSアカウントの作成
IFTTTアカウントの作成

AWSの利用にはクレジットカード情報の登録が必要です。登録後12ヶ月間は無料であれこれ使うことができますが、期間を過ぎるとサービス利用料が発生します。料金の仕組みは色々あって自分も混乱していますが、

通信量
関数の呼び出し回数

などによって決まるみたいです。今回の場合は、通信量も呼び出し回数も非常に少ないため、多くても数十円/月ぐらいだと思います。心配な方はAWSの料金について調べておきましょう。

AWSの設定

AWSでは、LambdaとAPIGatewayの２種類のサービスを用います。各サービスは、ざっくり言うと以下の役割を持ちます。

Lambda
自作したプログラムをLambda関数としてアップロードして置く場所
APIGateway
Lambda関数をAWS以外のWebサービスからもアクセスできるようにするためのもの

APIGatewayの設定

まずAWSのコンソールにアクセスし、検索ボックスからLambdaを検索します。

f:id:tori114:20181020233941p:plain

画面から、「新しい関数を作成」ボタンを押します。

f:id:tori114:20181020234127p:plain

関数名、ロールを設定すると次の画面へ遷移します。

f:id:tori114:20181021153707p:plain

左のタブから、APIGateWayを選択し、Lambda関数のトリガーにセットします。セットが完了すると、Lambda関数へのエンドポイントが作成されます。このURLを外部サービスから叩くことによって、関数が実行するような仕組みです。 f:id:tori114:20181104201338p:plain

このエンドポイントは後に使用するので、どこかに控えておきましょう。

Lambdaの設定

次に、Lambda関数の中身をアップロードしていきます。今回は、自分がSpotifyに登録しているプレイリストの中から、ランダムに１つ選んで再生するプログラムです。大まかな内容は前回と同じですが、ソースコードが見辛かったのと、Lambda用に改変する部分があったので修正しています。

まず、作業ディレクトリを作成します。

mkdir workspace
cd workspace

次に、以下のプログラムをlambda_function.pyという名前で保存します。

import spotipy
import spotipy.util as util
import random
import subprocess
import requests
import json
import os
from datetime import datetime

class PlaySpofity:

    def __init__(self, username, scope):


        self.username = username
        self.scope = scope

        self.token = util.prompt_for_user_token(self.username, self.scope)
        self.spotipy = spotipy.Spotify(auth=self.token)
        self.header = {'Authorization': 'Bearer {}'.format(self.token)}

        self.device_id = self.get_deviceid()
        self.playlist_id = None

    def get_deviceid(self):
        res = requests.get(
            "https://api.spotify.com/v1/me/player/devices",headers=self.header)
        devices = res.json()
        try:
            device_id = devices["devices"][0]['id']
        except IndexError:
            print("IndexError: Device did not found")
            exit()
        return device_id

    def generate_playlist(self, playlistname):
        playlist = self.spotipy.user_playlist_create(self.username, playlistname)
        playlist_id = playlist['id']
        return playlist_id

    def make_playlist(self, search_artist, playlistname="default"):
        self.make_playlist = self.generate_playlist(playlistname)
        artist_id_map = {}
        print (playlistname)
        if search_str == None:
            raise TypeError('Favorite artist is None')
        result = self.spotipy.search(q='artist:'+search_artist, limit=1)
        artist_id = result['tracks']['items'][0]['artists'][0]['id']
        print(result['tracks']['items'][0]['id'])
        artist_related_artists = self.spotipy.artist_related_artists(artist_id)
        track_ids = []
        for artist_list in artist_related_artists['artists']:
            result = self.spotipy.search(q='artist:'+artist_list['name'], limit=50)

            if len(result['tracks']['items']) > 1:
                track_ids.append(random.choice(
                    result['tracks']['items'])['id'])

        self.spotipy.user_playlist_add_tracks(username, self.playlist_id, track_ids)

    def random_select_playlist(self):
        current_playlists = self.spotipy.current_user_playlists(limit=50)
        playlist = random.choice(current_playlists['items'])
        return playlist

    def play_playlist(self, playlist_id):
        param = {'device_id': self.device_id,
             'context_uri': 'spotify:playlist:%s' % playlist_id}
        res = requests.put("https://api.spotify.com/v1/me/player/play",
                           data=json.dumps(param), headers=self.header)

def logging(errorLv, lambdaName, errorMsg):
    loggingDateStr=(datetime.now()).strftime('%Y/%m/%d %H:%M:%S')
    print(loggingDateStr + " " + lambdaName + " [" + errorLv + "] " + errorMsg)
    return


def lambda_handler(event, context):

    username = os.getenv('SPOTIFY_USERNAME')
    scope = os.getenv('SCOPE')

    sp = PlaySpofity(username, scope)
    playlist = sp.random_select_playlist()
    sp.play_playlist(playlist['id'])

    return {
            'isBase64Encoded': False,
            'statusCode': 200,
            'headers': {},
            'body': '{"message": "PlaySpofity was executed"}'
    }

if __name__ == '__main__':
    username = os.getenv('SPOTIFY_USERNAME')
    scope = os.getenv('SCOPE')
    sp = PlaySpofity(username, scope)
    playlist = sp.random_select_playlist()
    sp.play_playlist(playlist['id'])

次に、Lambdaの中でspotipyとrequestsライブラリを使用するために、作業ディレクトリ内にライブラリを配置します。

pip install spotipy requests -t

次に、bashrcに以下の項目をセットしましょう

$ vi ~/.bash_profile
export SPOTIPY_CLIENT_ID='XXXX'
export SPOTIPY_CLIENT_SECRET='XXXX'
export SPOTIPY_REDIRECT_URI='http://example.com'
export SPOTIFY_USERNAME='XXXXXXXXX'
export SCOPE='user-read-playback-state,playlist-read-private,user-modify-playback-state,playlist-modify-public'

Lambdaにアップロードする前に、ローカルでプログラムを実行します。

python lambda_function.py

実行すると、http://example.comがブラウザで開かれます。このURLを丸ごとコピーして、コンソールに貼り付けます。この手順を踏むことで、Spotifyの認証に必要な情報(access_token等)が、

.cache-XXXXXX

としてlambda.pyと同じディレクトリに保存されます。隠しファイルのままではlambdaにアップロード出来ないので、

mv ./.cache-XXXXXX cache-XXXXXX

とします。また、 spottily/util.py内の50行目を

cache_path=".cache-"....

cache_path="cache-"

と変更します。

プログラムが無事実行されると、Spotifyのプレイリストが紐づいているデバイス上で再生されます。

ディレクトリ内をzipファイルにまとめます。

zip -r lambda.zip *

このzipファイルを、Lambdaにアップロードします。
コードエントリータイプから.zipファイルをアップロードを選択し、先ほどのLambda.zipをアップロードします。

f:id:tori114:20181021153433p:plain

最後に、Lambdaにもbash_profileと同じ環境変数をセットしましょう。

キー	値
SPOTIPY_CLIENT_ID	'XXXX'
SPOTIPY_CLIENT_SECRET	'XXXX'
SPOTIPY_REDIRECT_URI	'http://example.com'
SPOTIFY_USERNAME	'XXXX'
SCOPE	'user-read-playback-state,playlist-read-private,user-modify-playback-state,playlist-modify-public'

これでLambdaの設定は完了です。

IFTTTの設定

次に、作成したLambda関数のエンドポイントを叩くために、IFTTTと呼ばれるWebサービスを用います。 IFTTTは、「If This Then That」の頭文字を撮ったもので、系統の異なるWebサービスやデバイスを繋げて、システムを作ることができます。今回は、

入力：スマートフォンの位置情報
出力：webhook(Lambda関数のエンドポイントを叩く)

となるようなシステムを作ります。

まず、IFTTTにアクセスします。

f:id:tori114:20181021154553p:plain

左上のMyAppletをクリックし、リンク先の右上にあるNewAppletをクリックします。 +thisを選択し、検索ボックスにlocationを打ち込み、選択します。

f:id:tori114:20181021153504p:plain

You enter an areaを選択すると、次のようなページに移動するので、ここで自宅の場所を選択します。

f:id:tori114:20181021153513p:plain

この選択した場所に入ることが、システムの入力となります。選択後、下のCreate Triggerをクリック、次に+thenの設定へと進んでいきます。検索ボックスから、Webhookを選択します。 Make a Web Requestを選択すると、次のページに移ります。

f:id:tori114:20181021153411p:plain

URL : APIGateway設定の際に控えたURL
Method : GET
Content type : 適当

設定の方はこれで完了です。あとはIFTTTのスマートフォンアプリをDLし、ログインをしておくことで実行可能になります。

Point

構築したシステムの動作を確かめる場合、スマートフォンを持って自宅付近をうろつき回るのは面倒です。その場合、Locationの代わりにbutton widjetを選択することで、スマートフォンのボタンウィジェットにIFTTTのボタンを作成することができます。

まとめ

今回は、帰宅するとSpotifyのプレイリストを自動再生するためのシステムを作りました。

2018-10-14

Pythonを用いてSpotifyのプレイリストを作成＆再生してみる

音楽系

今回は、PythonからSpotifyのAPIを叩いてみます。まず前提条件として、SpotifyのPremium会員への登録が必要です。

実行環境

Python 3.7.0

Cliend IDの取得

My Dashboard | Spotify for Developersへアクセスします。Create An APPから必要な情報を入力すると以下のページにアクセスできます。

「Show Client Secret」をクリックし、Cliend IDとClient Sercretをメモします。
また、「Edit Setting」ボタンからRedirect URIs にhttp://example.comを追加し、「Save」ボタンを押して保存しておきます。 f:id:tori114:20181014073045p:plain

Python側の準備

今回は、Spotipyと呼ばれるライブラリを用いてアーティストの検索などを行なっていきます。まずは、
pip install spotipy
でspotipyをインストールします。名前がややこしいので注意してください。

次に、環境変数にSpotifyのClient ID、Client Secret、Redirect URIを登録します。今回はbash_profileに記述しておきます。

$ vi ~/.bash_profile
export SPOTIPY_CLIENT_ID='XXXX'
export SPOTIPY_CLIENT_SECRET='XXXX'
export SPOTIPY_REDIRECT_URI='http://example.com'

プレイリストの自動生成と再生

では実際にプログラムの方に入っていきます。今回の大まかな仕様は以下の通りです。
1. 自分の好みのアーティストを一人選択する。
2. artist_related_artistsを用いて、選択したアーティストと関連性の高いアーティスト群を抽出する。
3. 関連アーティスト群からそれぞれ1曲1ずつランダムに選択し、プレイリストを作成する。
4. Spotifyと連携しているデバイスで再生する。

Spotidyと連携できるデバイスとして、個人的にはSONOS ONEがオススメです。ワイヤレススピーカーなので部屋のどこにでも置けるのが魅力的。音質も良く、セットアップも簡単、さらに最近IFTTT対応したというのがポイントですね。次回は、このプログラムをIFTTT経由で動かしてみたいところ。

Sonos One スマートスピーカー Amazon Alexa搭載ブラック

出版社/メーカー: Sonos
発売日: 2018/10/01
メディア: エレクトロニクス
この商品を含むブログを見る

プログラムと実行

実行コマンドは以下の通りです。
python main.py [アーティスト名]
実行すると初回のみ Enter the URL you were redirected to: と聞かれ、ブラウザでRedirectURIが開かれます。 URLをコピーし、そのままターミナルに貼り付ければOKです。

Point

デバイス情報と楽曲の再生はrequestsを用いて直接HTTPリクエストを送っています。spotipyから呼び出す関数が見当たりませんでした。(よくよく探せばあるのかもしれません。)
device_id = devices["devices"][0]['id']の部分で、0番目のデバイスIDを取得しています。Spotifyと連携しているデバイスを複数お持ちの人は、数字を変えて自分が再生したいデバイスを選択して下さい。
usernameは自身のユーザー名に置き換えてください。確認方法は色々あると思いますが、自分はiPhoneのSpotifyアプリから「My Library > 右上の歯車 > アカウント」で確認しました。

import spotipy
import spotipy.util as util
import sys
import random
import subprocess
import requests
import json
username = "XXXX"
scope = 'user-read-playback-state,playlist-read-private,user-modify-playback-state,playlist-modify-public'
search_str = sys.argv[1]

artist_id_map={}
token = util.prompt_for_user_token(username, scope)

sp = spotipy.Spotify(auth=token)
header = {'Authorization': 'Bearer {}'.format(token)}


res = requests.get("https://api.spotify.com/v1/me/player/devices", headers=header)
devices = res.json()
device_id = devices["devices"][0]['id']

playlist = sp.user_playlist_create(username,"NewPlaylist")
playlist_id = playlist['id']

result = sp.search(q='artist:'+search_str, limit=1)
artist_id = result['tracks']['items'][0]['artists'][0]['id']
print (result['tracks']['items'][0]['id'])
artist_related_artists = sp.artist_related_artists(artist_id)
track_ids = []
for artist_list in artist_related_artists['artists']:
    result = sp.search(q='artist:'+artist_list['name'], limit=50)

    if len(result['tracks']['items']) > 1:
        track_ids.append(random.choice(result['tracks']['items'])['id'])

sp.user_playlist_add_tracks(username, playlist_id, track_ids)

param = {'device_id':device_id,
         'context_uri':'spotify:playlist:%s' % playlist_id}

res = requests.put("https://api.spotify.com/v1/me/player/play", data=json.dumps(param), headers = header)

まとめ

今回、Pythonを用いてSpotifyのAPIを叩いてみました。途中手こずる場面もありましたが、無事Playlistの自動生成と指定したデバイスで再生できるようになりました。
次回は、このIFTTTと呼ばれるWebサービスと連携させてみようと思います。

参考

Documentation | Spotify for Developers
Welcome to Spotipy! — spotipy 2.0 documentation

せかいの世界（備忘録）

音楽・ITに関する色々なものを触ってみたり、競プロの記録を残したりします。

ABC179 F - Simplified Reversi

問題

解法

コード

ABC183 F - Confluence

問題

解法

コード

ARC109 C - Large RPS Tournament

問題

解法

コード

Ubuntu16.04でRealSenseD435iを動かす

環境

手順

帰宅するとSpotifyのプレイリストをランダムで自動再生するシステムを構築してみる

事前準備

AWSの設定

APIGatewayの設定

Lambdaの設定

IFTTTの設定

Point

まとめ

Pythonを用いてSpotifyのプレイリストを作成＆再生してみる

実行環境

Cliend IDの取得

Python側の準備

プレイリストの自動生成と再生

プログラムと実行

Point

まとめ

参考