UWSCでエンジニアならば1時間以内に解けなければいけない問題をチートして解く

こんぴーた UWSC

問4と問5を解答例を見て解いてみました。
問4は、解答例にヒントないのね。
問5の解答例は素晴らしい。



問4と5の関数

問題等や他の解答は、
UWSCでエンジニアならば1時間以内に解けなければいけない問題を解く - じゅんじゅんのきまぐれ
を参考にしてください。（リンク先の問4の解答にはバグがあるのは秘密です）
どちらも、リンク先と比べて数倍早いです。はい。

FUNCTION Q4F(q[])
	RESULT = ""
	DIM i, in, s, f, m, p, b, c, j, pb
	FOR i = 0 TO LENGTH(q) - 1
		in = i
		s = 1
		f = TRUE
		m = LENGTH(q) - 1
		p = ""
		WHILE f
			c = COPY(q[i] + p, s, 1)
			FOR j = i + 1 TO m
				b = LENGTH(q[j])
				IFB s <= b THEN
					pb = COPY(q[j], s, 1)
					f = TRUE
				ELSE
					pb = COPY(p, s - b, 1)
				ENDIF
				IFB pb >= c THEN
					IFB pb = c THEN
						in = in + 1
					ELSE
						in = i
						c = pb
						f = FALSE
					ENDIF
					b = q[j]
					q[j] = q[in]
					q[in] = b
				ENDIF
			NEXT
			IF in <> i THEN
				p = p + c
				m = in
				in = i
				s = s + 1
			ELSE
				f = FALSE
			ENDIF
		WEND
		RESULT = RESULT + q[i]
	NEXT
FEND


FUNCTION Q5F()
	DIM a[] = 1,2,3,4,5,6,7,8,9
	RESULT = Q5FSub(100, a[0], a, 1)
FEND
FUNCTION Q5FSub(sum, num, arr[], index)
	// 末端判定
	IFB index < LENGTH(arr) THEN
		// 足し算
		DIM i, resAdd = Q5FSub(sum - num, arr[index], arr, index + 1)
		FOR i = 0 TO LENGTH(resAdd) - 1
			resAdd[i] = num + "+" + resAdd[i]
		NEXT
		// 引き算
		DIM resSub = Q5FSub(sum - num, -arr[index], arr, index + 1)
		FOR i = 0 TO LENGTH(resSub) - 1
			resSub[i] = num + "" + resSub[i]
		NEXT
		// 結合
		DIM j = num * 10
		IF num >= 0 THEN j = j + arr[index] ELSE j = j - arr[index]
		DIM resMrg = Q5FSub(sum, j, arr, index + 1)

		// Merge
		RESULT = SPLIT(JOIN(resAdd) + " " + JOIN(resSub) + " " + JOIN(resMrg), , TRUE)
	ELSE
		IFB num = sum THEN
			RESULT = SAFEARRAY(0, 0)
			RESULT[0] = sum
		ELSE
			RESULT = SAFEARRAY(0, -1)
		ENDIF
	ENDIF
FEND

問4解説

総当たりに比べるとどうしてもコードが長くなります。
基本思想は、

  • 1桁目が最大のものを前に集める
  • 1桁目が最大のものが一つなら、それは確定して次を探す
  • 1桁目が最大のものが複数なら、1桁目を待避して2桁目が最大のものを集める
    • この時、桁数が足りない場合、待避した文字を補完して比較対象を取り出す
    • ただし、もし全てで補完した場合は、全て同じ数字ということなので、それは確定して次を探す
  • 2桁目が最大のものが一つなら、それは確定して次を探す
  • 2桁目が最大のものが複数なら、2桁目も待避して3桁目、、、と繰り返す

そんな感じです。
総当たり版は、数値として大小比較をしていますが、こちらは文字としてしか扱っていないので、桁数制限はありません。

問5解説

この問題、実は素晴らしいですね。
総当たりでEVALするという野蛮行為がいらないとは。
解答例（英語）の解説を読んだ方が良いです。
この解説以上のことは説明できませんし、その解説通りに組んでみました。


これFizzBuzzとあわせて覚えておきたい。
アルゴリズム的力量を測りたくなったら、

  1. まずはFizzBuzz
  2. 次に問5。EVAL的なものを使ったなら、使わない方法も考えてみて、と誘導
  3. 最後に問4

かな。


問5の誘導は、

  • 関数をf、数列を1...9と表現したとすると、求める関数は、f(1...9)=100だね。
  • 組み合わせるのは、「+」と「-」と「数値結合」
  • 「+」を考えると、1+f(2...9)=100。すなわち、f(2...9)=99
  • 「-」は、1+f(-2,3...9)=100。すなわち、f(-2,3...9)=99
  • 「数値結合」は、f(12,3...9)=100

となるようなfということ。
もう一歩踏み込むと

  • f(2...9)=99に対して「+」は、2+f(3...9)=99。f(3...9)=97
  • f(2...9)=99に対して「-」は、2+f(-3,4...9)=99。f(-3,4...9)=97
  • f(2...9)=99に対して「数値結合」は、f(23,4...9)=99

こんな感じでfの中身がどんどん減っていく。
最終的に、fに渡す数字が一つで求める値と同じであれば、求めるパターン、ということ。
操作は「+」「-」「数値結合」だけなので、f(9)=9といった同じ値でないと、生成できませんから。