【AtCoder ABC453AB】
Trim-OとData Log
（Common Lisp）

by
  • AtCoder ABC453のA・B問題をCommon Lispで解きました。
  • A問題では文字列の先頭から連続するoを除去するロジックを自前ループで実装しましたが、string-left-trimを使えばより簡潔に書けます。
  • B問題では直前の保存値との差が閾値X以上のときだけ記録する処理を、loopのwithとwhenを使って実装しています。

関連記事

1. A – Trimo

長さ NN の文字列 SS が与えられます。SS のうち先頭に連続する o をすべて取り除いた文字列を出力してください。

なお、SS 中のすべての文字が o である場合は空文字列を出力してください。

入力は以下の形式で標準入力から与えられる。

N
S

答えを出力せよ。

A – Trimo

例 1

7
ooparts

ooparts のうち先頭に連続する o をすべて取り除くと parts となります。

parts

例 2

6
abcooo

先頭の文字が o でない場合もあります。

abcooo

1.1. 回答

A – Trimo｜先頭の o を除去 問題 文字列 S の先頭に 連続する o を除去 入力 ooparts 出力 parts 実装 自前ループ loop across で先頭を走査 → subseq で切り出し vs 標準関数 string-left-trim 1行で完結

素直に文字列の先頭が文字に合致する間進むことにしました。

(defun solve (n s)
  (declare (type fixnum n)
	   (type string s)
	   (ignore n))
  (subseq s (length-first-char s #\o)))

(defun length-first-char (str ch)
  (declare (type string str)
	   (type character ch))
  (loop for i from 0
	for ch2 across str
	while (eql ch2 ch)
	finally (return i)))

(defun main ()
  (let* ((n (read))
	 (s (read-line)))
    (princ (solve n s))))

#-swank
(main)Code language: Lisp (lisp)
1.1. 回答

ただ、Common Lispには、string-left-trim があるので、実はそのまま解決します。

2. B – Sensor Data Logging

ある測定では、時刻 0,1,…,T0,1,\dots,T におけるセンサーの測定値を以下の規則で記録します。

  • 時刻 00 では、測定値を保存する。
  • 時刻 1,2,…,T1,2,\dots,T では、「現時刻の測定値」と「直前に保存された測定値」との差の絶対値が XX 以上であるとき、またその時に限り値を保存する。

時刻 i=0,1,…,Ti=0,1,\dots,T におけるセンサーの測定値は AiA_i でした。

測定値が保存された時刻と保存された値とを、時刻の昇順に出力してください。

入力は以下の形式で標準入力から与えられる。

T X T\ X A0 A1 … AT A_0\ A_1\ \dots\ A_T

測定値が kk 回保存され、そのうち時刻の昇順に並べた時に ii 回目の時刻が tit_i、測定値が aia_i であったとき、以下の形式で出力せよ。

t1 a1 t_1\ a_1 t2 a2 t_2\ a_2 ⋮ \vdots tk ak t_k\ a_k B – Sensor Data Logging

2.1. 回答

B – Sensor Data Logging time 0 1 2 3 4 t=0 t=1 t=2 t=3 t=4 常に保存 |差| ≥ X で保存 保存条件 |現在値 − prev| ≥ X のとき保存 & prev 更新 loop + with prevを保持しながら 各要素を走査 collect でリスト化 注意点 t=0はprevと同値のため 条件だけでも保存される = time 0 は冗長 入力の罠 Aの要素数は T+1 loop from 0 to T （to は inclusive）

a – prev の絶対値 が X のときだけ計測するので、prevを更新しながら、値のペアを集めることにしました。

(defun measure (X As)
  (declare (type fixnum X)
	   (type list As))
  (loop for a in As
	for time from 0
	with prev = (car As)
	when (or (= time 0)
		 (>= (abs (- a prev)) X))
	  collect (list time (setf prev a))))Code language: Lisp (lisp)

あとは、入出力を整えて完成です。
Anの個数は Tn + 1 なので、そこだけ注意が必要でした。

(defun print-measured (Mn)
  (loop for m in Mn
	  do (format t "~d ~d~%" (car m) (cadr m))))

(defun main ()
  (let* ((Tn (read))
	 (X (read))
	 (An (loop for i from 0 to Tn
		   collect (read)))
	 (Mn (measure X An)))
    (print-measured Mn)))

#-swank
(main)Code language: Lisp (lisp)