汎用コマンド探訪１ - wc
wc - word count
linuxコマンドの略記法は気持ちがいいが、すぐに慣れるようなものではないと思う。
grep（Global Regular Expression Print）なんかは分かりやすいが、tee なんかはもうなんのことやら、、って感じだ（データの動きがTの形になるから、らしい）。
wcは比較的分かりやすい方で、WordをCountするのが目的なんだそうだ。
でもwcは、単語の数も数えられるし、行数を数えることにも使える（というかむしろ行数を数えることに使う、という紹介が一番多い）。
以下にmanualから抜粋したオプションを書いておこう。
- -c / --bytes : バイト数を数える
- -m / --chars : 文字数を数える
- -l / --lines : 行数を数える
- -w / --words : 単語数を数える
お分かりの通り、そもそも-wオプションをつけないと単語数を数えられないのだ。
これはwcって名乗っていいものなのかなとも思う
ちなみに、オプション無しだと（環境にもよるが）
行数 単語数 文字数
がこの順に表示されるようだ。
AtCoder Beginner Contest 102 参加ログ
ABC102に参加しました
AtCoder Beginner Contest 102 - AtCoder Beginner Contest 102 | AtCoder
実力：緑色（最高R: 1007, 現R: 915）
今回は約30分おくれて参加（20:30~のところ、21:00~）。
これからは毎週参加して、レポートをこんな感じで書くようにしたい
A, B問題
この二つの難度はいつも通りで、標準入出力さえできて焦りさえしなければ、解ける問題
C問題 Linear Approximation
僕のレベルだと、C問題を解くのに30分以上はかかる。今回もそんな感じ（約34分）だった。
今回の僕の思考を整理すると、
- 問題文よく読む
- 平均値の周りを調べればいいんじゃね？ｺｰﾄﾞｶﾞﾘｶﾞﾘ- => WA
- 平均じゃダメなのか、、、何がおかしいの、、、？
- なんか極端なテストケース突っ込んでみるか
- BruteForceで調べると、確かに答え違うな、、、
- おk、平均、お前はダメだ。medianこそ正しい => AC
問題
WA一回で済んだのは僥倖だったものの、この思考プロセスには問題がある。
コンテストは時計を見ながらやっているので、各プロセスにかかった時間はだいたい把握している。以下の通り。
1: 5 min,
2: 12 min,
3: 3 min,
4: 7 min,
5: 5 min,
6: 2 min
3~6までに17 minもかかっていて、結局はじめから解き直しているのと同じになっている。
これは、2. で問題が正しく解けることの証明をしていないからだ。
反省点
次からはもう少し踏み込んで考え、証明に到るようにする。
D問題 Equal Cut
Dは解けるか解けないか2:8くらいの割合なのだが、今回は8の方だった。
今回の僕の思考を整理すると、
- 問題文を読む
- 全部調べようとすると組合せ爆発するから、何かしらうまい方法を考えなきゃいけないな
- 総和/4の値を超えるかどうかで数字を分けたらどうかな、、、
- quantileを超えたり超えなかったりで数字を分けられないかな、、、
- 時間切れ
こんな感じ。
解説を読んで自分なりに解説してみる
PQRSの切り口をleft, center, rightとする。
centerを固定すれば、
PとQを同じ大きさにするようにしてleftが決まり、
RとSを同じ大きさにするようにしてrightが決まる。
これで組み合わせはN通りしか無くなるので、全ての値を計算して最小値を出せば良い。
もしleft, rightの決定がO(1)で済むなら、全体の計算量はO(N)で済む。
あとは個々の計算量をうまく減らせるかどうかの問題になる。
"total(L, R) # left~right区間の値の和を返す" のような関数を用意しておいて、この関数はただすでに計算済みの値を返すようにする。
こうすれば、leftとrightの決定にも使えるため、O(N)を担保できる。
反省点
結局、「組合せ爆発をどうやって回避するのか」が最も重要なところだったようだ。
僕の思考プロセスのうち３も４も、与えられた数字をどうやって分けるかしか考えられていなかった。
よって今回の反省点は、
- もっと大局観を持って設問に臨むこと（今考えていることがダメそうかどうかを常に評価すること）
- 計算量にシビアになること
結果
R915 => R964 (49 up !!)
時間通りに参加してたらもっと上がってたかも、、、
a bolt out of the blue は、晴天の霹靂という意味。突然の、とかそんな意味。
僕は割と気まぐれな人間である。
突然何かを始めたかと思ったら、すぐにやめて他の何かに夢中になる。
最近はビリヤードにはまっていて、マイキューを買って週３日くらいプールバーに通っている。
でもいつ辞めるか僕でもわからない。ダーツも1年でやめてしまったし、大学入学の時に思いつきで読んでいた集合論の本も面白かったのにすぐ読まなくなった。脳科学の勉強も中途半端でやめてしまっている。
以前に（というか最初に）ブログの目的など綴ったこともあるが、
そもそもこのブログを始めた理由も、そんな感じである。突然の思いつきで、ただやってみたかっただけである。
さてところで、ブログタイトルが、そんな僕の気質をよく表しているんじゃないかとふと思った。このエントリを書いているのは、その気がつきを書いておきたかったからだ。
何気なくかっこいいからつけただけだったけど、何を書けば良いのかこれではっきりした。
なんでも良いから僕が突然に思いついて始めたことを、何をしたのかを、適度に書いていく。
僕は毎日作業ログを取っている。だから、それをブログに起こすことにした。
ちょうど今ここに書いている感じで、僕の考えたことや、調べたことを書いていこう。
第９地区と移民問題
昔から気になっていた「第９地区」というSF映画を見たので、感想文に似た何かを書いた。
※ネタバレを含みます。
SF映画の種類
コンテンツとしてのSF映画には2種類あって、それぞれ楽しみ方が違う。
ながら見ができるものと、出来ないものだ。
ながら見ができるタイプのSFの有名どころは、例えばインデペンデンス・デイ：リサージェンス
いわゆる、「宇宙人がやってくる！やっつけろー！」系の、映像を見なくても展開が大体わかるアレだ。
ながら見ができないやつは、例えばトランセンデンスやインセプションあたりだろうか。
世界観や設定、展開が独特で、それらを把握するのに気を使うのだ。
第９地区
第９地区がどちらのくくりになるかと言えば、どっちでもなかった。
宇宙人（作中ではエビとも言う）が20年も地球の一角に滞在し、社会問題化しているヨハネスブルクが舞台。
ドキュメンタリー調で話が進み、まるで史実であるかのように演出する。過剰なほどのグロテスク描写も、真実味を帯びさせるのに一役買う。
主人公のヴィカスは、MNUなる民間軍事組織に所属する、地球人のクズ代表だ。難民エビたちを第9地区から退去させ、厄介払いをするプロジェクトを押し付けられる。
彼は作中通してなぜか死亡フラグをたてまくる。
しかしながら彼はクズなだけでなくアホなので、任された仕事にイキリっぱなしだ。
プロジェクト中に見つけたものにあれやこれやと難癖をつけ、いじり倒していく。エビの卵を燃やして爆笑する描写が、二つの意味で爽快だった。
この主人公のおかげか、本作ではずっと緊張感があるのだ。いつエビに殺されるのかとヒヤヒヤさせられる。
若干意味合いは違うが、緊張感という意味ではオール・ユー・ニード・イズ・キルに近いものがある。
彼がいじるものの中には当然危険なものも含まれていた…のだが、これ以上は映画を見て欲しい。
風刺
さてどうもこの世界の宇宙人の起こす問題には、現代の戦争や難民といった問題に通じる部分がある。
この映画は、2009年に公開され、アパルトヘイト政策を風刺した映画として、かなりの高評価を得た。
第9地区：アパルトヘイトを彷彿させる人間たちの残酷さ - ビールを飲みながら考えてみた…
だが実は公開当時も、アパルトヘイトだけでなくあらゆる差別問題をくすぐる内容だったと評価されている。
映画「第9地区」って何かを風刺しているように思えませんか？... - Yahoo!知恵袋
しかしながらさらに時の進んだ2018年では、この映画はまた違った意味を持ってくるように思えた。
EUの難民問題
2015年欧州難民危機を知っているだろうか。
日本のメディアはあまり取り上げなくなったが、EUはとっくにパンク状態だ。
内紛状態のリビアやシリアからやってくる難民の数は、最大で年100万人を超えていた。
難民による性被害も巨大なものになり、治安の悪化も声高に叫ばれている。下記は欧州の移民・難民問題とテロリズムについて論じた政策オピニオンだ。
この文書に、ゼノフォビア（xenophobia：外国人嫌悪）という言葉が出てくる。これは、xenos（外国人）とphobos（嫌悪）を含む造語で、そのままの意味だ。
なぜゼノフォビアが発生するのか、どういった人がゼノフォビアを抱いてしまうのかについても、上記文献で述べられている。
EUにおけるゼノフォビアは、移民に対して向けられる。移民の流入のせいで、自分たちの生活の質を落とされていると感じると、その敵意は移民に向く。
全ての移民が悪いわけではないとわかっていながら、０か１、善か悪、で物事を判断する。
そもそもの仕組みやシステムに理由を求めず、「わかりやすい敵」に敵意を向けるのは歴史的にいつも行われてきたことだ。
第９地区では、エビたちへの明確なゼノフォビア描写がある。なにせこいつらは見た目は凶悪にデフォルメしたエビで、キャットフードとタイヤが大好きで、しかもめちゃくちゃな騒ぎを起こすのだからこれも当然かもしれない。
「第９地区」はいかにして解決すべきだったのか
作中では、第10地区への移籍によって、「臭いものに蓋」式の解決法を取っていた。
この処置の根底には、エビが下等なもの、ほとんど対話に値しないものという前提が推し量れる。
歴史は繰り返す。人類はアパルトヘイトから何も学んじゃいない。というわけだ。
だがそもそもエビが地球にやってきたその技術をして、圧倒的に人間のそれを上回っている。
宇宙船のリバースエンジニアリングなり、その他色んな研究ができたはずで、それによって人類の科学レベルは飛躍的に向上させることができただろう。
エビは人類に発展をもたらすことができた（はずだ）。
エビは敵ではなく、人類の発展に寄与する味方なのだ。
だが感情をコントロールして、最適行動を取れる人間は多くない。エビの見た目によってもたらされる不快感は非常に大きいため、エビを味方として捉えられる人間はほとんどいない。
これは資本主義の破綻と似た構造を持っている。
AI研究者の新井紀子氏の講演で、非常に的確な指摘があった。
新井紀子氏「資本主義社会が不可避に生む不公平と格差はリテラシーをもつ市民による民主主義で乗り越えられるはずだった。この前提が崩れてきている（市民はリテラシーを持つという仮定が苦しくなってきている）」
— sho_yokoi (@sho_yokoi) November 14, 2016
資本主義は難しい社会システムであり、参加するには一定以上のリテラシーを必要とする。
しかし市民が自発的に学ぶことを前提とした社会システムでは、感情面での制約が強い課題に対処することができない。感情が「知る」ことを避けてしまうからだ。
最後に議論を飛躍して結論を述べると、
民主主義以外の、新たな社会システムによって、個人の思考の仕方を再インストールして、問題の発生を抑えることが必要だったのだろう。
僕は個人が悪いのではなく、システムが悪いと考えたい。アパルトヘイトも、第９地区も、同じ構造の同じ社会システムが生み出した。この社会システムはもはや持続的でない。新たなシステムが必要なのだ。
どういった社会システムが実際に有効なのかは、この記事の範疇を超えそうなので、またどこかで書ければ（調べられれば）と思う。
最後に
グロが大丈夫な人全てにオススメできる良作SF。もっと早く見ておけばよかったと思った。
ARC091 問題F: Strange Nim の平易な解説 _1
AtCoderの解説が難しい、、、
AtCoderの過去問にチャレンジ！
AtCoder Reguler Contest (ARC)第91回を解いてみた。
しかしながら、解説が初心者には全く優しくないのであった。。。
そこで頑張って解説を解読しようと決意した。なるべく平易に細かく解説を試みます。
問題F: Strange Nim
問題文
高橋君と青木君は、石取りゲームをしています。最初、山が
個あり、
個目の山には
個の石があり、整数
が定まっています。
高橋君と青木君は、高橋君から始めて、交互に以下の操作を繰り返します。
山を 1 つ選ぶ。
個の石が残っている場合、 1 個以上
個以下の任意の個数の石を
先に操作ができなくなったプレイヤーが負けです。両者最善を尽くしたとき、どちらのプレイヤーが勝つか判定してください。
ただし、
で
以下の最大の整数を表します。
制約
入力はすべて整数である。
続きを読む