月報 2020/05, 2020/06

Sun May 17 2020 競技プログラミング

Codeforces が長年青色だったのが, こないだぽんと, 紫になった. 長年といっても, AtCoder に比べて頻繁に参加してたわけでもないけど. どうしても問題文が英語だとね. ともかくこれでようやく, 初めて, Div.1 になる.

あと, つい今したが, Google Code Jam 2020 の Round 2 があった. これで 1000 位以内が通過なのだが, 運の良さも手伝って 755 位で通過した. （正式に確定のメールが来たわけじゃないので取り消されても文句言えないけど.） 通過はどうでもよくて, 初めてコンテストでTシャツを貰うのが嬉しい.

というわけで, プロコンに関する能力の向上を感じる出来事が2つあったのだが, 偉そうにも, 何が向上に貢献したか語ってみる. 2つある.

1. DeepL
2. お酒を飲まない

DeepL は Google 翻訳をも押しのけてあっという間に本物の自動翻訳を我々に授けた. 数式を含んだ文章でも意味を少しも損なわずに日本語にしてくれるので特にプロコンの文章には助かる. 翻訳結果をちらっと眺めて, ものの一秒で 「ああ、第一段落は物語の説明だから読み飛ばしていいな」と判断できるのは大きなアドバンテージだ. というか今まで英語圏の人はそんな有利な状況で戦ってたんだな. ズルい.

お酒を飲まないこと. お酒を飲むことは脳に害があるのは間違いない. 怖いのは, 自分が酔ってることに気づけ無いことにある. 舐める程度の量なら大丈夫 → だいじょばない. 飲んだの昨夜だし大丈夫 → だいじょばない. 1ミリでも入れたなら影響はあるし, 最後に飲んでから丸24時間は酔ってるものと思ったほうが良い. 嘘だと思うなら, 自分で試したら良い. シビアに結果に影響するはずだ.

Sun May 31 2020 dc コマンドの練習

dc はスタックマシンによる計算機を実現するコマンド. ほとんどその操作を1文字のコマンドで行うので, AtCoder でゴルフをやるのに良さそう. というか kotatsugame さんが実際無双してる.

私も使えるようになりたい.

• マニュアル
  • kazmax.zpp.jp/cmd/d/dc.1.html

整数/少数に関する演算は普通のスタックマシン. 文字列が扱える. 文字列は文字列として表示する以外に, それ自体を dc のコマンド（のマクロ）として使うことが出来, マクロ実行に関するコマンドも用意されてる. 例えば条件分岐して実行するとか. つまり if 文と同じことが使える.

よし一通り読んだ. いくつかは意味がわからなかったけれど.

AtCoder 過去問を dc で解いてく

最近の問題から順に, A/B 問題を中心に埋めてく. いきなりゴルフをできるわけもないので素直に解いてく.

ABC168/A

いきなり数一個を標準入力から読む方法が分からない. ? で一行読んで dc として実行をするらしい. プロコンだと入力はスペース区切りで数字が並んでるので, スタックに入力を積むという操作をひたすらしてくれる.

条件分岐をして, 3種類のいずれかを実行すればいい.

[[hon]pq]  # [hon] を `p`rint して `q`uit するというマクロ
sh         # これを `h` に `s`tore する

[[bon]pq]  # 同様
sb

[[pon]pq]  # 同様
sp

?          # 入力 (数が一つスタックされる）
10%        # 10 で割った剰余を取る

d          # `d`uplicate
3=b        # それが 3 と等しかったら `b` を実行
           # `=` はスタックから取り出して剰余が消えてしまうので,
           # duplicate しておく必要があった

# if 0= or 1= or 6= or 8=
d0=p
d1=p
d6=p
d8=p

# else
lh         # `l`oad `h`
x          # e`x`ecute

最後の else は, 各マクロを全部 q で quit してるからそれ以降は実行されないことを利用している. のだが, これを動かすと期待通りの出力をした後に Exit code 1 で終了し, AtCoder では RuntimeError となる. なぜだろう. わからないが, マクロの最後の q をやめると解決した. このために else のようなことが出来なくなり, いくつか修正して

[[hon]n]
sh
[[bon]n]
sb
[[pon]n]
sp
?
10%
d3=b
d0=p
d1=p
d6=p
d8=p
d2=h
d4=h
d5=h
d7=h
d9=h

これで通った. q を消した以外に, 文字列の出力に n を使っている. しかし q で exit 1 するのはなんで？？？

ABC168/B

文字列の処理...? 分からないし他に提出してる人もいない. パス

ABC169/A

パス

ABC169/B

答えを先にいうと, \(\min(A,K) - \max(K-A-B,0)\) .

min や max は < による条件分岐で実現できるが, else 相当をぱっと書けなくて then 節だけでどうこうするようになってるので, \(\min(A,K)\) は

let mut a = A;
if A > K {
    a = K;
}

ってやる.

?
sk
sc
sb
sa

lklalalk
# Stack = K A A K
[r]sr
<r
# if A < K:
#   Stack = A K
# else:
#   Stack = K A
lkla-lb-
sd
# Reg[d] = (K-A-B)
ld 0
# Stack = _ _ (K-A-B) 0

[ld-]
sr
<r
# if (K-A-B) < 0:
#   _ _
# else
#   _ (_ - (K-A-B))
p

コメントを省いて不要な改行空白を除くと

?skscsbsalklalalk[r]sr<rlkla-lb-sdld0[ld-]sr<rp

で 48 byte. ちなみに現在の dc での最短は 23 byte abc167/submissions/13161505 . レベルが違う. 無駄なロード/ストアをしないで, できるだけスタック上だけで操作してそう. < が2つ登場してるので2回大小比較してるのは同じ？

ABC166/A

入力は文字列 "ABC" または "ARC". これを ? で受け取ってみると,

ABC
f
1122

c

ARC
f
12

この動作を完全に説明することは出来ないが, どうやら dc は強引に 16 進数として読める部分だけを読んでくれるらしい. 例えば "F" は 15 を表す. というわけで入力を受け取って "F" との大小比較をすることで所望の条件分岐が出来そう.

[[ABC]n]sb
[[ARC]n]sr
?d
F<r  # if "F" < input() then "ABC"
F>b  # if "F" > input() then "ARC"

dc で一位の人の 14 byte コード. https://atcoder.jp/contests/abc166/submissions/12790872

整数を print すると ascii コードとして見てやってくれるらしい. "ABC" も "ARC" も真ん中の一文字が違うだけなので, 条件分岐を作らずに上手く出力させてる.

Sat Jun 06 2020 WSL2 にした

ちょうど先週に Windows build version 2004 をインストールして, WSL2 が使える環境になった.

PowerShell から

PowerShell> wsl --list -v
  NAME                   STATE           VERSION
* Ubuntu                 Running         1

> wsl --set-version Ubuntu 2

(数十分待つ)

PowerShell> wsl --list -v
  NAME                   STATE           VERSION
* Ubuntu                 Running         2

人によって "Ubuntu" のところは "Ubuntu-18.04" だったり. 同じコマンドで 1 に戻すことも出来る. この変換の作業は数分掛かるとメッセージに表示されるがこれは嘘で, 数十分だと思ったほうがいい. そのイメージのサイズによる. まっさらな入れたての Ubuntu イメージなら1分掛からないから.

これを先週の金曜日にやったのだが, WSL内 Ubuntu18.04 から外の世界にネットワークにつながらない問題が発生した. インターネットはおろか, Windows にも繋がらないので, 例えば X サーバとのやりとりが出来なくて困った.

今日またトライしたら今は動いた. 正直原因が分からない. 先週から今日までで, やったこととしては

1. 今 2 にした WSL/Ubuntu を 1 に戻した
2. Windows 自体の再起動
3. WSL/Ubuntu-20.04 イメージのインストール
   • WSL1 の状態でインストールされたので 2 に変換し, 普通に使えることを確認
4. WSL/Ubuntu をまた 2 にしてみた
   • 動いた

怪しいのは Windows の再起動か, あるいは WSL2 への変換を何度かやると上手く行くときと上手く行かないときとがある? とかか.

何はともあれ動いた. いくつか設定は変える必要がある.

追記 (2020/06/08 12:36)

ネットワークが死ぬ原因が今分かった. 会社のVPNに接続するのに "Cisco AnyConnect ナンタラ Client" というのを使ってるんだけど, これで VPN に繋いでる間は死んでた. VPN 接続をやめたら解消された. 設定で Allow local (LAN) access を許可し, Block connections to untrusted servers をオフにしたら問題が解決した!!

docker

Windows に Docker Desktop を入れるのがいい. 最新のものは WSL2 Integration なんてものがあるのでそのあたりの設定を全てオンにする. すると, WSL2/docker と WSL2/docker-data というイメージが追加されて起動される. WSL2/Ubuntu からは Docker Desktop の方が見えるようになっており, シームレスに利用できる. このとき DOCKER_HOST といった環境変数は消しておくこと. apt で入れていたかもしれない docker-ce は不要なので紛らわしくないように消す. クライアントコマンドとして docker-ce-cli は引き続き必要なので残す.

unset DOCKER_HOST
sudo apt remove docker-ce
sudo apt install docker-ce-cli

シームレスに使えることもだけど, 問題の一つであった, Windows から WSL が見えないので volume が出来ない問題も普通に解決されている

docker run -v $(pwd):/hoge --rm -it python:3.7.7-slim ls /hoge

X11

Xサーバとして VcXsrv を使う. 外にもあるだろうが知らない.

VcXsrv の設定は qiita.com/ryoi084/items/0dff11134592d0bb895c これを参考にする.

WSL2 からXサーバの接続先を教えるのに環境変数 DISPLAY をセットする必要がある. 今までの WSL1 では単に DISPLAY=:0 とか DISPLAY=:0.0 で良かったが, WSL2 からは Windows の IP を教える必要がある. これもさっきの Qiita にも書いてあることだけど

export DISPLAY=$(cat /etc/resolv.conf | grep nameserver | awk '{print $2}'):0

とすればok.

Sun Jun 07 2020 GCJ Round3 2020

参加者は 621 人, 全体順位は 482 位でした ( 順位表 ).

2時間掛けて A 問題にしか手をつけられなかった. 1時間掛けて何も出来なかった時点でようやっと他の問題を眺めるくらいはしたけど, Aがマシだった.

普通に DP で編集距離 d(s,t) を求めるやつを書いて, それをたどって文字列 s を t に変換するような編集履歴を作って, 半分だけやる. 残りはやらない. というのを気合で書いた.

いや, 最初からこの方針を取ってたんだけど, 上手く行かない, 別なアプローチを試そう, やっぱりこれを修正してもっかいやろう, みたいなのを2時間ずっと繰り返してた.

提出して A-small が通ったのを横目にもう一度自分の提出したコードを見たら, 少なくとも自分の意図に反した条件式のミスを見つけて慌てて修正するも時間切れ. しかしなぜか A-large もそれで通ってしまった. もう何も分からん.

Sat Jun 13 2020 アソビ大全を買った

買った. 普通に遊べるものから, 一度やったら満足して二度とプレイしないようなゲームまでが収録されている.

一つが "ウサギと猟犬" というやつで, ウサギ陣営と猟犬陣営に分かれて二人でやる完全情報組み合わせゲームなのだが, 初期配置にもよるけど十中八九ウサギが勝つようになっている. これを収録する意味とは？

英語だと "Hare and Hounds" とか "Hare Games" とか言うらしい.

cympfh/hare-and-hounds

だいぶソースコードが汚くなってしまった. 毎回 3 手先までは真面目に読むということを再帰でさせるのだが, 同じ局面が何度も出現しうるゲームなので, 簡単に無限ループに入ってしまって, 上手に書けなかった. 3手先以降はもうランダムに打って場面を評価させるようにした. 普通に最善であるだろう手を打てるようになった.

"コネクトフォー" ("重力付き四目並べ") というゲームが収録されている. 大昔に親に買ってもらって遊んだ記憶がある. 先手必勝であることが証明済みらしいが, 人間にとって全然楽しい.

こちらはさっきのゲームと違って, 同じ局面は登場しないで一方向に進むだけだし, 毎回打てる手はたかだか 7 通り（どの列にコインを入れるか）しかないので, AI はどうやっても書ける.

cympfh/connect-four

これは局面の読みに再帰も使わずに, 二手先（自分が打って, 相手が打った後の局面）までを読んで局面の評価を min-max させる. 局面の評価は, ランダムにプレイさせて自分が勝つ回数を使って勝つ確率を推定させてそれを使った. ここの試行回数が露骨にAIの強さに反映される. 300 回程度以上からはあんまり上がらない.

2つ AI を書いたけど, どっちも局面を与えたら最善の手を打った後の局面を返すだけのプログラムとして書いた. UNIX 的なあるいはプロコン的な UI なのでAI部分を書くのだけに集中できて便利.

Sat Jun 13 2020 Q# に入門した

Codeforces で "Microsoft Q# Coding Contest" というのが今日から三日間やっていて （今回のはあくまで Warm up という位置づけ）, 気まぐれで参加してみた. 名前の通り Q# 限定のコンテストで, Q# を学ぶ必要がある. しかしこの言語, ドキュメントがあまりに不足していて辛い. さっさと全問通してしまってる人たちは Microsoft の Quantum チームの人たちじゃないのだろうか？

Sat Jun 13 2020 何が思想か？

何を思想的と思い, 何は思想的でないと思うのだろうか. また思想的でないものを我々はなんと呼ぶべきだろうか.

案

人によってたやすく公理が違うときがある. その公理系と直結する定理群を思想と呼ぶ. 例えば社会主義思想はそれを支える考え（土地は国が所有すべき, 職業は国がコントロールすべき）は正しいと仮定して話を進める. その正しさをサポートするエピソードをたくさん用意しているだろうが, 別にその正しさとは独立だ. その仮定は簡単に他に移住することが出来る.

人の思想に踏み込むのは危険で, 例えば今からラーメン屋に行く人に対して, 自分がダイエットしてるからとかという理由で, その人に他を薦めるのはいい迷惑だ. 人はダイエットすべきというのはあなたの思想であり, 彼には彼の思想がある.

主観的なものをカッコよく思想と呼んでるのかもしれない. だとすれば客観的な事実を述べるのは思想ではないということになる.

感情は思想

好き嫌いは人によってたやすく変わる. 目の前に出された納豆で喜ぶ人もいれば悲しむ人もいる. 人に押し付けてはならない.

感情は社会的なものから本能のものまである. 本能のものとは, 死を恐れる感情などだ. 例えば, 東京タワーとかにある, 足元がガラス張りの床の上に立つスリルを提供するあれがある. あれが割と平気な人もいれば, 絶対無理な人もいる. 後者にとってはそれはまさに死への恐怖だから, それは自然な感情だ. だからお前もそんなところに立つな, と人に警告するのは思想の押し付けに当たる.

理性は思想

理性的な態度は賢さであり, 感情の対極であり, 美徳だと思われる. しかしこれも思想だ. 共産主義者宣言はまさか一時の感情をぶつけてかきあげた文章ではない. あれは理性の塊であるし, 思想の塊でもある.

客観性について

円周率はいくらです, という宣言に主観性はなさそうに思える. 思想的と呼べる隙も全くなさそうに見える.

私はりんごが好きです, という宣言にも主観性がないと言える. 実際にりんごが好きなのであれば揺るぎない事実である. 仮にその私をAさんと呼ぶ. 誰が「Aさんはりんごが好きだ」と言っても常に事実でありえるなら, どこに主観性があるだろうか.

しかしその話題はとても主観的だ. 嫌いな人もいる, という一般化をすることもできるからだ. その一般化に意義があるかどうかは置いておいて.

それで, これは思想なのか？

Mon Jun 15 2020 dc やってく

dc はパズルとして面白い. 逆に本来の計算機として使う人なんていないんじゃないだろうか. シェルスクリプトからさっと呼ぶ計算コマンドとして使えなくはないけど.

man

マニュアルとして man dc があるが, ここには主要コマンドが載っているだけで, そこに載っていないコマンドや仕様がある. ソースコードをこないだ読んでまとめた → memo/dc .

tac

何行かわからないけれど何行かの整数が与えられる. これを逆順に出力せよ.

例えば

   seq 5 | dc -e '(FILL YOUR CODE)'
5
4
3
2
1

ここで入力が整数だけとしているのは dc に都合が良いから ( ? で読めるから). 何行か分からないというのが dc に優しくない. ? はちょうど一行を受け取って, dc コマンドとして実行する.

一旦問題を易しく

   seq 5 | tr '\n' ' ' | dc -e '(FILL YOUR CODE)'
5
4
3
2
1

だとする. ここで seq 5 | tr '\n' ' ' の出力はちょうど一行の

1 2 3 4 5

である. ? は一行読み込んで実行する. 1 2 3 4 5 というのは dc 的には, 5 つのコマンドから成っている（空白区切りで）. 1 というコマンドはスタックに 1 を積む操作にほかならない. 2 から 5 も全く同様. というわけで,

seq | tr ... | dc -e '?'

をすると内部のスタックに

(TOP)
5
4
3
2
1
(BOTTOM)

という状態を残して終了する. 何もプリントさせてないので何も出力しないで終了するが, f はこのスタックの状態をプリントしてくれる. このとき, 今上に書いたように, スタックの頭から順に書いてくれる. というわけで,

   seq 5 | tr '\n' ' ' | dc -e '?f'
5
4
3
2
1

で tac が出来た.

じゃあ元の問題に戻る. tr とかを挟まずに直接 dc に入力が渡されるパターン.

この入力のとき, 一回 ? を読んだところで一つの数値をスタックに積むことしかできない. z コマンドは現在のスタックのサイズ（長さ, 深さ）を取得する. ? で読んで入力がない場合, 何も実行されないのでスタックサイズが変わらない. ということで, この２つを組み合わせればできそうだ.

擬似コードで書くと次のような感じ:

seq 5 | dc -e '
  stack_size = 0  # 前のスタックサイズを記録しておく変数
  loop {
    ?
    # z() で現在のスタックサイズを取得
    if (stack_size < z()) {  # 増えてるということは入力を受け取ったということ
      stack_size = z()
      continue
    } else {
      break
    }
  }
  f
'

こんな上手い loop や if は dc には用意されていない.

もう１段階 dc に近い擬似コードに翻訳するとこんな:

seq 5 | dc -e '
  var@ = 0
  function r() {
    ?
    tmp_@ = var@
    var@ = z()
    if z() < tmp@ {
      r()  # recursive call
    }
  }
  r()
'

これを完全に翻訳して次を得る.

   seq 5 | dc -e '0s@[?zdl@rs@<r]dsrxf'
5
4
3
2
1

[...] が function の中身.

スタックサイズを記録するのにレジスタ @ を使ってるが, 入力が整数しか無い場合 scale レジスタが使える. s@ が k にできて, l@ を K に置き換えて良くなる. しかもこれは最初 0 で初期化されてるのも都合が良い.

seq 5 | dc -e '[?zdKrk<r]dsrxf'

Tue Jun 30 2020 PS2で遊んだゲーム

ビブリボン (PS)

これをやりたいためにPS2を買ったので. 音ゲーなんだけど自分の音楽CDで遊べるというPS初期ならではのシステム素晴らしい. それはいいんだけど, 難易度調整の概念がなくて基本難しい譜面ばっかり生成されてしまうのが厳しい.

塊魂 / みんな大好き塊魂 (PS2)

私でもタイトル知ってるくらいだし面白いんだけど, PS2のコントローラーでやるには操作が繊細すぎる. ハードがソフトにまだ追いついてない感じ.

ところでメモリーカードを持ってないのでPS2の電源を切る前にクリアしきらないといけないのが辛い.

シーマン (PS2)

さくさく育ってくれてる間は楽しい. 育成ゲームの皮を被ってるが普通にストーリーを楽しむゲーム. 数日放置すると死ぬらしいけど, 海に放っておけば大丈夫という設計が上手い. 旅行とか行く前にそれをやっておけば安心というね. しかしイグアニー（イグアナもどき）になってから一向にストーリーが進まない. バグか???

かまいたちの夜 (PS)

2日でクリアできる分量なのがいい. エロゲとかだと始めてからいずれかのエンドまでやるのにも半日かかるけど, これは一時間くらいで終わる. 分岐地点でいちいちセーブしなくても（そもそもメモリーカードないのでセーブ出来ないけど）記録されて自由に行き来できるのも易しすぎる.