AtCoder に登録したら解くべき精選過去問 10 問 を Vim で解いてみた

え、いまさらこのシリーズ?

と言いたいところですが、実は先日AtCoderの言語アップデートのテスト用コンテストが開かれまして、その中に今回追加されたプログラミング言語としてVimが新たに導入されました (要望を取り入れてくださったAtCoderさんありがとうございます🙏)。調べたところこの精選過去問シリーズをVimで解いた人はまだいなさそうなので、Vim初心者ながらプログラミング言語Vimで競技プログラミングに参加するための入門記事も兼ねて↓に掲載されている問題を解いていこうと思います。

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～

なお、AtCoderの言語アップデートはまだ作業中のようですので、今後実行環境が変更ないし削除される恐れがあることにご注意ください。

ちょっと待って⋯⋯「プログラミング言語Vim」って何?

Vimはプログラミング言語です。

主にエディタとして広く用いられるVimですが、その背後には強力なスクリプト言語 (VimScript/VimL) を内蔵しているほか、Vimの通常のエディタコマンドを用いても十分プログラミング言語としての役割を果たすことができます。この性質を用いて、プログラムの入力を「編集前のテキストファイル」、出力を「編集後のテキストファイル」として、入力を出力に「編集」するようなキーボード入力をプログラムとして与えることができます。

この仕様は Yukicoder, Anarchy Golf, VimGolf などの多くのコンテストサイトで採用されており、今回AtCoderに追加されたのもほぼ同じ仕様の実行環境となっています。

まあ、口で説明するより実際に見てみたほうが早いと思います。

肩慣らし: PracticeA - Welcome to AtCoder

まずは精選過去問を解く前に肩慣らしとして練習問題を解いてみます。

【問題概要】
3つの正整数 $a$, $b$, $c$ と文字列 $s$ が与えられます。 $a+b+c$ と $s$ を空白区切りで出力してください。
【入力】
$a$
$b;;c$
$s$

回答例1: 人間向けバージョン

:delete a
:delete f
:delete s
:let a = @a
:let b = split(@f)[0]
:let c = split(@f)[1]
:let s = @s
:put! = (a + b + c) . ' ' . s
:join!
:write
:quit

※提出する際は必ずプログラムの末尾に改行を与えてください。

読みやすいですね! 順番に見ていきましょう。

:delete a
:delete f
:delete s

まず入力が編集前のファイルとして与えられるので、deleteコマンドを用いて入力を切り取りながらレジスタに格納していきます。

レジスタはVimが変数と別に持つ一時的な値の格納場所で、アルファベット1文字の名前を持ちます。例えばaレジスタは@aというふうに参照できます。レジスタは今後も何度もでてくるのでぜひ覚えておきましょう。

:delete a コマンドは1行切り取ってaレジスタに格納する命令です。:deleteコマンドはrangeオプションを指定しない場合現在のカーソルがある位置の行を削除します。ファイルを開いたときVimのカーソルは最初の非空白文字の位置にあるので、この命令は1行目を削除します。これを繰り返して2行目、3行目を同様にfレジスタ、sレジスタに格納します。

:let a = @a
:let b = split(@f)[0]
:let c = split(@f)[1]
:let s = @s

レジスタに格納した値はそのままでは扱いづらいので一旦変数に代入しましょう。:letコマンドで変数の宣言および代入を行うことができます。bとcの値が空白区切りになっている2行目はsplit()関数で配列に分割したあと個別に取り出します。

:put! = (a + b + c) . ' ' . s

計算結果を出力します。.演算子は文字列結合です。:putコマンドでカーソルの位置にテキストを挿入できます。!オプションを追加するとカーソルの一つ前の行にテキストを挿入します。

:join!
:write
:quit

エディタを終了します。ちゃんとファイルを保存してから終了させる必要があることに注意してください。

なおこのままだと余計な改行が出力されてしまうので:joinコマンドで最後の改行を削除しています。

以上で練習問題が解けました。ちなみにVimの特性を使ってもう少し違うふうに解くこともできます。こんなふうに⋯⋯

回答例2: ゴルファー向けバージョン

DJ@"wD0@"JZZ

14 bytes

Vimはコードゴルフ (プログラムをなるべく短く解く競技) にも非常に適した言語です。:で始まるエディタコマンドだけでなく、Vimmerが普段使うようなノーマルコマンドを用いることでテキスト処理を非常に短いストロークで記述することができます。VimGolf.comというVimを用いたコードゴルフの専用サイトもあるくらいです。

上のコードを解説していきます。一見してもわけがわからないコードですが、一つ一つは難しくありません。Vimmerが普段使うコマンドの組み合わせです。

なお、上のコードはASCII制御文字が含まれているので、ここからはわかりやすくするためにVimで用いられる特殊記法<>を用いて記述します。

コード

DJ@"<C-A>wD0@"<C-A>JZZ

次のような入力を考えます。エディタを開いたとき、カーソルは左上の3の位置にあります。

エディタ

3
6 310
hoge

まず最初のDJが処理されます。Dはカーソルの位置から行末までを削除するコマンド、Jは現在の行と次の行を結合するコマンドです。この2つのコマンドを実行すると最初の行がまるごと消えます。

エディタ

6 310
hoge

ちなみにddでも同じ結果が得られますがこちらだと行末の改行文字までヤンクされてしますのでこの後の処理に不都合です。このとき削除された文字列は無名レジスタ""にストアされます。

次に@"<C-A>が処理されます。最初の@"は無名レジスタ""を参照しておりレジスタの中身がそのままノーマルコマンドとして実行されます。

ところで、Vimではほとんどのコマンドに数字を前置して繰り返し回数を指定することができます。たとえばjはカーソルを下方向に移動させるコマンドですが、17jと入力するとカーソルを17行ぶんに動かすことができます。この数値指定にレジスタの値を用いたのが今回のコマンドです。今回の例の場合1行目の3がヤンクされているのでこの次のコマンドが3回実行されます。

<C-A>はカーソルの次に出現する数字をインクリメントするコマンドです。現在カーソルは左上の6の位置にあるのでこの数字が3回インクリメントされます。つまり3+6が計算されて9に置き換えられます。

エディタ

9 310
hoge

この処理が終了したあと、カーソルは9の位置にあります。このあとwコマンドを実行してカーソルを310の先頭の3の上に置きます。

ここで再びDコマンドを実行し、カーソル位置から行末までを削除し、0で行の先頭に移動します。310が無名レジスタに格納されます。

エディタ

9 
hoge

あとは先ほどと同じように@"<C-A>を実行して無名レジスタの310を9に加算します。

エディタ

319 
hoge

最後にJを実行して行を結合し、ZZを実行します。ZZは:exitのエイリアスで、たった2文字でファイルを保存して終了する便利コマンドです。Vimゴルフは基本的にこのコマンドで終了させます。

エディタ

319 hoge

以上で肩慣らしは終了です。それでは精選過去問のほうもサクサク解いていきましょう。

第 1 問: ABC 086 A - Product (100 点)

【問題概要】

二つの正整数 $a$, $b$ が与えられます。 $a$ と $b$ の積が偶数か奇数か判定してください。

【制約】

• $1 \le a, b \le 10000$
• $a$, $b$ は整数

回答例1

:normal "adw"bdw
:put! = @a * @b % 2 == 0 ? 'Even' : 'Odd'
:wq

いちいち:deleteで値を取得するのはめんどくさいのでdコマンドでレジスタに格納しています。

ちなみに、:putコマンドの式ではダブルクオートをエスケープしないといけないので注意してください。ここでは回避するためにシングルクオートを使用しています。

回答例2

f r*0C<C-R>=<C-R>"%2?"Odd":"Even"
<Esc>ZZ

29 bytes

あまり真面目にゴルフできてないですがいちおうゴルフバージョンです。スペースを*に置換したあとヤンクして<C-R>=でエクスプレッションレジスタを挿入し<C-R>"でヤンクしたテキストを貼り付けています。

第 2 問: ABC 081 A - Placing Marbles (100 点)

【問題概要】

0 と 1 のみから成る 3 桁の番号 s が与えられます。1 が何個含まれるかを求めてください。

回答例1

:normal! "ax"bx"cx
:put! = @a + @b + @c
:wq

やるだけです。

回答例2

YPJwx@"<C-A>wx@"<C-A>0dwZZ

18 bytes

最初にYPJで入力を前後にコピーします。後ろの方のテキストを1文字ずつヤンクして@"<C-A>を実行します。Vimで0は繰り返し回数として認識されず行頭に移動するので0のときは前の数値が、1のときは後の数値がインクリメントされます。最後に前の入力を削除して終了です。

第 3 問: ABC 081 B - Shift Only (200 点)

【問題概要】

黒板に $N$ 個の正の整数 $A_1, \dots, A_N$ が書かれています。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます。

• 黒板に書かれている整数すべてを，$2$ で割ったものに置き換える。
  すぬけ君は最大で何回操作を行うことができるかを求めてください。

【制約】

• $1 \le N \le 200$
• $1 \le A_i \le 10^9$

回答例1

:normal "ndd
:let r = 99
:for i in range(@n)
  :normal "adw
  :let j = 0
  :let a = @a
  :while a % 2 == 0
    :let a = a / 2
    :let j += 1
  :endwhile
  :let r = r > j ? j : r
:endfor
:put! = r
:wq

ループも使えます。

回答例2

To be written

第 4 問: ABC 087 B - Coins (200 点)

【問題概要】

500 円玉を $A$ 枚、100 円玉を $B$ 枚、50 円玉を $C$ 枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど $X$ 円にする方法は何通りあるでしょうか？

【制約】

• $0 \le A, B, C \le 50$
• $A + B + C \ge 1$
• $50 \le X \le 20000$
• $A, B, C$ は整数である
• $X$ は $50$ の倍数である

回答例1

:normal "add"bdd"cdd"xdd
:let a = 0
:for i in range(0, @a)
  :for j in range(0, @b)
    :for k in range(0, @c)
      :let a += i * 500 + j * 100 + k * 50 == @x ? 1 : 0
    :endfor
  :endfor
:endfor
:put! = a
:wq

回答例2

To be written

第 5 問: ABC 083 B - Some Sums (200 点)

【問題概要】

$1$ 以上 $N$ 以下の整数のうち、$10$ 進法で各桁の和が $A$ 以上 $B$ 以下であるものについて、総和を求めてください。

【制約】

• $1 \le N \le 10^4$
• $ 1 \le A \le B \le 36$
• 入力はすべて整数

回答例1

:normal "ndw"adw"bdw
:let a = 0
:for i in range(1, @n)
  :let n = eval(substitute(i, ".", "+&", "g"))
  :let a += @a <= n && n <= @b ? i : 0
:endfor
:put! = a
:wq

各桁の和を求めるのに置換コマンドを使っています。

回答例2

To be written

第 6 問: ABC 088 B - Card Game for Two (200 点)

【問題概要】

$N$ 枚のカードがあり、$i$ 枚目のカードには $a_i$ という数が書かれています。
Alice と Bob はこれらのカードを使ってゲームを行います。ゲームでは 2 人が交互に 1 枚ずつカードを取っていきます。Alice が先にカードを取ります。
2 人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2 人とも自分の得点を最大化するように最適戦略をとったとき、Alice は Bob より何点多くの得点を獲得できるかを求めてください。

【制約】

• $N$ は $1$ 以上 $100$ 以下の整数
• $a_i$ は $1$ 以上 $100$ 以下の整数

回答例1

:normal "ndd
:s/ /\r/g
:sort! n
:let r = 0
:normal gg
:for i in range(@n)
  :normal "add
  :let r += i % 2 ? -@a :@a
:endfor
:put! = r
:wq

:sortコマンドは指定した範囲を行単位でソートしてくれる便利コマンドです。

回答例2

dd:s/ /\r/g
:sor! n
:%s/\n/\="-+"[@a+setreg('a',!@a)]/g
C<C-R>=<C-R>"0
<Esc>ZZ

66 bytes

長い⋯⋯。いちおうソートしたあと改行を+と-に置き換えてevalするということをしています。setregはレジスタへの代入が成功したかを返り値として返します。Vimでは真偽値という型はなく0か1かで表現されるので、そのまま加算しても無害です。

第 7 問: ABC 085 B - Kagami Mochi (200 点)

【問題概要】

$N$ 個の整数 $d[0], d[1], \dots, d[N-1]$ が与えられます。
この中に何種類の異なる値があるでしょうか？

【制約】

• $1 \le N \le 100$
• $1 \le d[i] \le 100$
• 入力値はすべて整数

回答例1

:normal dd
:sort u
:let a = line('$')
:normal ggVGd
:put! = a
:wq

:sortコマンドで重複行を削除したあと、行数を取得して出力します。

回答例2

C0<Esc>:sor u
qqJD<C-A>@qq@qZZ

22 bytes

最初に1行目を破滅させて0に置き換えます。この0は後ほどカウンタ変数として使われます。この0を含めてソートすると必ず先頭に0が来ます。qq~~@qq@qはまるで呪文ですが再帰マクロです。JD<C-A>は下の行を削除して現在の行をインクリメントする操作です。この操作は下の行が存在しないときに失敗して停止するので、結局カウンタが行数の数だけインクリメントされて終了します。

第 8 問: ABC 085 C - Otoshidama (300 点)

【問題概要】

10000 円札と、5000 円札と、1000 円札が合計で $N$ 枚あって、合計金額が $Y$ 円であったという。このような条件を満たす各金額の札の枚数の組を 1 つ求めなさい。そのような状況が存在し得ない場合には -1 -1 -1 と出力しなさい。

【制約】

• $1 \le N \le 2000$
• $1000 \le Y \le 2*10^7$
• $N$ は整数
• $Y$ は $1000$ の倍数

回答例1

:normal "ndw"ydw
:for a in range(0, @n)
  :let money = @y - a * 10000
  :let cnt = str2nr(@n) - a
  :let b = str2float(money - 1000 * cnt) / 4000
  :let c = cnt - b
  :if b >= 0 && c >= 0 && fmod(b, 1) == 0
    :put! = a . ' ' . float2nr(b) . ' ' . float2nr(c)
    :wq
  :endif
:endfor
:put! = '-1 -1 -1'
:wq

floatの扱いがめんどくさいです。Vimではintとstringは結合できますがfloatとstringはそのまま結合できないので一度intに変換してから結合しています。

回答例2

To be written

第 9 問: ABC 049 C - Daydream (300 点)

【問題概要】

英小文字からなる文字列 $S$ が与えられます。
$T$ が空文字列である状態から始めて、以下の操作を好きな回数繰り返すことで $S = T$ とすることができるか判定してください。

• $T$ の末尾に "dream", "dreamer", "erase", "eraser" のいずれかを追加する。

【制約】

• $1 \le |S| \le 10^5$
• $S$ は英小文字からなる

回答例1

:g/\v^(dream|dreamer|erase|eraser)*$/normal D
:put! = @\" == '' ? 'NO' : 'YES'
:normal jdd
:wq

Vimの利点の一つである正規表現で一発判定します。先ほど述べた通り:putコマンド中でダブルクオートはエスケープする必要があるので注意してください。

回答例2

iNO <Esc>@="/\\v<([ed]re*a.e*r*)*$\nSYES "
<Esc>DZZ

43 bytes

この問題の現最短コードから正規表現を拝借します。最初に先頭にNO[space]を挿入し@=で式評価によるマクロを実行します。\vはVimの正規表現の magic mode に移行するコマンドで、バックスラッシュなどのエスケープを省略できるようになります。今回の場合使いたい正規表現が文字列リテラルの中に入ってるので有効です。その後の\<は word boundary にマッチするメタ文字です。マクロはコマンドが失敗した時点で停止するのでマッチしなかった場合この語の処理は実行されません。マッチした場合SYES <Esc>で行を削除しYES[space]を挿入します。最後にDで余分な文字を削除します。

第 10 問: ABC 086 C - Traveling (300 点)

【問題概要】

シカの AtCoDeer くんは二次元平面上で旅行をしようとしています。AtCoDeer くんの旅行プランでは、時刻 $0$ に 点 $(0, 0)$ を出発し、$1$ 以上 $N$ 以下の各 $i$ に対し、時刻 $t_i$ に 点 $(x_i, y_i)$ を訪れる予定です。
AtCoDeer くんが時刻 $t$ に 点 $(x, y)$ にいる時、 時刻 $t+1$ には 点 $(x+1,y), (x−1,y), (x,y+1), (x,y−1)$ のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeer くんの旅行プランが実行可能かどうか判定してください。

【制約】

• $1 \le N \le 10^5$
• $0 \le x_i, y_i \le 10^5$
• $1 \le t_i \le t_{i+1} \le 10^5$
• 入力はすべて整数

回答例1

:normal "ndd
:let ct = 0
:let cx = 0
:let cy = 0
:let ok = 1
:for i in range(@n)
  :norm! "tdw"xdw"ydd
  :let distance = abs(@x - cx) + abs(@y - cy)
  :let parity = (distance + @t - ct) % 2
  :if parity == 1 || distance > @t - ct
    :let ok = 0
  :endif
  :let ct = @t
  :let cx = @x
  :let cy = @y
:endfor
:put! = ok ? 'Yes' : 'No'
:wq

やるだけです。

回答例2

To be written

おわりに

疲れました。

ちなみにVimの回答でわからないコマンドが出てきたら:help [command]コマンドを打つとヘルプが表示されます。ちょっと特殊な記号とかでもだいたい一発で出てくるので便利です。