YKpages

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

短編小説『コオロギの安息地』


はじめに

音楽について、あるいは、壁について述べる。


私の歩き方

ゆっくり、ゆっくりと、二次元平面上を這って進む場合、どこまで行くのが正解か。 たとえば、東京タワーを目指して進むとしたら、私は何者だと推定されるだろうか。 満足を知らず、ただ座って、誰かが何かを与えてくれることを待っているだけの私に、放課後の夕暮れは厳し過ぎるだろう。 それでも私は、あえて東を向いてみる。 レンガ造りの古びた赤い屋根の家と市営のプールを横切って、砂利道を一時間ほど進む。 母は「もっとゆっくりしていきなさい」と私を叱ったが、私に答える術は無かった。

森に入ると、街の喧騒は遠のき、少しだけ穏やかな気持ちになれた。 もちろん後悔はしたが、本当のことだけを胸にしまっておくことが最優先だと私は考えていた。 そして、雨は止みそうになかった。 私は諦めて木陰に座った。 空には淡く輝く太陽が浮かんでいて、私の心を支配していた。 それは呪縛と呼んでも差し支えなく、太陽と月の関係を悟ることもできないのだった。

私の隣に腰掛けた黒髪の少女はどこか儚げだった。 少女はもう動かないノートパソコンを傘にして、雨を凌いでいるようだったが、 それにしては綺麗な顔をしていた。 腰まで伸ばした少女の黒髪は、触ると消えてしまいそうなほど煌めていて、その美しさに私はしばらく見惚れてしまった。

「どうすればいいと思う? 答えはオレンジとオレンジの間にあるはずなんだけど、いくら探しても見つからないの……」

どうやら少女は困っているようだった。

私はあまり気乗りはしなかったが、自分の理解できる範囲で答えることにした。

「雨が止まないことにはどうしようもないよ。もしくはタクシーを呼ぶとか」

「タクシーはダメ! これ以上、私の畑を荒らさないで!」

私はタクシーの有用性について論じたいわけではなかった。 だからこそ、昨日の夜に観た映画の続きが気になってしまったのだ。 少女が畑を荒らされることを嫌うなら、私にはどうしようもないことであり、 昨日の夜に観た映画の続きこそ、正解に最も近いのだろうと予想できた。

私は少女に語りかけた。

「もう寝よう。疲れているんだ、私も、君も。少し眠ってしまえば、雨はきっと止む」

少女は頷き、木の幹に背を預け、眠った。 深い深い眠りだった。


心拍の上限

波は波を生み出し、心地よい風はすでに失われてしまった。 正常な判断を目指していた私の頭上を、コンパスが襲い狂う。 黙っているだけで済む段階はとうに過ぎ去っていることを忘れてはいけない。 落ち着け、落ち着けと、囁きかける天使諸君と一緒に、 どうにか許される条件は満たしつつあった。 そして、雨は止んでいない。

少女は目を覚ますと、木の枝を使って、地面に絵を描いた。 それはライオンがキリンを捕食している瞬間を切り取った絵だった。 獰猛なライオンと小粋なキリンの曖昧さがうまく表現されていて、私は感嘆の声を上げた。 相変わらずの雨はひどく悲しそうに世界を濡らしていた。

私は一心不乱に絵を描き続けている少女に向かって尋ねた。

「どう? 答えは見つかりそうかい? 雨は止んでいないけれど、どうにかなるんだったら、私も協力するよ」

少女は手を止めて顔を上げると、私を見つめた。 少女の瞳はコオロギのように真っ暗で、何も映していないように思えた。 そして、少女は何かを言葉として発しようとして、すぐにやめた。 頭の中から言葉を探して、口から発しようとして、やめた。 それを何度も何度も繰り返した。 その行動は少女に似つかわしくなかった。

しばらくしてから、少女は答えた。

「……たぶん、答えはオレンジとオレンジの間にあると思うの。申し訳ないんだけど、代わりに探してきてくれない?」

私は少し考えてから「分かった。探してみるよ」と返答した。 本当なら面倒事は避けたかったのだが、少女の頼みとあっては断るわけにはいかなかったのだ。 しかし、少女が見つけられないものを私が見つけられるとは到底思えない。 もちろん、その存在を否定したいわけではない。 少女を否定したいわけではない。 私は、探している答えがオレンジとオレンジの間にあるという妄想を否定したいのだ。

少女は木の枝を捨てると、濡れた地面に横たわった。 そして、ゆっくりと目を瞑った。 私は横たわった少女のほうへと歩み寄った。 そのまま少女を見下ろす。 白い肌は鋭く雨を反射して、ツヤのある黒髪は十二分に透き通っていた。 雨に濡れる少女はとても美しく、そのまま永遠に眠ってくれれば、私の苦労の半分は消失してしまうだろうと予想できたくらいだ。

私は横たわっている少女に囁いた。

「それじゃあ、君の世界を見せてもらうよ……本当にオレンジとオレンジの間に答えはあるんだね?」

少女は目を瞑ったまま答えた。

「そうよ。きっとあるわ。見つけたらすぐに教えてちょうだい。すぐによ」

私は小さく頷くと、少女の頭にそっと触れた。 そして、少女の世界に入り込んだ。


方向の行方

問いは必ず答えを導く。 壁も天井も無いこの国において、もっとも重要なことは叫ぶことだった。 それを教えてくれたのは見知らぬ旅人だったが、 あまり記憶は定かではない。 しかし、雨は降っていなかったはずだ。 いずれにしても、あらゆる可能性について言及することは悪いことではないし、 聞く耳を持たない人間の席を用意する必要もない。

「冷たい篝火、そこに佇む騎士、それらが答えだ」

私は少女にそう伝えた。 オレンジとオレンジの間にあったのはその二つだけだった。 本当に答えが見つかるとは思ってもみなかったが、 そんなことよりも、私は成長を感じていた。 太陽はすでに頭上高く昇り、私たちを追い越していた。 少女の答えはすぐそばにあったのだ。 間に合うかどうかなど問題ではなく、 間に合わせることに意味があるだけなのだと分かったのは、それから二年後のことだった。

少女は泣いていた。 美しい瞳から、美しい雫が零れ落ちて、地面を濡らした。 私は少女に何一つ言葉をかけてあげられなかったし、 少女も言葉を必要としていなかった。 私は満足を知り、優しさに触れた。 おそらく少女も同じだろう。 つまり、その点においては、私と少女は等しい存在だと言える。

少女は涙を拭いてから言った。

「ありがとう。これで安心して朝を迎えられるわ。 無意味で無価値な長い夜が終わって、また始まるわけだけれど……ねえ、もしよかったら、あなたも一緒にどう?」

私は少し考えるフリをしてから答えた。

「……遠慮しておくよ。君の邪魔はしたくないし、他に用事もあるから。それに君はひとりのほうがいい。君は答えを見つけてしまったんだから」

いつの間にか、雨は止んでいた。


おわりに

十分な約束を求める。


カクヨムYusuke Kato(@yusuke_kato) - カクヨム


競プロ問題コレクション - 今日から始める競プロ日記

最終更新日:2020/01/13

はじめに

復習しやすくするために、解いた問題をジャンルごとにまとめたいと思います。

ちなみにジャンルの分け方は私基準です(つまり雑)。

また、問題が重複している場合もあります。

少しずつ更新していきます。

まとめるコンテスト

目次

良く参考にする記事

全探索する問題

普通に全探索

DFSで全探索

bit全探索

部分的に決め打ちしながら全探索

計算量を考えながら全探索

参考記事

bit全探索について簡単にまとめる - Qiita

数え上げの問題

modをとる問題

参考記事

「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜 - Qiita よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録

二分探索する問題

参考記事

二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 - Qiita

三分探索する問題

参考記事

三分探索と黄金分割探索 - naoya_t@hatenablog

累積和の問題

参考記事

累積和を何も考えずに書けるようにする! - Qiita

動的計画法の問題

参考記事

動的計画法超入門! Educational DP Contest の A ~ E 問題の解説と類題集 - Qiita Educational DP Contest の F ~ J 問題の解説と類題集 - Qiita 典型的な DP (動的計画法) のパターンを整理 Part 1 ~ ナップサック DP 編 ~ - Qiita

尺取り法の問題

参考記事

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita

グラフ(DFS、BFS)の問題

隣接行列

  • まだ

隣接リスト

参考記事

DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita BFS (幅優先探索) 超入門! 〜 キューを鮮やかに使いこなす 〜 - Qiita

ソートの問題

ソートのアルゴリズム

参考記事

ソートを極める! 〜 なぜソートを学ぶのか 〜 - Qiita

pair, tupleを使うソート

参考記事

Z - 3.02.pair/tupleとauto

算数・数学、それに近い問題

合同式を使う問題

整数値の各位の桁に関する問題

参考記事

数字根 - Wikipedia

2進数を扱う問題

参考記事

C++ 数値を 2進数 8進数 10進数 16進数 文字列に変換する方法 | MaryCore

2次元グリッドの問題

インタラクティブな問題

文字列を埋める処理(ゼロ埋めなど)をする問題

参考記事

【C++】左詰め/右詰め/ゼロ埋めの方法と注意点【cout/iostream 文字揃え】 | MaryCore

切り上げする問題

入力の仕方を工夫したい問題

ちょっとした工夫をすると楽になる問題

setを使う問題

素因数分解を使う問題

おわりに

日々、精進したい。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com

AtCoder Beginner Contest 145 D - 今日から始める競プロ日記

はじめに

AtCoder Beginner Contest 145 に参加しました。

D問題の二項係数の計算で躓いてしまったので、 この記事にまとめておきます。

D - Knight

  • 二元グリッド上の (0, 0) にナイトの駒がいる
  • ナイトは (i+1, j+2) か (i+2, j+1) に動かせる
  • このナイトを (X, Y) に移動させる方法は何通りか

D - Knight

解いた方針

以下を参考に解き方をまとめます。

(+1, +2)を行う回数をn、(+2, +1)を行う回数をmとすると以下の連立方程式が立てられます。

2n + m = X
n + 2m = Y

これを解くとnとmを求めることができます。

n = (2Y-X) / 3
m = (2X-Y) / 3

そして、n+m回の移動のうち、(+1, +2)と(+2, +1)の組み合わせは、n+m C nで求められます。

また、この計算ではmodをとる必要があります。

以下のけんちょんさんの記事を参考にしました。

よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録

コード

二項係数の計算はけんちょんさんのコードをそのまま使っているので、 もしその部分を使う場合はけんちょんさんの記事を参考にしてください。

int main()
{
    long long X, Y;
    scanf("%lld%lld",&X,&Y);
    if((X+Y)%3!=0){printf("0\n");return 0;}
    long long n=(2*Y-X)/3;
    long long m=(2*X-Y)/3;
    if(n<0||m<0){printf("0\n");return 0;}
    long long nm=n+m;
    COMinit();
    cout << COM(nm,n) << endl;
    return 0;
}

おわりに

modのとり方がいまだによく分かりません......。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com

yukicoder No. 604 誕生日のお小遣い - 今日から始める競プロ日記

はじめに

最近、yukicoderも始めました。

本当は作問してみようと思って登録したのですが、 いざ問題を作ろうと思ったら何も思い浮かばなかったので、 他の方々が作った問題を解いて勉強していきます。

No. 604 誕生日のお小遣い

  • 誕生日になるとお小遣いが貰える
  • 歳がAの倍数のときはB円
  • それ以外では1円
  • 1歳からお小遣いをもらい始めたとき、総額がC円を超えるのは何歳か

No.604 誕生日のお小遣い - yukicoder

解いた方針

頑張って計算する方法(1行で書ける)と二分探索を使う方法があるみたいです。

ここでは二分探索のほうで解いてみます。

以下の記事を参考にしました。

c6h4c12takatakamasataka.hatenablog.com qiita.com

この問題の制約が

1 <= A,B,C <= 10^18

とかなり大きいので、計算量がO(N)でもダメです。

歳が増えるごとに、もらえる総額も増えるので二分探索が使えそうです。 二分探索なら計算量は`O(logN)であるため、大丈夫そうです。

計算の流れは以下のようになります。

  1. 二分探索の範囲を設定(左端=0, 右端=C)
  2. 中央の値を計算中央 = (左端+右端)/ 2
  3. 2で求めた中央の値(歳)のときもらえる総額を計算
  4. 3で求めた総額がCより大きいか小さいかで、範囲を更新
  5. 解が求まるまで2~4をループ

コード

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

int main()
{
    // 入力
    unsigned long long A, B, C;
    cin >> A >> B >> C;

    // 二分探索
    unsigned long long left  = 0; //左端
    unsigned long long right = C; //右端
    while(right - left > 1)
    {
        unsigned long long mid = (left+right)/2; //中央
        unsigned long long sum = (mid/A)*B + mid-(mid/A);
        if(sum >= C) right = mid;
        else left = mid;
    }

    // 解を出力
    cout << right << endl;
    return 0;
}

おわりに

二分探索をなんとなく理解した。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com

第二回全国統一プログラミング王決定戦予選 B - 今日から始める競プロ日記

はじめに

日本経済新聞社主催のコンテスト、 第二回全国統一プログラミング王決定戦予選に参加しました。

B問題で無限に時間を使ってしまったので、 同じ過ちを繰り返さないために、 ここにまとめておきます(100分くらいB問題に使った)。

atcoder.jp

B - Counting of Trees

  • D[1] ~ D[N] までの整数列が与えらえる
  • 次の条件を満たす、1 ~ Nまでの頂点を持つ木の個数を数える
  • 条件:1以上N以下の任意の整数iに対して、頂点1と頂点iの距離がD[i]である
  • また、解は998244353の余りを出力

解き方

まず、そもそも木が作れないパターンを判定する。 以下を満たす場合は'0'を出力して終了。

  • (1) 頂点1から頂点1までの距離が0かどうか判定
  • (2) 距離が0の頂点が二つ以上あってもだめだから判定
  • (3) 距離が飛び飛びになっていてもだめだから判定(距離4の頂点はないけど、距離5の頂点はあるみたいな状況)

(3)は判定しなくてもちゃんと実装できていれば自然に回避できるらしい。

次に、各距離ごとの頂点の個数を数える(辺の個数でもある)。

最後に、距離iの頂点の個数をcnt[i]、 距離i+1の頂点の個数をcnt[i+1]として、 cnt[i]のcnt[i+1]乗を掛け合わせていく。

サンプルケース3を例にとる。

  • 距離0の頂点が1つ
  • 距離1の頂点が2つ
  • 距離2の頂点が3つ
  • 距離3の頂点が1つ

距離0の頂点から距離1の頂点へ辺を張る方法は必ず1通りしかないのでこれは考えなくてよい。

距離1の2つの頂点から、距離2の3つの頂点への辺の張り方は、2^3 = 8である。 (これは高校数学の組み分け問題の考え方。3つの異なるボールを2人で分けるとき、分け方は何通りかみたいな問題。 参考:【高校数学A】組分け問題全パターン | 受験の月

同じように考えて、距離2の3つの頂点から、距離3の1つの頂点への辺の張り方は、3^1 = 3通りである。

よって答えは

1 * 8 * 3 = 24

となる。

そして最後に最も重要なことがある。

それはmodを取ること。

私はmodを取ることはちゃんと意識していたけど、 べき乗でpowを使ってそのpowの後でmodを取るようにしていたので、 オーバーフローを抑えられなかったらしい。

コンテスト残り5分くらいのときに、 「あれ、これ掛け算一回やるたびにmod取らないとダメじゃない?」 ということに気が付きました。

modは掛け算を一度行うたびにとったほうが良さそう

qiita.com

コード

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

int main()
{
    // 入力
    int N;
    cin >> N;
    vector<int64_t> D(N); // 与えられる整数列
    vector<int64_t> cnt(N, 0); // 各距離の個数をカウント
    for(int i = 0; i < N; i++)
    {
        int t;
        cin >> t;
        D[i] = t;
        cnt[t]++;
    }

    // 頂点1から頂点1までの距離が0だったらダメ
    if(D[0] != 0)
    {
        cout << "0" << endl;
        return 0;
    }

    // 距離が0である頂点が二つ以上あったらダメ
    int zeroCnt = 0;
    for(int i = 0; i < D.size(); i++)
    {
        if(D[i] == 0) zeroCnt++;
        if(zeroCnt >= 2)
        {
            cout << "0" << endl;
            return 0;
        }
    }

    // 距離が飛び飛びになっていたらダメ
    // (そんな状況はない?)
    bool flag = true;
    for(int i = 0; i < cnt.size(); i++)
    {
        if(flag == true && cnt[i] == 0) flag = false;
        else if(flag == false && cnt[i] > 0)
        {
            cout << "0" << endl;
            return 0;
        }
    }

    // 頂点1から距離がiの頂点の個数をT[i]
    // 頂点1から距離がi+1の頂点の個数をT[i+1]
    // ans *= T[i] ^ T[i+1]
    // 高校数学の組み分け問題と同じ考え方
    // 注意点:一回掛け算するたびにmodをとる
    long long ans = 1;
    const long long mod = 998244353;
    for(int i = 0; i < cnt.size()-1; i++)
    {
        if(cnt[i] != 0 && cnt[i+1] != 0)
        {
            for(long long p = 0; p < cnt[i+1]; p++)
            {
                ans *= cnt[i];
                ans %= mod;
            }
        }
    }    

    // 解を出力
    cout << ans << endl;
    return 0;
}

おわりに

何回もmodに苦しんでいる。悲しい。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com

AIZU ONLINE JUDGE ALDS1_1_A - 今日から始める競技プロ日記

はじめに

螺旋本の問題をゆっくり解いていく。

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

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

今日はALDS1_1_Aの挿入ソートの実装(p. 54)。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_A

3.2 挿入ソート(p. 54)

挿入ソートの疑似コードが与えられるので、自分で実装する

挿入ソートについてなんとなく書く

挿入ソートはかなり直感的なソート。 人が日常の中で何となくやっているソートだと思う。

数列Aが与えれれる。

5 2 4 6 1 3

挿入ソートでは、ソート済みの部分列と、 まだソートされていない部分列に分けてソートを行う。

まずは先頭の5をソート済みとする。 それ以外は未ソートとする。

(ソート済み) 5 | 2 4 6 1 3 (未ソート)

次に未ソートの部分列の中で、 一番左の値をソート済みの部分列の中で適切な場所に挿入する。

つまり、2を挿入する。 25よりも小さいので5の前に挿入する。

(ソート済み) 2 5 | 4 6 1 3 (未ソート)

これを繰り返す。

(ソート済み) 2 4 5 | 6 1 3 (未ソート)
(ソート済み) 2 4 5 6 | 1 3 (未ソート)
(ソート済み) 1 2 4 5 6 | 3 (未ソート)
(ソート済み) 1 2 3 4 5 6 | (未ソート)

挿入ソートの計算量

  • 最悪:O(N^2)(厳密には(N^2-N)/2とのこと)
  • 最良:O(N)

降順に並んでいる数列を昇順に並べ替えようとするとO(N^2)

昇順に並んでいる数列を昇順に並べ替えようとするとO(N)

ソート - Wikipedia

コード

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

// ソート対象の配列を出力
void printA(vector<int> A, int N)
{
    for(int i = 0; i < N; i++)
    {
        if(i == N-1) cout << A[i] << endl;
        else cout << A[i] << " ";
    }
}

// 挿入ソート
vector<int> insertionSort(vector<int> A, int N)
{
    for(int i = 1; i < N; i++)
    {
        int v = A[i];
        int j = i-1;
        while(j >= 0 && A[j] > v)
        {
            A[j+1] = A[j];
            j--;
        }
        A[j+1] = v;
        printA(A, N); // ステップごとの状態を出力
    }
    return A;
}

int main()
{
    // 入力
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    // 初期状態の配列を出力
    printA(A, N);
    // 挿入ソートを実行
    A = insertionSort(A, N);
    return 0;
}

おわりに

挿入ソートをなんとなく理解できた

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com

AtCoder Beginner Contest 144 D - 今日から始める競プロ日記

はじめに

AtCoder Beginner Contest 144 D問題が解けなかったので、 解説動画を見ながらまとめていく。

atcoder.jp

www.youtube.com

D - Water Bottle

  • 底面が a[cm] の正方形、高さが b[cm] の水筒がある
  • 水筒に体積 x[cm3] の水を入れる
  • 水筒を傾けたときに水がこぼれる角度を求める

解き方

まず二次元にして考える(これはできた)。

水の面積は

s [cm^2] = x [cm^3] / a [cm^2]

f:id:kato_robotics:20191028004426p:plain
abc144_d1

水筒を傾けて水がこぼれ始めるパターンは二つに分けられる。

f:id:kato_robotics:20191028011306p:plain
abc144_d2

分け方は面積 S が ab/2(水筒の半分)より大きいか小さいかで決められる。

コード

解説動画を参考に書いたコード

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

int main()
{
    // 入力
    double a, b, x;
    cin >> a >> b >> x;
    // 二次元で考えて面積を求める
    double s = x/a;
    // atan2で角度(ラジアン)を求める
    double rad;
    // 水が水筒の半分以上の場合
    if(s >= a*b/2)
    {
        double h = 2*(a*b-s)/a;
        rad = atan2(h,a);
    }
    // 水が水筒の半分以下の場合
    else
    {
        double w = s*2/b;
        rad = atan2(b,w);
    }
    // ラジアンを度に変換
    double PI = acos(-1);
    double deg = rad/(2*PI)*360;
    // 解を出力
    cout << fixed << setprecision(10) << deg << endl;
    return 0;
}

おわりに

場合分けができなかった。悲しい。

今日から始める競プロ日記まとめ

kato-robotics.hatenablog.com