YKpages

ロボット分野で勉強したことのまとめ

競技プログラミングで覚えておきたいこと ( C++ )

目次

はじめに

競技プログラミング(競プロ)を少しやってます。 競プロの問題を解いていく中で「これってこうするんだな~」みたいに思うことがちょこちょこ出てきたので、 忘れないようにまとめていきたいと思います。

使用する言語はC++です。C++は初心者なので間違っていたらすみません。 また、競プロで問題を解くためのコードなので一般的ではない可能性があります。

ちなみに、よく参加しているコンテストはAtCoderです。

ちょっとしたこと編

C++のヘッダファイル

とりあえず以下の5つを読み込んでいます。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

gccだと標準ライブラリを一括で読み込むことができるらしいです(使ってないのでよく分かってないです)。

#include <bits/stdc++.h>

qiita.com

名前空間

普段これを書くと怒られるかもしれないけど競プロなら大丈夫なはず。

using namespace std;

qiita.com

1000000007

AtCoderではたまに以下のようなことを言われます。

「答えが大きくなるかもしれないから1000000007で割った余りを出力してね」

そんなときはこのように書くといいみたいです。

const long long mod = 1e9+7; //1×10の9乗 + 7

ちなみに1000000007は素数らしいです(素数だからこそ?)。

typedef

長い型名を何回も書くのはしんどい、そんなときは短い名前を付けてもいいかも(可読性とトレードオフ?)。

typedef long long ll;
typedef unsigned int UINT;

非常に大きな値(または小さな値)

たまに大きな値(小さな値)が必要になるときがあります(初期値に与えるときなど)

long long int a = (1<<30);
long long int b = -(1<<30);

以上の例ではビットのシフトを行っています(30回左にシフト)。

ソート(sort)

sortを使えば計算量O(NlogN)でソートできるようです

#include <algorithm>
// 昇順ソート
sort(v.begin(), v.end());

// 降順ソート
sort(v.gegin(), v.end(), greater<int>());

cpprefjp.github.io

二つの配列を同時にソート(pair)

pairを使うと二つの配列を一緒にソートできます。

vector<pair<int, int>> p;
for(int i = 0; i < N; i++)
{
    int a, b;
    cin >> a >> b;
    p.push_back(make_pair(a, b));
}
sort(p.begin(), p.end());

注意点として、このソートではp.firstを元にソートされます。 そのためソートしたいほうをp.firstに入れます。

ちなみに、pairは以下のように値にアクセスできます。

p[0] = make_pair(1, 2);
cout << p[0].first << endl;    # 1
cout << p[0].second << endl;    # 2

桁数を指定して出力

AtCoderではたまに以下のようなことを言われます。

「絶対誤差または相対誤差が10のマイナス9乗以下の精度で解を出力してね」

この場合、小数点以下の桁数を指定して出力する必要があるかもしれません。

そうなったら、まずiomanipの読み込みます。

#include <iomanip>

そしてこう書きます(ansが出力したい解です)。

cout << setprecision(10) << ans << endl; //10桁出力

これで誤差も怖くありませんね。 qiita.com marycore.jp minus9d.hatenablog.com

実装編

全通りの探索(ビットシフトを使ったやつ)

ABC-080のC問題などで使いました。

2のN乗通りをすべて探索することができます。 コードを見ただけではどうなっているのか分かりづらいので、 実際に実行してどういう出力をするのか確認するといいと思います。

ちなみに、'&'はビット演算子の一つで二つのビットが両方とも1だった場合のみ1を返します。

for(int i = 0; i < (1<<N); i++) // 0 <= i < 2のN乗
{
    for(int j = 0; j < N; j++)
    {
        if(i>>j&1) // あるビットが1(true)か0(false)かを調べている
        {
            //処理
        }
    }
}

qiita.com www9.plala.or.jp

最大公約数と最小公倍数

最大公約数(GCD)の求め方はこうです。

int gcd(int a, int b) # a > b
{
    if(b == 0) return a;
    return gcd(b, a % b);
}

最小公倍数(LCM)の求め方はこうです。

a * b / GCD

しかし、a, bが大きい値の場合、a * bをするとオーバーフローする可能性があります。 そのため以下のように実装します。

a / GCD * b

コードは以下のように書きます。

int main()
{
    int A, B;
    cin >> A >> B;    # A > B
    int G = gcd(A, B);    # 最大公約数
    int L = A / G * B;    # 最小公倍数
}

qiita.com

アルゴリズム

累積和

まだです

しゃくとり法

まだです

その他参考

www.slideshare.net misawa.github.io

おわりに

これから追記していきます(忘れそう)

追記記録

2019/06/20 記事のバランス調整、「ビット全探索」を追記

2019/06/19 「大きな値」「ソート」を追記

2019/06/11 「桁数を指定して出力」を追記

2019/06/09 first

GitHub でリポジトリを管理するためのメモ(初期設定)

はじめに

GitHub はかれこれ4年以上使ってる。 それなのに新しくリポジトリを作ろうとするたびに、 「どうやるんだっけ?」と思ってググってるからそろそろメモを残しておく。

環境

  • Mac OS
    • ターミナルからコマンドでやる
  • Ubuntu 16.04 LTS
    • ターミナルからコマンドでやる

WindowsGitHub Desktop アプリを使う場合は以下の設定は不要

参考

以下の記事を参考にした。ありがたい。

qiita.com

zaki0929.github.io

GitHub で新しいリポジトリを作成

github.co.jp

  1. アカウントがない人はまずはアカウントを作成
  2. 新しくリポジトリを作成(Repositories で「New」ボタンを押すと作成できる)
  3. このときに、README.md、License、.gitignore を必要ならば作成する
  4. Public か Private かも選択

ssh で接続するための鍵を作成

UbuntuMac でコマンドからやるなら必要(GitHub Desktop アプリなら必要ないはず)

  1. 鍵を作成(すでに鍵を作っていた場合、上書きすることになるので注意)
  2. 表示した公開鍵をコピー
ssh-keygen
cat ~/.ssh/id_rsa.pub

作成した鍵を登録

  1. GitHub上 で Setting > SSH and GPG keys を選択
  2. 「New SSH key」ボタンを押す
  3. 適当な名前を付けて、さっきコピーした公開鍵をペースト

ローカル環境の設定

  1. まずは設定を確認
git config --global --list
  1. GitHub に登録しているユーザ名とメールアドレスを設定
git config --global user.name UserName
git config --global user.email sample@sample.com

ローカルリポジトリの設定

  1. GitHub で管理したいリポジトリを用意
  2. そのリポジトリcd で移動
  3. 以下のコマンドをうつ
git init
git remote add origin git@github.com:UserName/RepositoryName.git

push する

git add -A
git commit -m "message"
git push origin master

もし、すでに管理していたリモートリポジトリだった場合は先に pull する

git pull origin master

443ポートを使う場合

何かしらの理由により、443ポートを使う必要がある場合

 vim ~/.ssh/config
Host github.com
    HostName ssh.github.com
    Port 443
    IdentityFile ~/.ssh/id_rsa

よく使うコマンド

git config --global --list
git status
git add -A
git add FileName
git commit -m "message"
git push origin master
git pull origin master

おわりに

GitHub は本当に便利なので、 使い方をしっかり覚えておきたい

今のところの vimrc

はじめに

ここ二年間くらい Vim を使ってい続けていて他のエディタが使えなくなった。つらい。

今使っている vimrc を置いておく。 たいして変わったことのない最低限の vimrc 。

参考

以下の記事を参考。ありがたい。

qiita.com

qiita.com

wonderwall.hatenablog.com

vimrc

"文字コードをUTF-8
set fenc=utf-8

"Tabの設定
set tabstop=4
set shiftwidth=4
set noexpandtab
set list listchars=tab:\>\-

"インデント
set autoindent
set smartindent

"Vimの色を設定
colorscheme darkblue

"シンタックスハイライト
syntax enable

"検索
set hlsearch
set incsearch
set ignorecase
set smartcase
set wrapscan

"Vi互換ではない
set nocompatible

"バックアップ、スワップファイルを作らない
set nobackup
set noswapfile

"行と列を強調
set cursorline
set cursorcolumn

"ビープ音の設定
set visualbell
set vb t_vb=

"その他
set hidden
set showcmd
set showmatch

おわりに

Vim は特に使いやすいとは思っていなかったけど、 なんやかんや使い続けているので、 より便利になるように試行錯誤していきたい。

WSL ( Windows Subsystem for Linux ) インストールしてみた

はじめに

Windows 上で Linux が動く「WSL」が便利らしいのでやってみた。

目次

環境

Windows 10 Home

インストールまでの流れ

以下の記事を参考。ありがたい。

qiita.com

WSL のインストール

  1. スタートボタンを右クリック -> 「アプリと機能」を選択
  2. 設定ウィンドウの右上にある「プログラムと機能」をクリック
  3. 左にある「Windowsの機能の有効化または無効化」をクリック
  4. 一覧から「Windows Subsystem for Linux」を探してチェック ->「 OK」をクリック
  5. インストール後に再起動

Ubuntu 16.04 LTS をインストール

Windows Store で「Ubuntu」と検索。

Ubuntu」、「Ubuntu 16.04 LTS」、「Ubuntu 18.04 LTS」が出てくるから、 その中で「Ubuntu」をインストールした。 みたところ「Ubuntu 16.04 LTS」。

初期設定: とりあえずこのコマンドをうつ

sudo apt update
sudo apt upgrade
sudo apt install vim-nox

ターミナルの色を変更

デフォルトのままだと色が見にくかったので変更してみた。

以下の記事を参考。ありがたい。

www.lisz-works.com

github.com

console.zip をダウンロードして展開

コマンドプロンプトを開いて、console.exe があるディレクトリまで移動

そこで以下のコマンドを実行

そのあと、もう一度ターミナルを開きなおすと色が変更されている

colortool -d OneHalfDark

また、ls でディレクトリの色がおかしかったが、 以下の記事を参考にして直せた。ありがたい。

typea.info

qiita.com

コピペできるようにする

  1. ターミナルの上部を右クリック -> プロパティを選択
  2. オプション -> 編集オプション -> 簡易編集モードにチェック

これで右クリックするとコピペができる

Windows 側のディレクトリにアクセス

以下の記事を参考。ありがたい。

www.lisz-works.com

以下のコマンドで Windows の Cドライブへ移動できる

cd /mnt/c/

移動するディレクトリが決まっている場合は、aliasを設定するとよい。

bachrcに書き込む

vim ~/.bashrc

例えば以下のように。

alias cdc='/mnt/c/'

このように書くと、 「cdc」とコマンドを入力すると移動できる

まとめ

WSL をインストールして、さらに Ubuntu 16.04 LTS をインストールした。

おわりに

15分ほどでUbuntu のインストールができて感動した (もしかしたらもっとかかったかも)

MTGアリーナをやってみた感想( MTG ARENA , Magic : The Gathering Arena )

目次

はじめに

「Magic : The Gathering Arena(MTGアリーナ)」の日本語版が実装されたらしいのでやってみた。 小中学生のころ以来にカードゲームでわくわくしたので、その勢いだけでこの記事を書いている。 MTGをやっていたのは中学生が最後。ルールもうろ覚え。

公式サイトのリンク(日本語サイト)。

mtg-jp.com

分かりやすく情報がまとめられているサイト。 ありがたい。

mtg.taiken.online

きっかけ

MTGアリーナを知ったきっかけは、 ゲーム実況をやっている牛沢さんの動画。 おもしろいのでおすすめ。

この動画で、 MTGアリーナの存在も、 日本語版が実装されたことも、 初めて知った。

youtu.be

youtu.be

MTGアリーナを始めるまでの簡単な流れ

一応、MTGアリーナの始め方を書いておく。 簡単なのですぐに始められる。

まずはゲームのインストール。 環境がWindowsに限られることに注意。

公式サイトからインストールできる。

mtg-jp.com

インストールしたら起動。

新規でアカウントを作成する。 メールアドレスがあれば大丈夫。

ゲームが始まるとすぐにチュートリアルが始まる(とばすこともできる)。

以上。

感想(本題)

MTGアリーナをやってみた感想(本題)。

とりあえず、「めちゃくちゃおもしろい」の一言。

やっぱりカードゲームはおもしろい。 いろんなカードがあって、 いろんな戦略があって、 だけど、ただ勝つだけではなくて、 好きなカードで勝ちたいというロマンがある。

MTGアリーナはカードの絵柄も良いし、 音楽も良いし、 エフェクトも出るし、 いろいろ楽しい。

小中学生の頃にカードゲームで遊んでいた記憶がどんどん蘇ってくる。 遊戯王とかデュエルマスターズとか、 ヴァイスシュヴァルツポケモンカード、 いろいろなことを思い出す。 懐かしい。

MTGアリーナを数時間やってみただけでも、 「やって良かった」と感動するくらい良かった。 ばりばり課金してもいいかなとも思う。 と言ってもあんまりお金ないから、 何回かドラフトをやれるくらいかも。

おすすめの動画

新米MTGさんの動画。

MTGアリーナの実況動画とか、 MTGのルール説明などをあげている方(それ以外にもいろいろ)。 話し方が優しくて、話も分かりやすい。 そしておもしろい。

youtu.be

youtu.be

ストーリーを読む

MTGの雰囲気が好きなので、 ストーリーを読みたいなと思って探したら、 ちゃんと公式にあった(日本語に翻訳されたものもある)。 全部あるわけではないらしいけど、 とりあえず読んでみる。 MTGはカードゲームだけど、 ストーリーもしっかりしていて素晴らしい。

mtg-jp.com

magic.wizards.com

こっちが英語の公式サイト。

magic.wizards.com

あと、いろいろまとめてくれている記事。 ありがたい。

mtg.taiken.online

課金と初めてのドラフトをやってみた(追記:2019/3/7)

さっそく課金してみた。 一度だけ購入できる「5ドルでパック5つと2500ジェル」のやつ。

そしてさっそくドラフトへ。 やったのはイクサランの相克のやつ(750ジェル)。 正直、初めてで何にも分からない。

説明文に「一枚ずつ選んでデッキを組んでね」みたいなことが書いてあったから、 とりあえず好きなカードを選んでいった(さすがに色は合わせた)。

そして終盤の方でやっとのこと、 吸血鬼、海賊、恐竜、昇殿、などの共通したキーワードがあることを理解した。 だけどもう遅い。よく分からない白黒デッキができた。バランスが悪い。 何よりも決め手が無さすぎるから、 欲しかったから選んだだけの「ガルタ」を無理やり入れた。

そしてバトルへ。

やっぱりみんなちゃんとデッキ組んでるんだな、 と思いながら戦った。 何もできないとまで行かなかったけど、 勝ち筋はほとんどなかったと思う。

結果として三連敗。

でも楽しかった。 いろいろ学べることが多かった良い経験。

そして、一番面白かったのが、 その三戦のすべてで初期手札に「ガルタ」が来たこと。 そういう仕様なのかと思った。

ガルタが出せそうなバトルもあったんだけど、 操作ミスで出せなかったりした。 (好きな色のマナを選択するところで、ダブルクリックしたら違う色選んだ。 あと、単純に土地の枚数を数え間違えたりした)

三連敗したけど楽しかったから良い。

次やる前にこの動画でちょっと勉強しておく。

youtu.be

二回目のドラフト(追記:2019/3/10)

この前やった「イクサランの相克」ランク戦ドラフト。 やり方は分かったからもう一度挑戦した。

今回は初めから青黒の海賊を作るつもりでピック。 そして飛行メインのデッキになった(海賊集めたけど、海賊が主力ではなかった)。

しかし、結果的に6勝。 前回の三連敗から大きな成長があった。

ジェルの元も取れてランクもガンガン上がって良かった。

三回目以降のドラフト(追記:2019/3/12)

今のところ6回くらいランク戦ドラフトをやった。 勝率は平均で4勝くらい。 自分としては悪くはない。 もうちょっとでゴールドに上がれるくらい。

そろそろジェルが尽きるからどうしようかなという感じ。

おわりに

ということで本当にただ感想を書いただけで、 しかもたいして内容がない記事になってしまった。 それでもMTGがおもしろいことには変わりない。

あんまり勝ちにこだわりはないから(もちろん勝つに越したことはない)、 ただただ楽しんでMTGアリーナをやっていこうと思う。

あと、ほぼ初心者なので何かあれば教えてください。 ゲームのこととか、MTGのストーリーのこととか。

Cygwin を使いやすいようにちょっと設定してみる

目次

やること

  • ホームディレクトリを変更
  • ターミナルの見た目、文字サイズなどを変更
  • 簡単にパッケージをインストールできる「apt-cyg」をインストール
  • Cygwin について

はじめに

Cygwin で例えばデスクトップに移動する場合、以下のようにコマンドを入力する。

cd c:Users/"username"/desktop

毎回、コマンドを入力するのは面倒なのでホームディレクトリを変更したい。

あとは、デフォルト設定では文字が小さかったり、 なじみのないフォントだったりするのでこれも変更したい。

さらに、Vim とか使いたいとき、簡単にインストールできるようにするために、 「apt-cyg」をインストールする。

環境

それぞれのバージョンは、

指定する場合
cygcheck -c cygwin
全部
cygcheck -c

で確認できる。

本文

ホームディレクトリの設定

参考。

umashika5555.hatenablog.com

ユーザ環境変数でホームディレクトリを設定する。

* これからやる設定を行うと他のソフトウェアにも影響が出るかもしれないので気をつける (環境変数でホームディレクトリを設定すると他のソフトでもこれを参照するかも)

「コントロールパネル > システムとセキュリティ > システム > システムの詳細設定」の順に進むと、 「システムのプロパティ」ウィンドウが開く。

次に「環境変数」の設定ウィンドウを開き、 「ユーザ環境変数」で「新規」、またはすでにある場合は「編集」を押す。

そして以下のように設定。

  • 変数名:HOME
  • 変数値:c:Users/"username"/desktop/

* "username" は自分のユーザ名。

ターミナルの設定

Cygwin では「mintty」というターミナルが使用されているみたい(ターミナルの種類とかよく知らない)。

ターミナル上で右クリックして「Options」を選択。

「Looks」で文字色や背景色、カーソルの色を変更できる。 また、「Transparency」を設定するとターミナルを透過させられる。

「Text」で文字の大きさやフォントの種類を変更できる。 大きさは「12px」くらい、フォントは「MS ゴシック」とかにすると見やすい。

「Window」でウィンドウのサイズを変更できる。 デフォルトでは Columns:80、Rows24、 これを Columns:120、Rows36、にすると見やすい。

また、設定例として以下の記事があるみたい。なるほど。

koturn.hatenablog.com

apt-cyg をインストール

以下の記事を参考にインストール。

qiita.com

Vim をインストールしたいとき

apt-cyg install vim

やっぱり、apt は便利。

Cygwin について

Cygwin は、Windows 上で Unix ぽい環境を再現するためのソフトウェア。(以下参考)

ja.wikipedia.org

ターミナルは「mintty」、シェルは「bash」。(以下参考)

qiita.com

おわりに

Cygwin はちょっと Linux の環境使いたいみたいなときに便利。

環境を作っておいて損はない。

ROS でロボットを決まった距離走行させる ( Python )

目次

はじめに

ロボットを決まった距離走行させたいとき(または決まった角度の旋回)のメモです。

この記事では Python を使ってコードを書きますが、 どの言語でも同じようにできます。

方法

距離 [m] = 速度 [m/s] × 時間 [s]

この式を使います。

時刻の取得

Python では、t = time.time() である基準からの時刻を取得できます。

単位は秒 [s] 。

また、「time」ライブラリをインポートする必要があります。

ソースコード

#!/usr/bin/env python
import rospy
import time
from geometry_msgs.msg import Twist

class Test():
    def __init__(self):
        self.pub = rospy.Publisher('cmd_vel', Twist, queue_size=1)

    # 直進
    def pub_x(self):
        # 目的の距離と速度を設定
        dist = 1.0 # [m]
        speed = 0.2 # [m/s]
        target_time = dist / speed # [s]

        # Twist 型のデータ
        t = Twist()
        t.linear.x = speed
        t.angular.z = 0
            
        # 開始の時刻を保存
        start_time = time.time()
        # 経過した時刻を取得
        end_time = time.time()

        # target_time を越えるまで走行
        rate = rospy.Rate(30)
        while end_time - start_time <= target_time:
            self.pub.publish(t)
            end_time = time.time()
            rate.sleep()

    # 旋回
    def pub_z(self):
        # 目的の角度と速度を設定
        theta = 180.0 # [deg]
        speed = 90.0 # [deg/s]
        target_time = theta / speed # [s]

        # Twist 型のデータ
        t = Twist()
        t.linear.x = 0
        t.angular.z = speed * 3.1415 / 180.0 # [rad]
            
        # 開始の時刻を保存
        start_time = time.time()
        # 経過した時刻を取得
        end_time = time.time()

        # target_time を越えるまで走行
        rate = rospy.Rate(30)
        while end_time - start_time <= target_time:
            self.pub.publish(t)
            end_time = time.time()
            rate.sleep()

if __name__ == '__main__':
    rospy.init_node('tcmdvel_publisher')
    test = Test()
    # 直進
    test.pub_x()
    # 旋回
    test.pub_z()

気をつけること

Python では変数の型を宣言する必要はありませんが、

speed = 90 # int型
speed = 90.0 # float型

のような違いには気を付けなければいけません。

正確にロボットを動作させたいときは特に。

おわりに

他の方法も試しましたが、 この方法が最も簡単だと思います。

参考

dailyrobottechnology.blogspot.com

dailyrobottechnology.blogspot.com