No.620 ぐるぐるぐるりん 解説

問題

No.620 ぐるぐるぐるりん - yukicoder

所与の \( T, w, v, g_x, g_y \) に対して、

\( \left( \begin{array}c x_0 \\ y_0 \end{array} \right) = \left( \begin{array}c 1 \\ 0 \end{array} \right) \)

\( \left( \begin{array}c x_{t+1} \\ y_{t+1} \end{array} \right) = \left( \begin{array}{cc} v+1 & -w \\ w & v+1 \end{array} \right) \left( \begin{array}c x_t \\ y_t \end{array} \right) + \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

\( \left( \begin{array}c x_T \\ y_T \end{array} \right) = \left( \begin{array}c g_x \\ g_y \end{array} \right) \)

を満たし、かつ \( \sum_{t=0}^{T-1} ( u_{x,t}^2 + u_{y,t}^2 ) \) を最小化するような \( u_{x,t}, u_{y,t} \) を求めよ。

解説

\( M = \left( \begin{array}{cc} v+1 & -w \\ w & v+1 \end{array} \right) \)

と置きます。

満たすべき条件は要するに

\( \left( \begin{array}c g_x \\ g_y \end{array} \right) = M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) + \sum_{t=0}^{T-1} M^{T-1-t} \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

ということです。

\( M \) は拡縮と回転の合成変換となっており、拡縮倍率を表すスカラー \( s = \sqrt{(v+1)^2+w^2} \) と回転を表す行列 \( R = \left( \begin{array}{cc} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{array} \right) \) を用いて

\( M = s R \)

と表すことができます。

このうち、回転 \( R \) は \( \sum_{t=0}^{T-1} ( u_{x,i}^2 + u_{y,i}^2 ) \) の値に影響しませんから、

\( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) = R^{T-1-t} \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \)

と置くと、この問題の条件は

\( \left( \begin{array}c g_x \\ g_y \end{array} \right) - M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) = \sum_{t=0}^{T-1} s^{T-1-t} \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) \)

を満たし、かつ \( \sum_{t=0}^{T-1} ( u'_{x,t}^2 + u'_{y,t}^2 ) \) を最小化すると言い替えることができます。

これは、成分ごとに考えれば単なるスカラーの問題として解くことができて(*1)

\( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) = \cfrac{s^{T-1-t}}{\sum_i s^{2(T-1-i)}} \left( \left( \begin{array}c g_x \\ g_y \end{array} \right) - M^T \left( \begin{array}c 1 \\ 0 \end{array} \right) \right) \)

となります。

あとは \( \left( \begin{array}c u'_{x,t} \\ u'_{y,t} \end{array} \right) \) から \( \left( \begin{array}c u_{x,t} \\ u_{y,t} \end{array} \right) \) を復元すれば完成です。

--------

(*1) 球と平面の接点の問題(原点 \( (0,0,0) \) を中心とする球が平面 \( ax+by+cz=d \) に接しているとき、その接点の座標を求めよ)の考え方で解くことができます。

感想

というわけで、ほぼ高校数学の範囲で厳密解を求めることができて、あとは具体的な数値を代入するだけですので、これで★4.5は過大気味ではないかとも思いましたが、実際に解けている人が非常に少なく、強い人も苦労しているようですので、競技プログラミング的には難しい問題のようですね。

No. 410 「出会い」ショートコード解説

はじめに

yukicoder コンテストで出題された問題 No. 410 「出会い」のショートコード(2016年8月13日現在)の解説です。

問題ページ: http://yukicoder.me/problems/no/410

ショートコード: http://yukicoder.me/submissions/110735

問題の概要

入力:

A B
C D

が与えられる(A,B,C,Dは整数)。(abs(A-C)+abs(B-D))*0.5 の値を出力せよ。

私の答案

tr - _|dc -e?sx?sy-d*vlxly-d*v+.5*p

35 bytes です。言語は Bash です。 tr と dc を呼び出しています。 dc は先日 yuki さんにお願いして導入してもらい、使えるようになりました。

dc とは?

逆ポーランド形式の無限精度の計算が行える卓上計算機」だそうです(出典: http://kazmax.zpp.jp/cmd/d/dc.1.html)。今日では、 RubyPython で精度を気にすることなく整数演算ができますが、かつて Perl の時代にはそういうわけにはいきませんでした。なまじっか Perl が使えてしまうせいで RubyPython を覚える気になれない私は、 dc にはまだまだお世話になっています。

コードの解説

まず、 tr - _ で、入力に含まれる - (マイナス)を全て _ (アンダースコア)に変換しています。これは、 dc の入力においては - (マイナス)は二項演算子であり、負号は _ (アンダースコア)で表すことになっているからです。(一方、出力においては負号は - (マイナス)です。つまり、 dc は自分が出力する数値を解釈できないという謎仕様です。)

次に、負号を変換した入力を dc に渡しています。 -e は perlruby の -e と同じで、スクリプトの直接指定です。そのスクリプトをトークンに分解すると、次のようになります。

? sx ? sy - d * v lx ly - d * v + .5 * p

? は、入力を1行読んで実行する、です。最初の ? で入力の A B が読まれ、次の ? で C D が読まれることになります。読まれた値は、スタックにプッシュされます。

sx は、スタックをポップして変数 x に格納する、です。最初の ? の実行後のスタックは A B ですので、 sx で x には B が入り、スタックは A だけになります。同様に、 sy で y には D が入り、スタックは A C になります。

- d * v という一連の命令が2回出てきます。 d はスタック先頭の値の複製、 v は(非負の)平方根です。つまり、スタック先頭の2つの値の差を2乗してその平方根を求めていますので、差の絶対値が得られます。

lx ly は、変数 x と y の値(つまり B と D )をスタックにプッシュします。

+ .5 * で、これらを足して 0.5 倍しています。 .5 *2 / のほうが短そうですが、デフォルトで商が整数になってしまうので、ここではうまくいきません。

p で結果を出力しています。

おわりに

解説の配信のとき、説明が必要っぽい雰囲気だと思ったので、書いてみましたが、いかがだったでしょうか。全く需要がない気もしますが、果たして最後まで読んでくれた人はいるのでしょうか。

gnupack 版 Emacs で IME の on/off に合わせてカーソルの色を変える方法

gnupack 版 Emacs とは

本家 GNU が配布している WindowsEmacs バイナリは、 IME が on のときに

  • 入力中の文字が画面に表示されない
  • C-x b などのキーシーケンスで b が IME に吸われる

などといった不具合があるため、日本語環境ではまともに使うことができません。(なお Emacs 自体が独自の辞書を備えた入力メソッド機能を内蔵しており、そちらを使えば上記の問題は起こりませんが、せっかく IME があるのだからそれを使いたいですよね。)

そこで、 gnupack というプロジェクトが、上記の問題を解決するパッチを当てた Emacs を独自にビルドし配布しています。これのお世話になっている人は多いと思います。私もそうです。

gnupack プロジェクト日本語トップページ - OSDN

(ところで、 gnupack が現在(2016年5月)単体で配布している最新の Emacs は 24.2 と若干古いのが気になります。今後も是非とも本家に追随するか、もしくは上記の問題を解消するパッチを本家に取り込んでもらうようにしてもらえると嬉しいです。なお Cygwin を含むフルパッケージのほうには Cygwin でビルドされた Emacs 24.5.1 が含まれているようですので、そちらを使えということかもしれませんが、 Emacs だけのために Cygwin を丸ごともう1セット導入するというのもなかなか厳しいものがあります。)

IME の on/off に合わせてカーソルの色を変える

例えば IME が on のときだけ Emacs のカーソルが赤くなるようにすると、とても快適です。これについて gnupack 版での設定方法を説明します。(なお MuleMeadow とは設定方法が異なります。また、以下の方法は本家 GNU 配布版 Emacs では使えません。)

やることは以下の3つです。いずれも ~/.emacs.d/init.d に書いておくといいと思います。

1.入力メソッドIME に設定

(setq default-input-method "W32-IME")

初期設定では default-input-method"japanese" に設定されているので "W32-IME" に変更します。この "W32-IME" という入力メソッド名は本家 GNU 配布版には存在しないものです。これを設定することにより、入力メソッドとして IME が使われるようになります。 C-\ (初期設定で toggle-input-medhod コマンドが割当てられている)を押して IME の on/off が切り替わるのを確かめてみてください。

2. [kanji] キーイベントの有効化

(global-set-key [kanji] 'toggle-input-method)

初期設定では [kanji] には ignore が割り当てられているので変更します。これを設定しなくても「半角/全角」キーを押せば IME の on/off は当然切り替わりますが、これを設定することにより、「半角/全角」キーを押して IME の状態を切り替えたときに、次に説明するフックが呼ばれるようになります。また [kanji] キーイベントは「半角/全角」キーを押したときだけでなく、例えば言語バーをマウスでクリックして IME の状態を切り替えたときなどにも発生するため、このときにもフックが呼ばれるようになります。

3.フックの登録

(add-hook 'w32-ime-on-hook (function (lambda () (set-cursor-color "#ff0000"))))
(add-hook 'w32-ime-off-hook (function (lambda () (set-cursor-color "#0000ff"))))

IME が on になったときと off になったときにそれぞれ呼ばれるフックです。ここでカーソルの色を変えています。上記では IME が on のときに赤、 off のときに青ですが、好みに応じて変更してください。

まとめ

以下のコードをあなたの ~/.emacs.d/init.d の最後にコピペして下さい。

(setq default-input-method "W32-IME")
(global-set-key [kanji] 'toggle-input-method)
(add-hook 'w32-ime-on-hook (function (lambda () (set-cursor-color "#ff0000"))))
(add-hook 'w32-ime-off-hook (function (lambda () (set-cursor-color "#0000ff"))))

幾何の問題

知っていればそのまんまですが、知らないと驚くと思います。(私は知らなかったので驚きました。ていうか、答えはわかっていますが解き方がわかりません。)

問題

\(t>0\) とし、点 \(P\) の座標を \((t,\dfrac{1}{2t})\) とします。

2点 \(A,B\) の座標をそれぞれ \((1,1),(-1,-1)\) とします。

このとき、 \(BP-AP\) を求めてください。

(\(BP\)は点\(B\)と点\(P\)との距離、\(AP\)は点\(A\)と点\(P\)との距離。その差を求めてください。)

解説

そうなのです!最初に「知っていればそのまんま」と書きましたが、「逆数のグラフが双曲線であることを」知っていれば、ということです。いや、ちっとも知りませんでした。

なるほど! \(\sqrt{b}-\sqrt{a}\) の形なので、有理化の要領で \(\sqrt{b}+\sqrt{a}\) を掛けたりしてみましたが、複雑化する一方でうまくいきませんでした。まるっと自乗してしまえばいいんですね。素晴らしいです。

解答

\[\begin{align}BP-AP &= \sqrt{(t-1)^2+(\dfrac{1}{2t}-1)^2}-\sqrt{(t+1)^2+(\dfrac{1}{2t}+1)^2} \\ (BP-AP)^2 &= \left(\sqrt{(t-1)^2+(\dfrac{1}{2t}-1)^2}-\sqrt{(t+1)^2+(\dfrac{1}{2t}+1)^2}\right)^2 \\ &= (t-1)^2+(\dfrac{1}{2t}-1)^2 + (t+1)^2+(\dfrac{1}{2t}+1)^2 \\ & \quad - 2\sqrt{\left((t-1)^2+(\dfrac{1}{2t}-1)^2\right)\left((t+1)^2+(\dfrac{1}{2t}+1)^2\right)} \\ &= (t-1)^2+(\dfrac{1}{2t}-1)^2 + (t+1)^2+(\dfrac{1}{2t}+1)^2 \\ & \quad - 2\left(t^2+(\dfrac{1}{2t})^2\right) \\ &= 4 \end{align}\]

よって \( |BP-AP| = 2 \) 。

\(t > 0 \) より \( BP-AP > 0 \) なので \( BP-AP = 2 \) 。

…ということのようです。合ってるかな?

1 から始めて 3x+1 と 4x+1 で生成される数の問題

ふと思い付いた問題ですが、自分ではよくわかりませんので、誰か解いて答えを教えてください。

\(x\) の初期値を \(1\) とします。
\(x\) に対して、次の操作 A または B を選んで、適用します。
A : \(x\) を \(3\) 倍してから \(1\) を加えます。(\(x:=3x+1\))
B : \(x\) を \(4\) 倍してから \(1\) を加えます。(\(x:=4x+1\))
これを任意の回数繰り返します。

例えば、最初に操作 B を行い(\( 1 \times 4 + 1 = 5 \))、次に操作 A を行うと(\( 5 \times 3 + 1 = 16 \))、 \(x\) の値は \(16\) になります。
これを、「 \(16\) の生成列は BA である」と表現します。

別の例として、 \(10000\) の生成列は ABBABBA です(確かめてみてください)。

ここで問題です。

異なる2つの生成列を持つような数は存在するでしょうか?
存在する場合には、例を示してください。
存在しない場合には、それを証明してください。

追記:寄せられた考察(2015年12月9日)

上記の問題に対して、何人かの方から、様々なアプローチの考察を頂きました。ありがとうございます。頂いた順に、結論だけ簡単にまとめて掲載します。(私の解釈に基づいて記載しているため、元々の表現と異なっていたり、結論自体が異なっているものもありますが、ご了承ください。また、最終的な結論の正しさが確認できないものについて、正しいと考えられる中間段階の結論を記載しているものもあります。)

  1. 最後の共通部分を取り除いた2つの異なる生成列の一方は A で終わり、もう一方は B で終わるため、生成される数は奇数である。
    ―― roiti (@roiti46)
  2. 最後の共通部分を取り除いた2つの異なる生成列を持つ数を \(36\) で割った余りは \(13\) である。
    ―― %20 (@henkoudekimasu)
  3. 2つの異なる生成列を持つ数は、4億以下には存在しない。
    ―― ろくかん松 (@rokukan)
  4. 最後の共通部分を取り除いた2つの異なる生成列の一方は AAAAAA で終わり、もう一方は BBB で終わる。
    ―― %20 (@henkoudekimasu)
  5. A のみからなる生成列と B のみからなる生成列とが同じ数を生成することはない。
    ―― %20 (@henkoudekimasu)
  6. 最後の共通部分を取り除いた2つの異なる生成列の一方は BBB で終わるので、生成される数を \(64\) で割った余りは \(21\) である。したがって、もう一方の生成列の最後の A の行う前の値を \(64\) で割った余りは \(28\) となる。
    ―― ぴろず (@p_shiki37)
  7. \( A = \begin{pmatrix} 3 & 1 \\ 0 & 1 \end{pmatrix} , B = \begin{pmatrix} 4 & 1 \\ 0 & 1 \end{pmatrix} \)
    と表現でき、これらを用いた2つの生成列を \( S_1 , S_2 \) とすると、
    \( {S_1}^{-1} S_2 = \begin{pmatrix} a & 1-a \\ 0 & 1 \end{pmatrix} \) の形になる。
    ―― ぬ (@nu4nu)
  8. 操作 A を \(3x+1\) の代わりに \(2x+1\) にした場合には、二進数で表した時に、 A は右に 1 を追加する操作、 B は右に 01 を追加する操作になるため、異なる生成列が同じ数を生成することはない。
    ―― roiti (@roiti46)
  9. 元の問題は、「\(n \ge 1 \) で定義される2つの異なる非負整数列 \( \{p[n]\},\{q[n]\} \) と正整数 \(X,Y \) であって、次を満たすものが存在するか」と同値。
    • \(p[1]=0,q[1]=1\) (「最後の操作が同じでない」と対応)
    • \( p[n+1]-p[n] \in \{0,1\} \) ( \(q\) も同様)
    • \( \sum_{k=1}^{X} 3^{p[k]} 4^{k-p[k]} = \sum_{k=1}^{Y} 3^{q[k]} 4^{k-q[k]} \)
    よって \( \#\{k|p[k]=0\} \equiv 0 \) mod \(3\) などが示される。
    ―― かならい (@sugarknri)

また、以下は私自身の考察です。

\(x\) の初期値を \(0\) にした場合、自明な解 A \(=\) B \(=1\) があります。
また、初期値を \(2\) にした場合、 ABAAAA \(=\) BBBBB \(=2389\) という解が見付かります(なので、解が存在しない証明で、初期値に依存せずに、このケースを含んでしまっているものは、誤りであることがすぐにわかります)。
初期値を他の自然数にした場合も含めて、これら以外に解は見付かっていません。

 

『シンプル・ライフゲーム』に参加した記念(解説なし)

CodeIQ で出題された『シンプル・ライフゲーム』というコードゴルフに参加しました。

codeiq.jp

Perl と C で最短を取ることができました。 Perl は初日からガチで臨んだので、全言語最短が取れて良かったです。 C は締切前日に気まぐれで始めて、ちゃんと競えないタイミングで最短を更新してしまったので、申し訳なかったです。

締切後に解答を公開したところ、 Perl の解説を angel さんが書いてくださいました! いつもながら的確でわかりやすいです。しかも、私のコードからさらに 3 文字も縮めています。

ange1.hateblo.jp

そして、 C の解説を、出題者の ozy さんが直々に書いてくださいました! 三連休の全てに仕事が入っている中、合間を縫って書いてくださったとのことです。

d.hatena.ne.jp

さらに、 CodeIQ MAGAZINE の公式の解説記事で、貴重な文字数をかなり割いて、 Perl の解説を書いてくださいました!「10の極意」など、魅せ方がさすがです。自分のコードなのに、ほほうと思ってしまいましたw

codeiq.jp

以上、 Perl も C も、 angel さんと ozy さんにすっかり解説していただいたので、私から付け足すことは何もありません。ありがとうございます!

 

『デスコロC #1』の感想

はじめに

デスコロC #1』で優勝しました!

codeiq.jp

前回が最終回だった tbpgr さんの『デスマコロシアム』シリーズを引き継いで、新たに ciel さんの『デスコロC』シリーズが始まりました。企画の内容は前シリーズとほとんど変わっていないはずですが、出題者が交代した影響は想像以上に大きいようで、全く違った雰囲気になっています。一言で言うと、超ガチです。スーパーガチです。その理由は、主に次の2点です。

  1. 『デスマコロシアム』シリーズ最大の特徴であった、役によるバトルが、バッサリとカットされ、一切の運要素が排除されています。
    • 前シリーズでは、コード長と言語ペナルティがトップに届いていなくても、僅差ならバトルでの逆転に期待することができましたし、大差でも「デスマーチ」による一発逆転が用意されていました。これにより、誰もが優勝の可能性を持って参加できました。
    • 今シリーズでは、純粋にコード長と言語ペナルティだけで競うため、トップに1ポイントでも負けていれば、絶対に優勝できず、絶望するしかありません。逆に言うと、トップの人はトーナメントの組み合わせにかかわらず優勝が約束されています。
  2. 出力文字列が、かなり複雑なものになっています。もはや、コーディングの工夫だけではどうにもならず、知識、考察、閃きなどの総合力が試されます。

また、途中経過が毎日ではなく数日おきだったり、ツイートのまとめが行われなかったりしたことも、ストイックさを醸し出す要因になっていたと思います。

私は、初日に2桁バイトのコードを提出し、そのまま最後までアベベのごとく独走状態でした。初日に提出した時点では、暫定トップに立ってみたもののすぐに追いつかれて後はガチゴルフ勝負、といういつもの展開を予想していたのですが、意外な展開となってしまいました。

私の解答

print/.$/gfor sort map/.{999}/?$_=$'.$&:y/9Zz0-z/Aa0-z/<s/s$/sNtUUVb/,(A^eUVb)x3822

Perl (83) です。3822回ループを回していますが、このうち先の2822回で1000文字のデータを生成し、後の1000回で1文字ずつローテートさせながら、ソートして出力しています。

問題の解説

この問題の出力文字列は、ある文字列をブロックソート(BWT)した結果になっています。短いコードを書くためには、このことに気付かなければなりません。

どうすればこれがブロックソートだと気付くのでしょうか? 出力文字列を見てまず気付くのは、同じ文字が連続して現れるなど、ある程度の規則性があることです。もちろん、今までのデスマコロシアムの出力文字列にも規則性がありました。今回違うのは、規則性がありながらも、具体的に調べていくと、細かい部分が不規則になっていて、これをそのままコードに落とすのは困難だということです。

次に気付くべきは、文字列の先頭付近にある、あからさまに怪しい $ の文字です。いかにも何かの終端を表していそうです。ところで、上記の Wikipedia の記事によると、ブロックソートの変換後のデータは「ccoaa, 3」のように、変換後の文字列と開始位置の組で表されています。しかし、変換前の文字列に終端文字を付加しておけば、開始位置の情報を別途持たなくても、変換後の文字列に埋め込まれた終端文字の位置から特定することができ、実際にそのような実装も存在します。

したがって、

  • ブロックソートの結果は同じ文字が連続する傾向がある
  • ブロックソートをするときには終端文字を付加することがある

この2つを知っていれば、もしかしてブロックソートかな? と気付くことができます。

推測ができたところで、実際にブロックソートであることを確認してみます。まず、出力文字列に現れる文字の出現頻度を、ASCIIコード順に調べると、次のようになります。

文字頻度
$ 1
0 16
1 16
2 16
3 16
4 17
5 17
6 15

次に、出力文字列を、先頭から、この頻度に従って切り分けてみます。

文字頻度文字列
$ 1 b
0 16 PP00$zzzuuuVVUUU
1 16 QQ11000vvvWWWVVV
2 16 RRR22211wwXXXWWW
3 16 SSS333222xxYYYXX
4 17 TTT444333yyyZZZYY
5 17 UUU555444zzzaaZZZ
6 15 VV66555000bbaaa

ちょうどいい位置で切れていますね。ブロックソートで間違いなさそうです。

次に、ブロックソートする前の文字列の生成ですが、結果記事によると、「線形合同法っぽい方法で生成」できるようです。これは全く気付きませんでした(○○○○○=「ROT13」かな?とか思っていました)。もし気付いていたら、もっと違ったコードになっていたかもしれませんね。私のコードでは、この文字列を6文字単位のローテートと解釈して、 y と s を使ってなんとか生成しています。

(2015/11/7追記)「線形合同法っぽい方法」の部分について、 angel さん(アイコンが急にかわいくなった!)が詳しく考察されています。

ange1.hateblo.jp

ところで、ブロックソートは、データを縮めるための前処理として行われるものですが、今回はコードを縮めるためにわざわざ圧縮元のデータに遡るところが面白いと思いました。下手をしたら、圧縮データを埋め込んで逆符号化したほうが短くなるなんてことにもなりかねないわけで、うまくバランス調整されていると感じました。

f:id:saito_ta:20151105224407p:plain

まとめ

今回の問題はかなり難易度が高かったようで、題意通りに解けた人がわずかしかいなかったとのことですが、私としては、今までの問題よりパズル的な要素が強くて、とても楽しめました。

ciel さん、出題及び集計お疲れ様でした。次回も楽しみにしています。