ふくほのひとりごと。

高専生が勉強したことの自分用メモ。

AtCoder / 高橋君のバグ探し

ふくほです。
ABC015-C 高橋君のバグ探し
を解きました。
https://atcoder.jp/contests/abc015/tasks/abc015_3:embed;cite

考えたこと

全探索するとO(K^N)になります。
制約から、K^Nは最大でも5^5 = 3125
になるため、間に合います。

i番目までの質問に
答えたときの値のパターンを
queueに入れます。

i番目までの質問に
答えたときの値のパターンは
i-1番目までの質問に
答えたときの値と
T_{i,x}(1\leq x \leq K)
のxorをすべて試したものになります。
これを、queueのvectorで実装しました。

提出コード

atcoder.jp

感想

vectorの中にqueueを
入れたのは初めてでした。
ちょっとずつC++
わかってきてる気がします
(完全理解とは程遠いですが)

AtCoder / 友達の友達

ふくほです。
ABC016-C 友達の友達
を解きました。
atcoder.jp

考えたこと

友達の友達の友達の…
だとUnionFindで管理することが
最適ですが、
今回は友達の友達までなので
木は使いません。

ユーザーiの友達を2重vectorで
管理します。
ユーザーiの友達の一人をj
としたとき、jの友達を全探索します。
jの友達をkとしたとき
iとkは友達でないことと
まだkが友達の友達として
数えられていないこと
の2つを確認します。
3重ループになりますが、
制約が小さいので大丈夫です。

提出コード

atcoder.jp

感想

はじめUnionFindで実装してて
あれあれ？ってなってました。
bool配列最高。
vectorの要素で回すfor文、
簡潔で分かりやすくて好き。

AtCoder / バスト避けられない運命

ふくほです。
ABC012-C バスと避けられない運命
を解きました。
atcoder.jp

考えたこと

これは典型的なワーシャルフロイド！
1つめに経由地、2つめに出発地、
3つめに目的地をおき3重ループ
を回します。

ワーシャルフロイドは
3重ループの順番が違っても
3回同じことをすると
最適解が出るらしいので
念のため三回同じループを回しました。

提出コード

atcoder.jp

感想

初見で苦労した問題の一つです。
そういえばダイクストラ
何も知らないので
最短経路問題に出会った
いい機会だし勉強しておこうかなと
思いました。

どうでもいいですが
ループの順番変えて回した時、
同じこと何回したら最適解が出るかを
探索するためにcntの値を変えて
たくさん提出してたら
初めて提出回数制限が来ました。()

AtCoder / スフィンクスのなぞなぞ

ふくほです。
ABC006-C スフィンクスのなぞなぞ
を解きました。
問題↓
atcoder.jp

考えたこと

鶴亀算を３変数にしたやつですね。
1\leq N \leq 10^5, 1\leq M \leq 5\times 10^5と大きめ。
三重ループは勿論、二重ループ
(2つの値を決めておいて、最後の1つが
条件を満たしているのか吟味する方法)
でも間に合わなさそう。
何とかして多重ループは
避けたいお気持ちでした。

ここで私は思いつきました。
赤ちゃんの数をa, 老人の数をb, 大人の数をc
と置いた時、問題から
4a + 3b + 2c = m
a + b + c = n
の２つの式を満たすことがわかります。
ここから1文字を消去し
2変数の関係式に持ち込みます。
今回はcを消去しました。
結果
2a + b = m-2n
が得られます。
ここでbを固定してみると
a=(m-2n-b)/2
このaは非負整数になります。

最後に、c=n-a-bから
cを求めます。
cも非負整数であることを
確認する必要があります。

提出コード

C++↓
atcoder.jp

Python↓
atcoder.jp

複雑なデータ構造を
使わないものだったので
Pythonでも書いてみました。
同じような実装なのに
Pythonのほうが遅い…！
っていう気づきがありました。

感想

こういう簡単めな数学で
複雑じゃないアルゴリズムだと
実装が軽くて好き。
昔の問題なので、今のAtCoderだと
茶diff真ん中くらいかな。
なんて考えます。

AtCoder / おいしいたこ焼きの売り方

ふくほです。
AtCoder ABC005-C おいしいたこ焼きの売り方
を解きました。
問題↓
atcoder.jp

考えたこと

AとB, sortした状態で
与えてくれるのか、ありがたい。
お客さんとたこ焼きを1:1に
対応させればよいみたいです。
よってqueueを使って早い時間に
できるたこ焼きから
お客さんに渡していく
と考えるのが自然かな。

計算量は O(MN)くらいになりますが
NもMも100以下なので間に合います。
(もし間に合わなかったら
どうやって解くんだろ、いもす法…？)

提出コード

atcoder.jp

感想

初見で解いたのが2020/6/15だったので
5か月ぶりに解いてみたことになりますね。
5か月前の自分はAの配列の
スタート地点を操作して
無理やり計算量削減してました。
この頃、まだqueueの存在
知らなかったと思います。
昔の提出コード↓
Submission #14377258 - AtCoder Beginner Contest 005

これは昔の問題だけど
今コンテストに出てきたら茶diff
真ん中くらいになるのかな…
と思ったりします。怖い。

AtCoder / 幅優先探索

ふくほです。
ABC007-D 幅優先探索
を解きました。
問題↓
atcoder.jp

考えたこと

BFSは習得に苦労した
アルゴリズムの一つでした。
queueが活躍しまくるやつ。

昔のコードではqueueをxとyに
分けていましたが、
今回はひとつのqueueに
座標の情報と最小コストの値を
詰め込みました。
queue,ll>>que;
.first.first → 縦の座標
.first.second → 横の座標
.second → そのマスまでの最小移動回数
としました。
また、一度訪れたところを
もう一度探索されると
無限ループに陥るので
bool配列visitedで何とかしました。
(ansの値が0である場合ない場合で
場合分けしてもよかったかもしれない)

あと、配列は0始まりなのでsy~gxは
入力したらとりあえず1ずつ引きました。
初心者の時わからず
これでバグらせまくりました()

提出コード

atcoder.jp

感想

BFSは基礎なので
しっかり固めていきたいです。
もう空で書けるようになったっ

ベクトル解析 / フレネセレの公式

ふくほです。
ベクトル解析を初めて学んだときに
最初にぶつかった壁
フレネセレの公式について
簡単にまとめます。

1. 必要なベクトルをそろえる

位置ベクトル \vec{p}(t)で与えられる
曲線 Cについて考えていきます。

前提として、単位接線ベクトル \vec{t}を
定義しておきます。
\vec{t} = \frac{\vec{p}'}{|\vec{p}'|}
( \frac{d}{ds}\vec{p} = \vec{p}'と表記しています)
細字の tは変数, 今回の単位接線ベクトル \vec{t}は
ベクトルなので混乱しないようにしてください…
(私は初見で大混乱しました)
それと、今回は曲線の長さ sで
微分しています。
変数変換が必要なので少し厄介ですね。

1.1. 単位主法線ベクトル

単位主法線ベクトルは Cの
二階微分の方向の単位ベクトルです。
これを \vec{n}として
\vec{n} = \frac{\vec{t}'}{|\vec{t}'|}
と表すことができます。
(正規化しないものは単に
主法線ベクトルと呼ばれています)

1.2. 単位従法線ベクトル

単位従法線ベクトルは \vec{t}と \vec{n}の
外積で定義されるベクトルです。
これを \vec{b}として
\vec{b} = \vec{t} \times \vec{n}
と表すことができます。
(そのままですね。)

また、外積はその2ベクトルが張る
平行四辺形の面積になりますが
今回の \vec{t}, \vec{n}が張るのは
1辺1の正方形であるため
\vec{b}の大きさは1になります。
特に正規化しなくてももともと
単位ベクトルになっているわけです。

2. 曲率と捩率

上記の二つのベクトルの考え方がわかると
曲率と捩率を求めることができます。
文字通り、曲率は曲線の曲がり具合を
捩率は曲線のねじれ具合を表しています。
(「捩じれる」でねじれるって読むらしい)

2.1. 曲率

曲率 \kappaは |\vec{t}'|で表すことができます。
Cの接線の傾きが急に変化するほど
曲率は大きくなります。
この Cの接線の傾きの変化が
|\vec{t}'|というわけです。

よって、 \vec{t}' = \kappa \vec{n}
という関係式が成り立ちます。
これがフレネセレの公式の第1式です。

また、 \kappaの逆数を曲率半径と呼び
Cの各点を円の一部と
みなしたとき、その円の半径を
表しています。

個人的にわかりやすかった記事↓
math.keicode.com

2.2. 捩率

捩率 \tauは \vec{b}' = - \tau \vec{n}
から求めることができます。

単位従法線ベクトルのところで用いた
\vec{b} = \vec{t} \times \vec{n}
の両辺を t で微分すると
(途中式は省略しますすみません。)
\vec{b}' = \vec{t} \times \vec{n}'
という関係式が現れます。
ここから、 \vec{b}' \perp \vec{t}
がわかります。

よって、 \vec{b}' は \vec{b} , \vec{t} の
両方に直交することが分かりました。
また \vec{n}も \vec{t}と直交しているため
以下の式が成り立ちます。
\vec{b}' = - \tau \vec{n}
これがフレネセレの公式の第2式です。

\tauは曲線の長さに対する \vec{b}の変化率を表し
\tau>0のとき、進行方向から見て右側に
\tau<0のとき、進行方向から見て左側に
それぞれ曲線がねじれているといえます。

3. フレネセレの公式を完成させる

最後に、 \vec{n}の導関数について考えます。
\vec{b} = \vec{t} \times \vec{n}
より
\vec{n} = \vec{b} \times \vec{t}
が成立します。

この両辺を sで微分して整理すると
\vec{n}' = -\kappa \vec{t} + \tau \vec{b}
が得られます。
これがフレネセレの公式の第3式です。

以上長くなりましたが
フレネセレの公式を
すべて導くことができました！

位置ベクトル \vec{p}で表される
曲線 Cにおいて
\vec{t} = \frac{\vec{p}'}{|\vec{p}'|}
\vec{n} = \frac{\vec{t}'}{|\vec{t}'|}
\vec{b} = \vec{t} \times \vec{n}
\kappaを曲率( \kappa = |\vec{t}'|)、 \tau を捩率
としたとき以下の３式が成立する。
(1) \vec{t}' = \kappa \vec{n}
(2) \vec{b}' = - \tau \vec{n}
(3) \vec{n}' = - \kappa \vec{t} +\tau \vec{b}

おわりに

初めてこの公式を目にしたのは
自粛期間だったのですが、
よくわからなくて何度も参考書を
読みなおしたのを覚えています。
今こうやって復習できて、また
理解が深まった気がします。
相変わらず、記事としての体裁は
あまり整ってはいませんが…