AtCoder Regular Contest 005_C_器物損壊!高橋君
0-1BFSの問題.障害は多い方が燃えるよね.
問題の説明
高橋君はの迷路を移動する.高橋君は2回まで障害物を乗り越えられるものとして,ゴールに辿り着けるかを判定せよ.
条件
考えた事
迷路の基本的な実装は,
BFSについては,
を参考にしてもらいたい.手数がいらない,つまり何手で迷路にゴール出来るかは考えなくていいというのは後述する大きなポイントであり,DFSに似通っている.
ただ,それとの大きな違いとしては2回まで塀を超えられる事だろう.今までならばとりあえず深く探索し,行く先全て塀で塞がれていたらそれでおしまい,別のルートを探る方針であった.今回は二回まで塀を乗り越えられるため,それでは終わらない.
どう考えるべきだろうか.答えは塀を乗り越えた回数で移動経路をカウントするべきだろう.つまり塀を乗り越えた回数が0回のところは全て0と記し,1回乗り越えて行ける場所は1,2回ならば2......というようにやり,ゴールまでに乗り越えた塀の数が2回以下かどうかで判定をすればいい.
図のようなイメージをもてばいいだろう.青で記した部分が塀を乗り越えた回数である.これは上にあるチーズのBFSとは少し違う.あちらでも自分が次に行けるところにdist配列を用いて番号を振っていったが,その時は行ける場所は(現在の手数)+1とし続けていた.対してこちらは塀を乗り越えずに行ける箇所は+1としていない.
つまり,BFSでは移動コストが常に1である一方,この問題は0である時と1である時が混在する.そのため,このアルゴリズムの事を0-1BFSと表記するのだ.*1
考え方の説明はこの辺にして,この問題はどう実装すべきだろうか.
こういう時は直感を大事にしたい.実際に君がこの迷路を解くとしよう.目の前の壁,すぐ乗り越えますか?乗り越えた先に希望があるとは限らない.苦難を乗り越えたからといって幸せになれる保証はない.まずは穏便に,穏健に,今の状況で行けるところを全て探索するだろう.そうした上で行き詰って初めて壁を打破するのが普通である.*2
今回の問題も同様である.目の前に塀があるからといってぽんぽんぽんぽん乗り越えたとて,それが最善である保障は全くない.右の突き当りの塀を1回だけ乗り越えたら着くかもしれない.なるべく塀は乗り越えたくはないのだ.体力と関節に不安のない小学生ならいざ知らず,大人であり,かつ松潤やキムタクみたいに塀を乗り越える事が絵になるような人種でない私たちは,落ち着いて,老練に全部見てから検討すればいい.重ね重ねであるが塀はあまり乗り越えたくないのだ.ぎっぐり腰なるかもしれないし.
閑話休題.つまりどうすべきか.塀を乗り越える必要がある場合をなるだけ後回しにして,乗り越えずにいけるものを先に試せばいい.このように先端と末尾の両方に格納し,取り出せるデータ構造としてdeque(両端キュー) が存在する.0-1BFSではそれを採用する.コスト0で出来るものを先に,コスト1かかるものを後に回し,探索していくのである.
行く先に塀がなければそこはコスト0で行ける部分であるので,dist配列(今回では,塀を乗り越えた回数を記録するもの)には今いるところと同様の数字を入れて対応する.*3
そしてpush_frontとして前端に格納している.これによって移動コストが同等のものを先に扱えるようにしている.
行く先に塀がある場合は,今いるところから1増やした数字を入れて対応する.そしてこちらはpush_backとして末端に格納している.こうする事でコストの低い順に扱えるのだ.
迷路の途中でdequeの中身が無くなって移動コストが高い方が先に扱われるのではないかと不安がる人もいるかもしれない.しかし,今回塀は乗り越えたくないが乗り越えても"いい"事に目がいけばそうならないのは明らかだろう.
また,if文とdequeの合わせ技でなるべくコストの小さい順に処理し,もしコストがかかるとしても最小限に抑えられる事も分かるだろう.言われてみれば当たり前であるが,移動コストの最小値は,その塀の隣接上下左右にあるマスの移動コストの最小値+0or+1である.だから数字の小さい順に調べる事に合理性があるのだ.
本当に繰り返しになるが,なるべく塀を乗り越えず,コストの低い順に扱いたい.それを実現するのが0-1BFSなのである.
プログラム
第10回日本情報オリンピック 予選(過去問)E - チーズ (Cheese)
BFS(深さ優先探索)の問題.最短時間で工場見学できるカナ?!
問題の説明
の区画のこの町には個の工場があり,それぞれの工場が硬さのチーズを作っている.チーズの硬さは工場によって異なり,硬さからまでのチーズを生産出来る工場がちょうどつずつある.
最初のネズミの体力はであり,チーズを個食べる毎に増える.ただし,自分の体力より硬いチーズを食べる事は出来ない.
ネズミの移動に関するルールは以下の通り.
- ネズミは上下左右,隣り合うマスに分で移動できる.
- ネズミは工場及び,. のマスを通過する事が出来る.(この時にチーズを食べなくてもよい.)
- X のマスに侵入する事は出来ず,町の外に出る事も出来ない.
- チーズを食べる時間は考えないものとする.
今,ネズミはS からスタートした.上のルールの下で,ネズミが全てのチーズを食べる最短時間を求めよ.
条件
考えた事
問題文がややこしい.おそらく意図的なものではあるが言いたい事が分かりづらくなっている.
何を求めて欲しいか.それはとても簡単である.S→1→2→3→......のように動いていく最短時間を求めればいいのだ.ここで注目したいのは,S→1への行き方と1→2への行き方は全く無関係である事だ.S→1で2分かかったとて,500分かかったとて,1→2の行き方には影響しない.*1
つまり,S,1,2,3......の座標を配列にまとめ,要素[tex:i(0≦i≦N)*2]からに行く場合の最短時間を求める函数をつくり,それを足し合わせれば,ネズミが全てのチーズを食べる最短時間を求められるのだ.
これが例えばチーズを食べた工場が通れなくなるとなると少し面白い.食べた工場を×とする一工夫が必要となる.興味ある方はやってみてもよい.
そのため,main函数では,
とし,Sの座標を事前にまとめておくことには注意が必要である.
続いて,最短経路を求める函数を考えよう.迷路の移動方法については
を見てもらいたい.
BFSでのポイントはqueueである.
としてqueueを作り,その先頭の座標をgenに入れて入手.popして先頭削除を繰り返す.これを行う事で移動時間が短い順に座標を取り出し操作を行える.これと,
を合わせてdist配列で時間管理する事で,今いるところから+1minで行けるところ全てに記しをつける事が出来る.
図に表すとこんな感じ.まずSから上下左右の範囲で行けるところをqueueに入れ,1(右)1(下)で記しをつけていく.続いて1(右)の座標情報を入手し,そこから行けるところに2(右)をつける.同様に1(下)の座標情報を入手し,そこから行けるところに2(下)をつけていく.さらに2(右)の......と繰り返し,Gまでの最短時間を求めるのがBFSである.スタックと違い,1番下(古いデータ)から取り出すため,このような操作が出来るのだ.このようにして[tex:i(0≦i≦N)*3]からに行く場合の最短時間を求めれば,後はそれぞれの時間を足し合わせて出力すればいいというのは前述の通りだ.
プログラム
パ研合宿2019 第3日「パ研杯2019」C - カラオケ
全探索の問題.基本にして大事なんだと思う(ゆるふわっとした表現.)
問題の説明
人の生徒のグループが与えられ,こいつらが「カラオケ大会」に出る事となった.
歌える曲は曲であり,番号が曲を歌うと,点を取る事が分かっている.
コンテストのルールは以下の通り
- まず,グループ全体を通して,曲から歌う曲を2曲選ぶ.
- それぞれの生徒がこれら2つを歌う.
- 各生徒の得点はこの2曲のうち,高い方の点数とする.
- これらを生徒人について行い,生徒の得点の合計をグループの得点とする.
このルールの下で,グループの得点の最大値を求めよ.
条件
- 入力は全て整数.
考えた事
問題文の意味は何か.曲を2つ選び,その2つのうち大きい方の値を足していって作成可能な最大値はいくらかという事である.文章が恣意的であるが,大事なのは曲の選び方である事を理解して欲しい.
極端な例であるが,この生徒のグループ皆が十八番*1のものを選んでしまえば難しくもなんともないのである.しかし,なかなかそんな都合よく行く事ばかりではない.
例えばこの曲がめっちゃ得意で200点出せる人がいたとしよう.しかし,その人の声質が極めて独特でその曲にめちゃんこ合っているが,他の人には全く歌えず1点ばかり出してしまうかもしれない.そうした場合,カラオケ大会でその曲を持ち込むのは憚られるだろう.皆が効率よく点を取れる曲を持ち込むのが良さそうだ.*2
いうなれば小学校の頃にあった大縄跳びに近いのだ.あれもすごく俊敏に跳べる人に合わせていると他がついてこれず上手く巡らない.かといって遅くしすぎるとそれはそれで跳んだ回数が稼げない.縄を回す速さを調整する必要があるのだ.
ではこの最適な速さを見つけるにはどうしたらいいか.もちろん全て試せばいいのだ.縄を最遅から最速まで全て試し,そこで得られた跳躍回数を比較して,最大を出力すればいい.
それは今回も同様である.カラオケ大会に持ち込める曲の選び方は通りあるので,それら全てのパターンを試し,点数の最大値を出力すればいい.
とし,countに持ち込んだ2曲のうち点数の高い方の点数(生徒の得点)を足していく.それを今までの持ち込み曲で得られる合計と比較すれば良いわけだ.計算量はであり,高々程しかなく間に合う.*3
プログラム
A - 深さ優先探索
DFS(深さ優先探索)の実装の練習です.蟻本を読みながらチャレンジ.
問題の説明
の大きさの迷路が与えられています.各々のマス目にはs,g,.,# のいずれかが与えられ,高橋君は自分のいる場所から上下左右に動く事が出来ますが,斜めに移動する事は出来ません.また,s,g,.,を通過する事は出来るが,# を通過する事は出来ません.
今,高橋君がsからスタートしたとき,上のルールに則ってg まで辿り着けるか答えなさい.
条件
- s,g はそれぞれ1つだけ存在する.
考えた事
何はともあれ,まずは移動方法をどのように表すかを考える.斜めに移動できる場合は,
とすればよい.しかし,今回の場合は上下左右にしか動けないため,
このようにdx,dyベクトルを作り,iを変化させる事で上下左右の移動を表現した.
DFSは再帰函数で記す事が便利とされている.ならばこの場合,どのように再帰を終わらせる条件を作ればよいだろうか.
一つは当たり前であるが移動先が迷路の外である場合.もう一つは移動先が# である場合.ではこれだけでよいだろうか.
残念ながら,これだけでは足りないのである.これだと左右に行ったり来たりするような移動をした場合,再帰函数が無限に呼び出されてプログラムが終らなくなってしまう.そのため,今回は,
なる迷路に合わせたbool型の2次元配列を用意し,初期状態は全てfalseとし,現時点で高橋君が存在している場所をtrueとする.こうする事で移動先がtrueならばそこを通らないように条件節を作った.
まとめると,
- 場外に行かない
- # を通らない
- 一度通った場所には戻らない(移動先がtrueでない)
として,ifの条件節を作り,これを満たした上下左右の移動のみを再帰して呼び出し,trueをつけて上下左右で上の条件を満たしているところにまたtrueをつけていく事を繰り返す再帰函数を作成した.
状態遷移は4方向の移動の4通り,DFSは各マスについて高々1度しか呼び出されない(既に呼び出した部分にはtrueがつく)ため,計算量はとなり,条件を考えても十分間に合う.
求めたいのは,迷路をゴール出来るかどうかであるため,後はスタート地点からdfsを回し,ゴール地点の座標でのcheck配列がtrueかfalseとなるか調べればよい.
プログラム
日記。その19
もし、全ての差別や区別が無くなったとしたら、男女の社会的性はどうなるのだろうか?我々は無意識にこれが同じになると思い込んでいる。例えば、「女性が昇進出来ないのはまだ差別があるからだ。差別を取り払えば男女共に同程度の比率となるはず。」と言った言論である。これはバニラジェンダー仮説といわれる。実際、フランスには「パリテ」といったものが存在し、どんな場であっても男女同数を維持しようとしている。この大学だってそうだ。男女比に偏りがあるからこそ、女学生の入学者を増やすようにキャンペーンを行っている。しかし、これらのキャンペーンには本当に意味があるのだろうか?私には意味のないようなものに思えてならないのだ。
ファクトフルネスという本が一昨年流行った。ここには人間の10の本能による勘違いが記されている。その中にこういったものがある。単純化本能、犯人捜し本能、そしてパターン化本能といったものだ。私はバニラジェンダー仮説とはここから生まれているのではないかと考える。
我々を含め大衆は愚かだ。そのため、単純な帰結を得るものに惹かれてしまう。つまり、職場に女性が少ないのは女性差別があるからだといったものだ。
厄介なのはかつて女性が少なかった原因として女性差別がそこに存在した事は歴然とした事実ということだ。明治、昭和時代は世界問わず全世界で女性が就労したい仕事を自由に選べない現実があった。そのため、現代においても女性が少ない理由をそこに求めてしまう。いうなれば事象を単純に考え、誰かのせいであると犯人を捜してしまうのだ。
しかし、それが今の男女雇用の不均等を招いているとするのは早計だ。実際に日本よりもデータの上で男女平等とされるアメリカ、スウェーデンであってもエンジニアになる人の男女比は明らかな偏りを見せている。大学院の進学率も同様だ。
薄々気付いたかもしれない。つまり、これは生物学的な性差なのだ。どれだけ女性の待遇をあげようとエンジニアになる女性が急上昇する事はないのだ。
これだけいうと私が女性差別主義者だと捉われてしまうかもしれない。寧ろ逆だ。バニラジェンダー仮説を信仰する人間こそが女性を暗に差別しているのだ。上の議論でお気づきの通り、ここでいう「バニラ」とは男性の事を指し続けている。そして、これはどの機関、どの組織でもそうだ。ここに今の男女平等の歪みが存在する。それは、男女差別を取り除いた時、「男性のように」女性が生きる事が前提とされている事だ。生き方の基準が男性にあるのだ。
男性にとっての幸せが女性にとっての幸せとは限らない。当たり前だ。そもそも男性と女性を同じ土俵で比べてはいけないのだ。それは各々の育ちの違いの原因もある。だがそれ以上に脳機能が違うのだ。男性にとっての幸せが女性にとってのそれとは限らないし、逆もまた然りだ。どちらかの性はどちらかの性の上位互換でも、劣化でもない。
これを踏まえて我々は何をすべきか?簡単だ。選択を尊重できる社会を作る事だ。もっというと理想を捨てる事だ。男女平等が良いのはもちろん分かる。ただ、それが暗黙の上で女性の幸せ、もしくは男性の幸せを歪めているのかもしれない。その虚構に縋りつくくらいならば、男女はあるがままに振舞う事を許容する方がずっといい。
理系に行く男性がいても、芸術学部に行く女性がいてももちろんいい。そして、数学科に行く女性がいても、看護学部に行く男性がいてももちろんいい。大事なのは男女問わず、「男ならこう、女ならこう」といったジェンダーロールを押し付けない事、そして男女がちょうど半々を自然な状態と考えない事だ。
狩りに出るのは男ばっかりだったろう?あれだって自然なんだ。現代に求められているのは、そこで狩りに出ず家を守る男性と、自分から進んで狩りに行く女性が許容される自由さなのだ。そしてこれは自由であるからこそ、価値があるのだ。無理やり5:5が普通といって人数を取り揃えようとするのは傲慢なのだ。
もっともここではこのような指摘があるだろう。「自然ならばいいのか、そうするのは危険な思想だろう。それは自然主義的誤謬ではないか。」たしかにそうだ。全く正しい。自然であるから良いという思想は差別を招く。優生学もここからきている。今までは男が狩りに出て、女が家事をするのが自然、だからこそ男性は働き、女性は家事をすべきだ。というものだった。たしかにこれなら立派な自然主義的誤謬であろう。
しかし、私の主張はそうではない。男性が狩りに出て、女性が家事をするのが自然である事は否定しないが、そこから各々がジェンダーロールに沿って何かをすべきという価値観を否定するものだ。性別の垣根に捉われず、したい事をしたいように出来る事が多様性であろう。
では男性、女性が強制される職ならどうであろうか。例えば相撲の土俵には女性は上がってはならないとされている。これは先の主張に真っ向から反するものではないか。これについてはどう考えるのか。
私としてはこれは言葉遊びの領域だと考える。つまり「~であるべき」と、「~でなくてはならない」の違いだ。多くの男性、女性が強制される職は「~であるべき」ではなく「~でなくてはならない」事が多い。女性の着付けに男性が関与するのは心理的に望ましい事ではないだろう。
我々が認識を改めたいのは特に理由無く、あるいは昔そうだったからという理由だけで「男性、女性がすべき」となっているものだ。明確に理由をつけて何かを行う場合、それは差別にあたらない事が多い。
差別と区別の違いはその区分けが合理的であるかどうかだ。特に説明出来ない、あるいは非論理的な理由でその職につく権利を剥奪する事には反対であるが、明確に、論理的かつ合理的にその職にはその人しかつけないとするのに反対するのはおかしいだろう。
もし区別すら許されないのならば、誰でも簡単に医師を標榜したり、人を裁けるようになるだろう。それは社会システムの崩壊を招く。
ポルポトの誤りはそこからきていた。彼もまた、差別には反対であったが、彼は区別もまた差別と思い込んでいた。つまり、エリート層は非エリートを差別しているとして虐殺したのだ。結果、国には小学生で医師や弁護士を行うものが現れる始末であり、カンボジアの破壊を招いた。
彼の思想は原始共産主義と呼ばれるが、富や地位こそが差別を招くというものだった。だから一切の富を廃し、少しでも階級のあるものを失職させたり処刑を行ったのだ。ここには少し同意出来る人がいるかもしれない。富や立場が無ければ差別なんて起こらないと考える人がいてもおかしくはないはずだ。
しかし、それは因果と相関を履き違えている。差別の酷い国は往々にして貧富の格差や階級制度が苛烈な事が多い。もちろん、そこには非合理的なものも存在してそれに関しては取り払う必要がある。しかし、多くの場合差別の原因は富や地位ではない。他の、例えば人種、肌の色、出自が原因である事が多々だ。
こういえば分かりやすいだろう。アメリカ合衆国の大学は白人の在籍率が他の人種の在籍率よりも高い。ポルポトの主張は「この差別の原因は大学にあるから」大学を潰すようなものだ。しかし、この偏りに対して大学という組織そのものが責められるのはおかしい。結果と原因を履き違えている。責められるべきは大学の中に巣食う差別構造であり、それが非合理的なものから来ているならば是正する必要があるだろう。
ただ、これを理解している人は世界全体でもずっと少ない。実際、アメリカでもこの差別の原因を大学という組織にあると考え、黒人は白人に比べて低い点でも大学に合格できるようになっている。今世界で問題となっている逆差別である。かつての差別の揺れ戻しで差別が引き起こされているのだ。昔の失敗を今つけ払いしようとするとても愚かな発想である。
ともかく、差別と区別は明確に違うモノだと分かってもらえただろうか。今の男女の歪みもここから来ているといえるだろう。かつて女性が差別されていたから、今は過剰に女性を優遇しているのだ。しかも、男性目線での幸せになれるように。それは間違いだ。全体として考えるのでなく、一人一人自分なりの夢や幸せをもち、全体がそれを尊重出来るようになってほしいのだ。昔ならともかく、今なら教育水準も上がり、技術も進歩した。この大学にいる人はきっといいキャリアを積んで上に立つ人が多いだろう。だからこそ、様々なものを思いやれる、そんな人であってほしいと願う次第だ。
日記。その18
冬ですね。おはようございます。最近とても寒いですね。さて、冬と言えばなんでしょう?雪?イルミネーション?いえいえ、冷え性でしょう。冬は冷え性の季節です。今日は冷え性についてお話します。
まず、冷え性とよく言われるものは主に末端冷え性の事を指します。これと低体温症の違いは、前者は冷えた不快感が中心となるのに対し、後者は実際の体温が低い状態を指す事です。つまり、前者は身体の熱が不均等故に末梢神経が冷えてしまい、不快感を感じるのです。
冷え性の原因としてはレイノー現象と呼ばれるものがあげられます。レイノー現象とは、末梢の動脈が血管のけいれんを起こし、指の血流が非常に悪くなる症状です。閉塞具合によって、寒いところにいくと「白色」「紫色」「赤色」などに変色します。もっとも多いのが指ですが、他に耳や足・鼻・唇などに生じることもあります。他にも、末梢への血流障害、神経障害などもあげられます。
さて、対策はなんでしょうか?もちろんまずは服装に気を付ける事です。実際に末梢神経は冷えているのでまずそこを温める必要があります。次にそもそも冷えないようにするにはどうすればよいか?運動をしてストレスを溜めない事です。ストレスは万病のもと。自分の好きな事や趣味をしましょう。課題や大学の事を忘れて思いっきり遊びましょう。それではみなさん、よい一日を!
日記。その17
私は死の淵にいたアレックスを本人の同意なくロボット化して生かした事は間違いだと考える。勿論、家族の願いとしてはどんな形でも父親が生きて欲しいと願うだろう。それに関してはよく分かる。ただ、その手段としてロボット化を生じた博士には責任があるだろう。
まず第一にリスクの説明が足りない。アレックスが爆破された後、生きる手段としてロボット化される事自体は伝えているが、それを遠隔で操る事が出来る(ロボコップ化される)とは伝えていない。この処置を治療として見た時、そのリスクについて触れないという事は許されない。身体がロボット化される事は知っていても義足のような形かもしれない。それについて本来詳細な言及が必要だ。
また、大きく人類構造を逸脱している。ロボコップは武器を携帯する描写があるがそれは元のアレックスの身体と大きく異なる。明確に戦闘ロボ化されている。それは果たして適切なのか?君だって生き延びる代わりにワニにされると言われたら悩むだろう。
しかし、もしかしたらこういうかもしれない。生き延びるのなら何でもいいと。どんな形でも生かしてくれと。しかし、生きているとはそもそも何だろうか。この映画では会社からの指示により、脳波が変わり、アレックスの意思と無関係に行動する描写があった。これはアレックスが本当に生きている事になるのだろうか?
自分の身体も保てず、自分の意思すら自分でコントロール出来ない。この場合主なのはどちらか?もしかしたら主なのはロボの方かもしれない。いうなればこれは、ロボットにまだ生きているアレックスという名の警官の脳と心臓と肺を移植したにすぎないとすら考えられるだろう。つまり、アレックスはもう死んでいて、ロボットにアレックスの思考を植えつけたにすぎないという事だ。
これらの問いに対しこの映画では以下のように答えている。具体的には、途中から指示を無視するのだ。会社からの指示を無視して自由な行動を行う。自由とは即ちその存在の意思だ。そして、この意思はアレックスによるものなのは明らかだ。つまり、主はアレックスであり、アレックスの身体がロボットになっただけで、精神はそのままであり、アレックスは生きているといった事だ。
だが、もしプログラムの指示に抗えなかったら?最後にセラーズを撃てなかったら?それは生きていると言えるのか?臓器移植との違いは何だ?
ともかく、ロボット化を取り行った博士には多大な責任がある。一つはリスクの意図的な隠蔽、そしてそれに伴う自由意志を剝奪されたものの生死についての倫理的問題。人によって生きているか、死んでいるかの価値観は大きく異なる。実際、アレックスはロボット化した肉体を見て自分を殺すようにいった。そこで自分を殺さなかったのももしかしたらプログラムによるのかもしれない。人によってアイデンティティーは異なる。それを勝手に揺らがせた博士については(結果が良かったとしても)裁かれるべきだろう。そして、もし次回作があるならば自由意思を取り戻せなかった、つまりプログラムで完全に操られたアレックスの生死についてどのような答えを下すかを見てみたいものである。