Processing math: 100%

AtCoder Regular Contest 153 B,C,D,E問題メモ

B - Grid Rotations

問題

  • H×W のグリッドにそれぞれ文字 Ci,j が書かれている
  • Q 回、以下の操作を行う
    • ai,bi が与えられる
    • グリッドを、ai 行目と ai+1 行目の間の線、bi 列目と bi+1 列目の間の線で十字に分割する
    • 分割された4つの長方形領域をそれぞれ180度回転する
  • 最終的なグリッドに書かれた文字を出力せよ
  • HW5×105
  • 1Q2×105

解法

タテヨコは独立に考えていい。
最初の i 行目が最終的に ri 行目、j 列目が cj 列目に移るなら、答えの (ri,cj) のマスにあるのは Ci,j である。

なので、1次元のクエリ操作を2回考えればよい。
縦方向(H 行)の操作を考えるとする。

愚直に考えると区間反転をいっぱいしなきゃいけなくて、そんなこと短時間でできるの? となる。
だが、今回は「2つに区切った区間をそれぞれまるっと反転」と決まっているので、実験してみると良い性質がすぐ見えてくる。

最初   1 2 3 4 5 6 7
      |-------|-----|    a=4
1回目  4 3 2 1 7 6 5
      |---|---------|    a=2
2回目  3 4 5 6 7 1 2
      |-----------|-|    a=6
3回目  1 7 6 5 4 3 2
      |-------|-----|    a=4
4回目  5 6 7 1 2 3 4

結局、1回の操作では 1,2,...,N の並びが逆順+転回を起こす。

特に2回の操作をまとめると、a1a2 の順で操作が発生すると (a1a2)modH だけ転回する。

よって、2個ずつ、いくつ転回したかを追っていって、Q が奇数なら最後の操作だけ愚直にやればよい。

Python3

C - ± Increasing Sequence

問題

  • 1 または 1 からなる数列 A=(A1,...,AN) が与えられる
  • 以下の条件を全て満たす数列 x=(x1,...,xN) を構築できるか判定し、可能なら一例を挙げよ
    • |xi|1012
    • 狭義単調増加、つまり xi<xi+1
    • Ai×xii=1N にわたる総和が 0
  • 1N2×105

解法

符号が Ai によって反転されうるため、Aixi の正負が入り交じる。

総和を特定の1つとかある範囲で調整する、ということを考える際、 狭義単調増加は置ける値の範囲が i ごとに変わるため扱いにくくて、できれば広義単調増加で考えたい。

最初に x=(1,2,3,...,N) と仮決めして、そこからの差分 y を考えると、y は広義単調増加であれば良くなる。

よって、x をそのようにした際の Aixi の総和を S とする。

A    -1  1 -1 -1  1 -1
x'    1  2  3  4  5  6
----------------------
     -1  2 -3 -4  5 -6  →  S = -7

ここで、たとえば S が負で、A1=1 だったとき、y1 は好きなだけ減らせるので、逆に総和は S から好きなだけ増やせることになる。(1012 という制約はあるが、一端無視して)

A    -1  1 -1 -1  1 -1
----------------------
x'    1  2  3  4  5  6
y    -7  0  0  0  0  0

x    -6  2  3  4  5  6
----------------------
      6  2 -3 -4  5 -6  →  S = 0

また、同様に S が負で、AN=1 だったとき、yN は好きなだけ増やせるので、同様に S から好きに増やせる。

S が正の時は逆に、A1=1 または AN=1 なら総和を好きに減らせる。

じゃあ、そうでない時は?
y には、先頭からある範囲までに一定値を減じる、または末尾からある範囲に一定値を加えてもよい。

たとえば S が負(k)なら、y1yj に一斉に一定値を減じたとき総和が k 増加してくれればよいので、A1Aj の総和が負(特に微調整を考えると 1)ならよいことになる。

よって、Ai の先頭or末尾からの累積和を取っていって、

  • S が負なら
    • ①先頭からの累積和で、総和が 1 になるところ
    • ②末尾からの累積和で、総和が +1 になるところ
    • いずれかを見つけ、その範囲の y に①なら S を加算、②なら S を減算
  • S が正なら
    • ③先頭からの累積和で、総和が +1 になるところ
    • ④末尾からの累積和で、総和が 1 になるところ
    • いずれかを見つけ、その範囲の y に①なら S を減算、②なら S を加算

すれば、調整が可能となる。
(最初に述べた、先頭・末尾の1項だけで調整する操作も、この処理にまとめられる)

S0 で、そのような箇所が全く登場しないとき(-1と+1が、良い括弧列となっているとき)は、調整ができず不可能。

で、最後にこれが 1012 を超えないかだが、

  • S は、最大 N(N+1)22×1010 で、±Syi の範囲
  • x の最大値は 2×105
  • よって x=x+y の絶対値は 1011 を超えない

ので大丈夫と分かる。

Python3

D - Sum of Sum of Digits

問題

  • N 個の整数 A1,...,AN がある
  • f(x) を、正整数 x の10進表記での各桁の和とする(f(153)=1+5+3=9
  • 非負整数 x を決めたとき、Ni=1(f(Ai+x)) としてあり得る最小値を求めよ

A = ( 4 13  8  6)

x=7 とすると、

f( 4+7) = f(11) = 2
f(13+7) = f(20) = 2
f( 8+7) = f(15) = 6
f( 6+7) = f(13) = 4
                 ~~~ 総和は 14

解法

考察は下の桁から考えた方がわかりやすいように思うが、実装は上の桁から行う。ややこしい。

数列 X に対し、問題で求められる値 (適切な x を加算したときの Ni=1(f(Xi+x)) の最小値)を、F(X) とする。

すると、下の桁から再帰的に求めるようなアルゴリズムができる。(実際はこのままではTLEだが)

A = (141, 926, 358, 793) とする。
下1桁を考えると、(1,6,8,3) である。

x=0 → 1 + 6 + 8 + 3 + F((14,92,35,79))

x=2 → 3 + 8 + 0 + 5 + F((14,92,36,79))  358 が 360 に繰り上がっている
               ~                ~~
x=4 → 5 + 0 + 2 + 7 + F((14,93,36,79))
           ~                 ~~
x=7 → 8 + 3 + 5 + 0 + F((14,93,36,80))
                   ~               ~~
x=9 → 0 + 5 + 7 + 2 + F((15,93,36,80))
       ~                  ~~

答えは、この5つの場合の中の最小値

x の加算による繰り上がりを反映した上で、各 Ai を10で切り捨て除算したような A に対する F(A) を求める問題に再帰的に縮小できる。

制約的に9回再帰すれば十分であり、その頃には A の値は0か1になっている。
そしたらもう x を足して繰り上げる意味は無いので、F(A)=sum(A) となる。

F() の引数となりうる状態数は、各桁につき「N 個のうちどこかまでが繰り上がった状態」なので、N+1 通り。
Ai の桁数の最大値を K(9) とすると、全部で O(KN) となる。
実行制限時間に間に合わせるには、各 F() を求めるのに O(1)O(K) 程度までなら大丈夫。

しかし、下の桁からの再帰を素直に実装すると、1つの状態の計算に O(N) かかってしまう。これはダメ。

上の例において、例えば F((14,92,35,79)) の結果から F((14,92,36,79)),F((14,93,36,79)),... が順次差分計算できることを利用すれば、ならして O(1) で求められる。

そのような実装は、下の桁からの再帰ではやりにくいので、上の桁から埋めていく。

自分のDPの定義は、あまり説明しやすい実装では無い(もっとわかりやすいDP定義による実装がありそう)が、、、

  • DP[i,j]= 以下のように作られた Bi に対し、Bi[j] の下1桁がちょうど繰り上がる場合の F(Bi)
    • AAk%10i を基準に降順ソートする
    • Bi[k]=Ak/10i1(切り捨て除算)とする
  • j=0 の場合は、1つも繰り上がりが発生しない場合の F(Bi)
例
A = (141, 926, 358, 793)

DP[2,3]:
  100で割ったあまりの 41,26,58,93 を基準に降順ソート → (793, 358, 141, 926)
  その後、10で割る → B2 = (79, 35, 14, 92)
  
  このB2に対し、B2[3]=14 がちょうど繰り上がる(足す数 $x$ の下1桁が6である)前提での F(B2)

同様に B3=(9,7,3,1) である。
DP[3,:] から DP[2,:] を求めるにあたり、B2B3 の間で元となった Ai の位置関係 P2 を求めておく。

 i     1       2       3       4
B3   9(926)  7(793)  3(358)  1(141)     ... B3としての値(元のAiの値)

B2  79(793) 35(358) 14(141) 92(926)     ... B2としての値(元のAiの値)
P2     2       3       4       1        ... B2における、元のAiのB3における位置

DP[3,:]P2[:] から DP[2,:] を求める。

B2  j  xの下1桁  x加算後のB2の下1桁の和  上の桁
↓  0      0           20       +      F(7,3,1,9)  = DP[2,0]
79  1      1           14       +      F(8,3,1,9)  = DP[2,1]
35  2      5           20       +      F(8,4,1,9)  = DP[2,2]
14  3      6           14       +      F(8,4,2,9)  = DP[2,3]
92  4      8           12       +      F(8,4,2,10) = DP[2,4]

B3  j  xの下1桁  x加算後のB3の下1桁の和  上の桁
↓  0      0           20       +      F(0,0,0,0)  = 20 = DP[3,0]
 9  1      1           14       +      F(1,0,0,0)  = 15 = DP[3,1]
 7  2      3           12       +      F(1,1,0,0)  = 14 = DP[3,2]
 3  3      7           18       +      F(1,1,1,0)  = 21 = DP[3,3]
 1  4      9           16       +      F(1,1,1,1)  = 20 = DP[3,4]

x 加算後の B2 の下1桁の和」は、、、

  • まず素の状態で B2 の下1桁の総和を取る(9+5+4+2=20)。これが j=0 のとき。
  • j=1 のとき、x の下1桁は1のため、N 個の数に1が足され、うち j=1 個が繰り上がる(桁和が10減る)
    • j=0 の時の差分から、20+1N110=14
  • j=2 のとき、x の下1桁は5のため、N 個の数に5が足され、うち j=2 個が繰り上がる
    • j=0 の時の差分から、20+5N210=20
  • j=3 のとき、x の下1桁は6のため、N 個の数に6が足され、うち j=3 個が繰り上がる
    • j=0 の時の差分から、20+6N310=14

、、、としていくと、O(N) で全体を求められる。

DP[3,:]P2[:] から DP[2,:] を求める際も、似たような差分計算ができる。

  • まず、DP[2,0] を求める際に必要となる F(7,3,1,9)=min(DP[3,:])=14 である。
  • DP[2,1] を求める際に必要となる F(8,3,1,9) は、、、
    • B3 における P2[1]=2 番目の項が1増える (9,7,3,1) → (9,8,3,1)
    • 差分を考えると、
      • 1つの項が1増えたため、DP[3,:] から各項が 1 ずつ増える
      • B3 の値が1増えた DP[3,2] だけは、N 減る
        • x 加算後の下1桁の和の更新方法を考えれば、こうなることがわかる
      • これによって、初期状態より DP[3,2] が小さくなったら、最適な min(DP[3,:]) が更新される
  • DP[2,2] を求める際に必要となる F(8,4,1,9) は、、、
    • B3 における P2[2]=3 番目の項が1増える (9,8,3,1) → (9,8,4,1)
    • 差分を考えると、
      • 初期から2つの項が1増えたため、DP[3,:] にとっては各項が 1 ずつ増える
      • B3 の値が1増えた DP[3,3] だけは、N 減る
      • これによって、b+2 より DP[3,3] が小さくなったら、最適な min(DP[3,:]) が更新される

…としていくと、こちらもならして O(N)DP[2,:] を埋められる。

例:
DP[2,0]で必要な F(7,3,1,9):

  DP[3,:] =  (20, 15, 14, 21, 20)   →   F(7,3,1,9) = min(DP[3,:]) = 14

DP[2,1]で必要な F(8,3,1,9):

  ・DP[3,:] の各項に1足す
  ・繰り上がった 7 (元のAi=793)がB3で位置するindex = 2 なので、DP[3,2] からN引く
  
  DP'[3,:]=  (21, 16, 11, 22, 21)   →   F(8,3,1,9) = min(DP'[3,:]) = 11

DP[2,2]で必要な F(8,4,1,9):

  ・DP[3,:] の各項にさらに1足す
  ・繰り上がった 3 (元のAi=358)がB3で位置するindex = 3 なので、DP[3,3] からN引く
  
  DP''[3,:]= (22, 17, 12, 19, 22)   →   F(8,4,1,9) = min(DP''[3,:]) = 12

Python3

E - Deque Minimization

問題

  • '1'~'9'からなる文字列 X に対し、以下を考える
    • X に以下の操作を行い、文字列 S を得る
      • S を空文字列で初期化する
      • X1,X2,...,XN の順に、S の先頭または末尾に挿入する(XiXi 文字目)
    • この操作により得ることができる S のうち、整数としてみたときに最小のものを f(X) とする
  • '1'~'9'からなる文字列 Y が与えられるので、f(X)=Y となるような X の個数を mod998244353 で求めよ
  • 1|Y|200000

解法

f(X) を構成するための操作

X1 はまぁそのまま挿入するとして、最小にするなら下記のようにすればよい。

  • Xii2)を S に挿入するとき、その時点の S の先頭を S1 として、
    • S1Xi なら、Xi を先頭に挿入
    • S1<Xi なら、Xi を末尾に挿入

S1=Xi の場合も本当に先頭でいいのか? と思うが、上記の方針をとる以上、

  • 暫定の S が全て同じ文字なら、先頭と末尾どちらに挿入しても変わらない
    • 重複を除くため、先頭に挿入することで統一する
  • S が全て同じでないなら、どこかではじめて S1 と異なる文字 c が出てくる
    • この c は、必ず S1 より大きい
      • cS1 より小さくて、S1 より後に挿入されたなら、先頭に来ているはず
      • cS1 より小さくて、S1 より前に挿入されたなら、S1 の方が後に来ているはず
    • よって Xi は先頭に挿入し、S1 が続く長さを長くした方が良い

また、S=11233 を作れるけど、途中段階では敢えて S=32131 みたいにすることで、最終的には 11233 としたときより S を小さくできる、みたいなことは起こらない。

11233 にしようと 32131 にしようと、これ以降、何をどのような順で前・後ろに挿入可能かは全く同条件であり、

(同じ並び)11233(同じ並び)
(同じ並び)32131(同じ並び)

なら確実に前者の方が小さい。その時々で最小となるように前・後ろのどちらに挿入するかを決めていってよい。

よって、X が決まっているなら、そこから f(X) を作る操作は意外と単純である。

先頭を固定した場合の数

先頭要素 X1Y の何文字目にあたるか(Y がどこから生成されていったか)を固定する。

Yi から生成されたと決め打つと、そこから後は左右に広がっていったことになるので、

  • Yi1Yi2...Y2Y1
  • Yi+1Yi+2...YN

X2 以降の要素の並び順は、上記のような2つの列をマージしたものに限定される。
(マージ:ここでは、列の中での順序は保たれるように、2つを1つにまとめる操作を指す)

その上で、いくつかの制約がある。

先頭から昇順が続く範囲しか X1 にできない

以下のような時に、3を最初に置くことはできない。

Y:  1  2  4  5  [3]  4  6  ...

3を最初に置いた後に5を挿入したとすると、その5をわざわざ前に持ってこないと この Y は作れないが、f(X) を作る操作に違反する。

上記の例なら、先頭の4つ 1,2,4,5 が、X1 となり得る範囲となる。

置く順序の制約

もし、長さ nm の2列を単純にマージするなら、 場合の数は n+mCn で求められるが、そう単純でもない。

前に置かれるべき数が、誤って後に置かれることは基本的にないが、
後に置かれるべき数は、それ以前に自身より小さい値が前に置かれていないと、前に置かれてしまう。
そうなるとより小さい f(X) が作れるような、数え上げの対象ではない X となってしまう。

以下の2通りの場合に注意する。(①は、ちゃんと考えれば②にまとめられるかもしれないが、分けて考えた方がわかりやすい)

  • ①同じ要素が連続している箇所を先頭とする場合
  • ②後に置かれるべき数の列の中で、これまでより小さい値が出てくる場合

今、i=6,X1=5 を先頭に持ってくるとき、どうなるか考える。

i:  1  2  3  4  5  6  7  8  9 10 11
Y:  1  2  2  3  5 [5] 5  3  4  4  2

X2 以降は、このような2列のマージとなる。

  • 前に置かれる 5→3→2→2→1
  • 後に置かれる 5→3→4→4→2

次に来るのはいずれでも 5 だが、5 が来ると、f(X) の構築方法から考えるとこれは前に置かれることになる。
よって、X2 には、前に置かれる方の5しか来てはいけないことになる。

次も同様で、(最終的に i=5,6 に収まるべき)'55' がある状態に(最終的に i=7 に来るべき)'5'が来たら、 これは前の方に置かれてしまうのでダメ。ここも前に置かれる方の3しか来れない。

暫定S:   3  5  5

残り列
前に置かれる  2→2→1
後に置かれる  5→3→4→4→2

S の先頭が3になってはじめて、これ以降の5は後に置くべきとなったので、 X4 には前に置かれる'2'も後に置かれるべき'5'も採用できる。

①の制約は、「同じ要素が連続している箇所を先頭とする場合は、その中の末尾以外は、自身より前の、より小さい値が1個置かれるまでは、前にしか置けない」という制約となる。

これにより、たとえば 1233[355555]566… という並びでは、 「ある数字の連続箇所の末尾 (3)」と「次の数字の連続箇所の末尾以外 (55555)」において、 それを先頭とした場合に実質的に考慮すべき「前に置かれるべき数の列」が同一となる。 (3→3→2→1)

また特に、Y の先頭要素が連続していた場合は、その中の末尾のみ、先頭とすることができる。

Y:  1111112233...
    ~~~~~          先頭にはできない

例に戻って、続けて 5 が置かれた場合の続きを考える。

暫定S:   3  5  5  5

残り列
前に置かれる  2→2→1
後に置かれる  3→4→4→2

ここでもまた、次に後に置かれるべき'3'が来てしまうと前に置かれてしまうので、'2'が先に置かれる必要がある。

同様に、(しばらく進めて)後に置かれるべき列の最後の'2'も、前に置かれるべき'1'の後に置かれる必要がある。

これが②の制約で、「後に置かれるべき値が置かれるときには、先に、より小さい値が前に置かれていないといけない」となる。
ただし、いくつかの要所さえクリアすれば、要所以外は必然的に条件を満たすことが多い。

たとえば後に置かれるべき2つの'4'は、その前に既に'3'が置かれているので、 先頭は2以下となっていることがわかっているため、勝手に条件はクリアしている。

要所となり得るのは、「後に置かれるべき列」の中でも 「これまでに出てきたどの値より小さい値がはじめて出てきた時(狭義単調減少)」なので、 特に値の範囲が1~9である本問題においては、たかだか7個である。

制約の列挙方法としては、例えば、以下のようにすればよい。
Y の中で昇順が保たれる範囲を YAsc、それ以降を YNotAsc とする。

YNotAsc の先頭から累積minを取りながら、累積minを更新する要素 Yj を探す。 Yj に対し、Yj1 以下の要素が YAsc 中で最後に出てくるのが Yi だったとすると、 「Yj が置かれる前に Yi が置かれなくてはいけない」という制約が見つけられる。
ただし、それより前に見つかった制約と Yi が同じであれば、無視してよい。

また、YNotAsc の中に Y1 より小さい値が出てきたら、 そいつを前に置かれることが阻止できないので、そのような Yf(X) となるような X は0個となる。
(これは最初に確認して例外処理してしまうのが、混乱しなくてよい)

先ほどからの例において、前後に置かれるべき列に②の制約を追加すると以下のようになる。

前に置かれる  2→2→1
             ↓      ↘
後に置かれる  3→4→4→2

具体的な数え上げ方法

先頭を固定して、マージするべき前後の列と制約も定まった。これをマージする方法の数を数え上げたい。

やりたいことはトポロジカルソートの数え上げではあるが、そんなの多項式時間では無理なので、 「ベースは2列のマージ」であることを利用することになる。

経路数え上げに言い換えるのがわかりやすい。

前\後  -   3   4   4   2
 -     1 |           |
 2                   |
 2                   |
 1

左上から右か下に進み、右下までの経路数が答えだが、「前の'2'に進む前に後の'3'に立ち入ってはいけない」「前の'1'に進む前に後の'2'に立ち入ってはいけない」という制約は、上記のような壁で表現できる。

愚直には1マスずつ埋めていくとできるが、N2×105 なので、O(N2) は無理。
しかもこれ、あくまで先頭を固定した場合なので、先頭毎にこれだけかかる。

複数の“ある要素を先頭とした場合の数”を、ある程度まとめて計算できれば嬉しい。

そこで、「どこを先頭にしたって、列の末尾の部分や、そこにかかる制約は同じになる」ことに着目して、逆から考える。

i:  1  2  3  4  5  6  7  8  9 10 11
Y:  1  2  2  3  5  5  5  3  4  4  2

i=6 を先頭とした場合にマージしたい列
  前:  2→2→1
      ↓      `---↓
  後:  5→3→4→4→2

i=3 を先頭とした場合にマージしたい列
  前:  2→1
           `----------------↓
  後:  3→5→5→5→3→4→4→2

それぞれ長さは違うが、末尾から見たときの並びと、制約の張られる位置は同じ

→逆からDPすれば、複数の場合を一度に考えられる

末尾からとした場合、各 Yi を先頭とした場合の答えがDP配列のどこに現れるかが異なってくる。
答えとなり得る箇所を全て合計すると、全体の答えとなる。

逆にした場合のDPと、各要素を先頭としたときにどこを拾うべきかを示したのが、以下となる。
制約の壁は横になる。

      i     11  10   9   8   7   6   5   4   3   2   1
i 前\後  -   2   4   4   3   5   5   5   3   2   2   1
0  -     1                                  (2)  (1)
1  1    ~~~
2  2                                    (2)
3  2    ~~~~~~~~~~~~~~~~    (5) (5) (3)
4  3                            
5  5
6  5                    (5)

ここまでの考察から、拾うべき位置は以下のようになることがわかる。

  • 基本的には、i を先頭とするなら、前の列は i1、後の列は i+1 から始まるので、その斜めのラインに乗っかる
  • ただし同じ要素が連続している場合、その中での末尾要素以外は、1つ前の値の高さに揃えられる

拾うべき位置の高さがある程度揃う、というのが重要で、 YAsc の中で同じ要素が連続している箇所の個数はたかだか9個なので、 9種類の高さの、連続する横範囲の値の合計がわかれば良いということになる。

また都合のいいことに、制約の壁が出現する位置も、性質上、同じ高さに来ることになる。

したがって、同じ要素が連続している箇所はイレギュラーのない綺麗な形となり、畳み込みでまとめて計算できる。

より具体的な方法を示すにあたり、後の列においてindexが逆順になっているのがやりにくいので、 j=N+1i として昇順に振り直す。
(このように、逆順のindexに変換する関数を f(i) とする)

     (i     11  10   9   8   7   6   5   4   3   2   1)
      j  0   1   2   3   4   5   6   7   8   9  10  11
i 前\後  -   2   4   4   3   5   5   5   3   2   2   1
0  -     1                                  (2)  (1)
1  1    ~~~
2  2                                    (2)
3  2    ~~~~~~~~~~~~~~~~    (5) (5) (3)
4  3                            
5  5
6  5                    (5)
  • 初期化
    • DP=[1,0,0,0,...]
    • l=0: 左からDPが切り詰められる(壁によって防がれる)長さ
  • YAsc で、出てくる種類数を Ki 種類目の要素が最後に出てくるindexを ai とする
    • 便宜的に a0=0,aK+1=|YAsc|+1 を追加する
    • 例) YAsc=1223555 なら、a=[0,1,3,4,7,8]
  • i=1,...,K の順に、
    • d=aiai11 …(次に求めるべき行と、DPが現在示す行の差分-1)
    • Q=[dCd,d+1Cd,d+2Cd,...]
      • Qk: 下段に d、右段に k だけ移動する経路数
    • DP[l:]Q を畳み込み、新たな DP[l:] とする
    • DP の必要な箇所を合計する
      • e=ai+1ai の時、f(i)ef(i)1 の範囲を合計
    • DP を切り詰める
      • 以降、もう答えとして計上した箇所は不要。DP=DP[:f(i)e]
      • Yai を置くまで Yj を置いてはいけない」制約が設定されていれば、l=f(j) とする

畳み込み、答えの範囲を合計する処理は、1回あたり O(NlogN)、 それがたかだか9回なので、十分高速となる。

Python3

programming_algorithm/contest_history/atcoder/2023/0114_arc153.txt · 最終更新: by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0