uva.es で 3 問解いた

ここ数日で 3 問解きました。

• 108 Maximum Sum
• 350 Pseudo-Random Numbers
• 377 Cowculations

Maximum Sum は、 N * N の行列が与えられたとき、要素の和が最大になる部分矩形を探し、その和を出力するもの。普通に、というか何も考えずに左上の座標と右下の座標を for で回してその中の総和を…と書いてみたらアウト。これじゃ 6 重ループだし…。行ごとに和を計算（m[i][j] から右に k 個分和を取ったものを r[i][j][k] 等として保存）しておいて、列方向に順に足して調べていく方法をネットで見つけたのでそれで AC でした。

Pseudo-Random Numbers は擬似乱数の周期を求めればいいのかな? 擬似乱数の列が与えられた種（L）から始まらないかもしれない点を考える必要があります。得た数字をその順番とともに保持しておけば、すぐ分かる。

Cowculations は単に計算をすればいいみたい。 4 種類の数字（V, U, C, D）で構成される数? に対して繰り上がりのある和、左右シフトなどの演算を行います。最後に与えられる数と計算結果が合致するか否かを最終的に出力すれば完了。数は最大 8 桁で演算は 3 回だけという制限なのでさくっと。本質でないところで色々手間取りましたが。

これでやっと 20 問。動的計画法（DP: Dynamic Programming）がまだ習得出来ないです。