ABC-308 振り返り
CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)
問題ページ: AtCoder Beginner Contest 308 - AtCoder
当面の目標
水色
全体の振り返り
A,B完答。 C,DはそれぞれWAとLTEで完了できなかった。残念。 それぞれPythonでは対応がし辛い問題だった。 C++への移行を考えたほうがいいかもしれない。 C++でやるとなると、競プロ専用のマクロみたいなのが多く混ざってきて、特殊対応している感あってあまり気が進まなかったのだけど・・・。
追記: 学び
- コマンドライン引数の受け取りは、中継用のリストを利用せずに直接利用するリストに流し込むほうが有意に早い
- データの溜め込みはリストよりもタプルにしたおいたほうが早い
- グリッドの現在地店から次地点4箇所の探索について、
filterを使うよりもdx[4], dy[4]の配列をforで回したほうが早かった。テーストによっては2倍以上、1.4sec以上差が開いているものもあり。
A
条件式を並べるだけ。
B
PythonのDictではdefaultdictを使わなくても、
キーがなかった場合のデフォルト値が設定できる。
getを利用して要素にアクセスする。
d.get("a", default_val)
C
最初デバッグ用のprintが残っていたのに気が付かず数回のWA。
その後printを修正しても、数件がWAのまま解決できなかった。
Zereo Divisionがあるのかなとか色々探しても解決できず。
割り算の箇所で丸め込みの誤差が発生しているため、割り算を排除する形で計算を行えば解決していた。
確率と人のindexそれぞれを用いてソートするため、ソートに関する比較関数内でIFを利用する必要があるが、標準のkey指定では対応できない。
from functools import cmp_to_keyを利用することで対応可能。
Pythonのデータソートについて検証してみた | DevelopersIO
D
アルファベットの順に並んでいる道を探してゴールまで辿り着く問題。 訪問済みの箇所を塗りつぶしていく形でDFSすれば良いのまではすぐに思いついた。 実装苦労するかと思ったが意外と楽だった、15分ほど。
再帰関数の呼び出し回数制限でWAが1回。 下記が必要だった。
import sys sys.setrecursionlimit(10**6)
ここからLTE1件が最後まで解決できなかった・・・。 解答例を見てもPythonでやっている例はあまりない。C++じゃないと厳しかったか?
ABC-303 振り返り
日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）
問題ページ: https://atcoder.jp/contests/abc303/tasks 解説動画: https://www.youtube.com/watch?v=_toS2Czj1to
当面の目標
水色
全体の振り返り
D問題まで、そんなに悩むことはなかったが実装時間が足りていなかった。 E問題以降はまともな時間内で解ける感じがしなかったので解法の勉強が必要。
時間はD問題完了時点で90分。 重複不可集合(set)の使い方とか調べ方読みながらやっていたので、このあたりに慣れたら早くなりそう。 あと実装中にprintデバッグするのが効率悪いので、デバッガで実行できるようにしておいたほうが良い。
各問題振り返り
A問題
10分。
特に悩む点はなかった。
dictで文字の対応マップを作って判定していたが、解答例では文字列をそのままreplaceしていた。
確かのそちらのほうが実装早そう。
B問題
24分。
発生していない組み合わせを探す問題。
問題文の理解と、itertools.combinationやsetの使い方を調べながら実装するのに時間がかかってしまった。
discardで削除。
解答例は全ての(x,y)の組を取り上げて、文字列中に出てくるかをスキャン。 下手に言語の機能使うよりこっちのほうが実装早かったかも。
C問題
26分。
移動させながらHPを回復させて移動完了できるか判定の問題。
実装方法について迷いはなかったが、アイテムが使用済みかの管理をSetでやるかdictでやるかを迷ってコーディングが少しウロウロした。
hpのリセット処理に関して、利用する変数が間違っているポカミスに気が付かずにタイムロス。
D問題
30分。
aとAからなる文字列を最速でタイピングする時間計算の問題。
capsの状態を分けた1つのリストでDPすれば良さそうだなというのはすぐに検討がついた。
ゆっくりやったのもあったがちょっと時間かかりすぎている。
状態遷移時の操作が6通りぐらい出てしまってややこしかったが、解答例や解説動画ではそんなにパターン多くない。
caps → a → caps の操作は考慮しなくても大丈夫っぽいのだがなぜだろう。
値が入力されるiに関して、その情報源になるi-1をループして最小値を持ってきていたが、
解答例では情報源側をiにして、次ステップのi+1に対して書き込んでいた。
この解答の書き方だとi+1の値を更新する際にmin処理で値を残すようにできるので、ちょっとだけ実装がシンプルになるかも。
iの対象をどっちにするか切り替えるのは別の問題でも役に立つことありそう。
E問題
10分、解ききれず。
スターグラフが連結してツリーになったものから、元のスターグラフ形状を算出する問題。
問題文読むのに時間かかってしまった。一番上の単語定義の文章をしっかりと読み込んでおくべきだった。
頂点数が多いノードを探せば行けるかな? → k=2の場合がめんどくさそうだな、からの、
次数が1のノードから順に消し込んでいく処理をすれば行けそうだなーと考えたところで終了。
解答的には、上記の方法でも行けるが、DFSないしBFSしてmod 3 = 1のものを取り出すのが楽、と。
復習で実装。 隣接表現リストでの実装はやりやすかった。 DFSは再帰関数で親のノード名だけ渡しておけば、2重にたどる処理を弾けるから実装が楽だな。
屋外での自律移動ロボットシミュレーション環境のまとめ
屋外走行のシミュレーション環境
屋外走行ロボットのシミュレータとしていいものがないかなとがした記録。
結論：
あんまちょうどいいものはない。
- gazeboで頑張って歩行者やワールドを作りこむ
- LGSVLかCARLAで、機体操作部分を自分でロボット対応に書き換える
あたりしか手がなさそう。
gazebo
開発者: OSRF
ゲームエンジン: 無し
githubスター数: 150
ROS標準のシミュレーション環境。
物理シミュレーション付きでホイールオドメトリの誤差なども取得できる。
利用シーンとしては屋外や広くても倉庫程度のものが多い。
環境を作りこむのが大変なのかな？多分。
gazeboで屋外環境を作りこんでいるものも一部ではある。
https://github.com/chapulina/dolly
ロボット自体の動作確認がメインで、歩行者や自動車を追加したシーンでのテスト、などは弱い。
CARLA
開発者: Intelなど出資が複数社
githubスター数: 4k
Intelなど大御所が出資する、OSSとしては最大手と思われる自動運転シミュレータ。
UE4を使っているだけあって画面は綺麗。
専用のros_bridgeを利用してROSと接続可能。
トピック型はステアリング、アクセルなどロボットでなく自動車操作に特化している。
ドキュメントによるとvhicleモデルとしてバイクも使えるらしい。
それだったら２駆動輪ロボットも追加できるようにして欲しかったなぁ・・・。
参考:
https://github.com/carla-simulator/ros-bridge
https://carla.readthedocs.io/en/latest/tuto_A_add_vehicle/#add-a-2-wheeled-vehicle
LGSVL
開発者: LG シリコンバレー研究所, Tier4など
ゲームエンジン: Unity
githubスター数: 1k
自動運転用のOSSとして有名なAutoware, Apollo対応のシミュレーション環境。
Autowareを開発するTier4では、LGSVLをシミュレーション環境として利用しているらしい。
ROSとの接続にはROS標準？のros_bridgeのwebsocketのノードを利用する。
roslaunch rosbridge_server rosbridge_websocket.launch
で普通に立ち上げるだけでOK。
ただし、機体操作のコマンドはAutoware用のメッセージ型になってしまう。
また、中身も自動車に特化している。
ROS標準のgeometry_msgs/Twistに変更できないかコードを追ってみたが、rosbrigdeのデータを取り込む処理で自動車専用のステア角度、アクセルなどのデータ構造に変換されていた。
物理シミュレーションの界面でも、ブレーキやギア状態を計算に利用している。
YoutubeにLGSVLでDuckieBotを走らせる動画が上がっていたので2駆動輪ロボット対応かと思って掘ってみたけど、2019.07のリリースでDuckieBot対応が削除されていました・・・。
※ ROS kineticでのrosbridge_websocketは標準でインストールされるpythonパッケージが間違っていて動かないので注意。下記でインストール。
sudo apt install ros-kinetic-rosbridge-suite
sudo pip2 uninstall autobahn | sudo pip2 install autobahn
sudo pip2 uninstall txaio | sudo pip2 install txaio
参考:
https://tech.tier4.jp/entry/2019/02/22/171052
https://github.com/lgsvl/simulator/blob/master/Assets/Scripts/Sensors/VehicleControlSensor.cs
https://github.com/lgsvl/simulator/releases/tag/2019.07
RoboSim
開発者: ZMP
ゲームエンジン: 不明(見た感じではUnity?)
ZMPが最近公開した屋外ロボット用のシミュレータ。
歩行者なども追加できる模様。
利用は問い合わせ必要。
Ubuntu 16.04にKakouneのインストール方法
公式リポジトリのREADME通りにやっても通らなかったのでメモ。
# g++7のインストール sudo add-apt-repository ppa:jonathonf/gcc-7.1 sudo apt-get update sudo apt-get install gcc-7 g++-7 # コンパイラをGCC7に変更 export CXX=g++-7 export CC=gcc-7 # githubリポジトリをクローンしてビルドしてインストール mkdir -p ~/Documents/github cd ~/Documents/github sudo apt install libncursesw5-dev pkg-config git clone https://github.com/mawww/kakoune.git && cd kakoune/src make PREFIX=$HOME/.local make install
ディープラーニングを用いた3次元点群レジストレーションを動かす
下記を動かす。
https://github.com/chrischoy/FCGF
環境構築
ディープラーニング系ライブラリのDockerイメージをまとめたDeepoを利用する。
FCGF要求のpython3.7 + pytorchな環境はビルド済みタグにはない。
ので自作する。
FCGFダウンロード
cd ~/Documents
git clone https://github.com/chrischoy/FCGF
Dockerイメージのベース作成
cd ~/Documents
git clone https://github.com/ufoym/deepo.git
cd deepo/generator
ython3 generate.py --cuda-ver 10.1 --cudnn-ver 7 Dockerfile pytorch python==3.7
docker build -t my/deepo .
※cudaやUbuntuのバージョンによっては、組み合わせが作れないことがある。
下記のdockerhubからベースイメージを得ているので、
下記で存在するものを指定する。
https://hub.docker.com/r/nvidia/cuda/tags?page=1&name=ubuntu
ベースイメージに必要パッケージをインストール
docker run --gpus all -it --rm -v $HOME/Documents:/Documents my/deepo bash
apt update
apt-get install libblas-dev
apt-get install liblapack-dev
apt-get install gfortran
cd /Documents/FCGF
pip install -r requirements.txt
apt-get install -y libgl1-mesa-dev
※ Minkowski Engineのインストールにはかなり時間がかかる。
Dockerイメージを更新
docker commit {起動中のコンテナID} my/deepo:ver2
テスト工学覚書
同値分割
異なる結果が帰ってくる各領域ごとに分けること。
代表的な値でテストが行えるようになる。
境界値分析
条件分岐の境目の値でテストを行うこと。
境界部分にはバグが入り込みやすい。
今日の作業
開発２日目
Visual Studioで起動してアプリのデバッグができるようになった。
C#でのdictへのアクセスができるようになった。
指の遷移をキーとして辞書を作成し、指変更時間の平均値を算出できるようになった。
