えびちゃんの日記

えびちゃん（競プロ）の日記です。

ABC 357 C 埋め込みに関して

「埋め込みするにあたってもちゃんとしたコードを書く必要があるじゃん」という声が聞こえたので、ちゃんとしたコードを書かずにやる方法に言及します。 エディタの機能を使いこなすことが重要です。

エディタでの操作

レベル $K$ のカーペットを得ている状態からレベル $K+1$ のカーペットを得る操作の一例を考えます。わかりやすさのため、$K=1$ としたときのテキストを添えながら書きます。

###
#.#
###

(1) 全体を矩形選択*1してコピーしておく。

(2) 全体を矩形選択し、全ての文字を . で置き換える。

...
...
...

(3) (1) でコピーした内容を先頭に貼りつける。

###...
#.#...
###...

(4) カーソルを先頭行の末尾に移動し、末尾に再度貼りつける。

###...###
#.#...#.#
###...###

(5) 全体の内容を切り取る。





(6) (1) でコピーした内容を 3 回（横方向に繰り返すように）貼りつける。



#########
#.##.##.#
#########




(7) 末尾に移動し、(5) で切り取った内容を貼りつける。



#########
#.##.##.#
#########
###...###
#.#...#.#
###...###




(8) 末尾に移動し、(1) でコピーした内容を 3 回貼りつける。



#########
#.##.##.#
#########
###...###
#.#...#.#
###...###
#########
#.##.##.#
#########




(9) 保存する。



できました。



Vim の紹介



ここで、各操作は Vim*2のコマンドで実現することができます。



    

  • (1) <CTRL-V>G$"ay
    • 

  • (2) <CTRL-V>G$r.
    • 

  • (3) "aP
    • 

  • (4) $"ap
    • 

  • (5) "bdG
    • 

  • (6) 3"aP
    • 

  • (7) Go<ESC>"bP
    • 

  • (8) G3"ap
    • 

  • (9) ZZ
    • 





<CTRL-V> と <ESC> はそれぞれ「control を押しながら V を押す」「esc を押す」です。



たとえば、下記のような内容（<CTRL-V> と <ESC> の箇所は、それぞれ 0x16, 0x1B の文字コードを持つ文字を直接なんとかして入力する）を c.vim という名前で用意しておきます。



<CTRL-V>G$"ay<CTRL-V>G$r."aP$"ap"bdG3"apGo<ESC>"bPG3"apZZ




また、c-out.txt という名前のファイルに下記を書き込んでおきます（レベル $K=0$ のカーペット）。



#




これに対して、下記を実行することで、レベル $K+1$ のカーペットが得られます。



% vim -N -i NONE -u NONE -s c.vim c-out.txt 2>/dev/null






補足



使った機能の説明です。



    

  • <CTRL-V>：矩形選択の開始
    • 

  • G：最終行に移動
    • 

  • $：行末に移動
    • 

  • "ay：a という名前のレジスタにコピー
    • 

  • r.：. に置換
    • 

  • "aP：a という名前のレジスタから（カーソルの前に）貼りつけ


      

    • 3 を前置することで 3 回繰り返す
      • 

    

    • 

  • "ap：a という名前のレジスタから（カーソルの後に）貼りつけ
    • 

  • "bdG：最終行までを切り取り、内容をb` という名前のレジスタに入れる
    • 

  • o<ESC>：カーソルの下に行を追加する


      

    • o で挿入モードになったのを <ESC> で解除する
      • 

    

    • 

  • ZZ：保存する
    • 





（補足おわり）




最近は “Vim-like な” キーバインドを提供する IDE もあるようですが、こうした機能をサポートしているのかは知りません。
それからえびちゃんは Emacs を普段使いしていますが、実は Vim のことも好きです。



埋め込み



さて、埋め込んだ結果、次のような内容のファイル c.py が得られます。



S = [
    "#",
    """###
#.#
###""",
    ...,  # K = 2 のときの答え
    ...,  # K = 3 のときの答え
    ...,  # K = 4 のときの答え
    ...,  # K = 5 のときの答え
    ...,  # K = 6 のときの答え
]
n = int(input())
print(S[n])





$K=6$ のときは $3^{12} \approx 5.3\times 10^5$ 文字となり、提出コード長制限の 512 KiB を上回ってしまいます。
試しにファイルの内容を gzip -9 で圧縮してみると、十分小さくなりそうなことがわかります*3。



% cat c.py | gzip -9 | wc -c
    5897





これを（提出コードに入れやすいように）Base64 でエンコードします。4/3 倍程度になってしまいますが全然問題ないでしょう。



% cat c.py | gzip -9 | base64 | fold -w76
H4sIAAAAAAACA+3dUa4kRQ4F0P9YReu9H5BQ7YBV8IlYAD+t0YjZ/zTqAXrqUakqE5nhsI8VIwVY
...
+/778a9///6PP/38+Zfvx38BHgVMXiMkCQA=





あとは記事の冒頭のツイートのように直接シェルから実行してもよいですし、そういうのが嫌であれば Python で exec してもよいでしょう。



# Zsh
echo 'H4sIAAAAAAACA+3dUa4kRQ4F0P9YReu9H5BQ7YBV8IlYAD+t0YjZ/zTqAXrqUakqE5nhsI8VIwVY
...
+/778a9///6PP/38+Zfvx38BHgVMXiMkCQA=' |
    base64 -d | gunzip > main.py
python3 main.py







# Python
from base64 import b64decode
from gzip import decompress

SRC = """
H4sIAAAAAAACA+3dUa4kRQ4F0P9YReu9H5BQ7YBV8IlYAD+t0YjZ/zTqAXrqUakqE5nhsI8VIwVY
...
+/778a9///6PP/38+Zfvx38BHgVMXiMkCQA=
"""

exec(decompress(b64decode(SRC)))





所感



久々にこういう遊びをした気がします。
この手の考え方も選択肢に入れておくと、何らかの局面で役に立つこともあるのではないでしょうか。



補足：コンテスト中は（いわゆる正攻法の）再帰のコードを Rust で書きました。



おわり



おわりです。




*1:矩形は「くけい」と読みます。多くのエディタでできる操作だと思います。


*2:Vim というのはエディタの名前です。そういうエディタがあります。


*3:同じようなパターンの繰り返しでできる文字列なので、納得感はあります。