さて次はD問題です。 これは簡単な数学的知識があればなんとなく方針は立つと思います。一般にある図形を拡大・縮小、回転、平行移動だけで写すような変換は、 $$ \begin{bmatrix} a & b \\ c & d \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} + \begin{bmatrix} tx \\ ty \end{bmatrix} = \begin{bmatrix} x’ \\ y' \end{bmatrix} $$ みたいな形の連立方程式でかけます。拡大・縮小の比率は問題文から0.5であることが分かっているので、適当な方法で回転角度と平行移動距離を求めれば問題は解けそうです。ここで注意したい（僕が間違えた）と ...

さて続いてはC問題です。これは僕は当日は解けなかった。 この問題の難しいところは、N、Mともに100000なので、まともに隣接行列を持ったのではメモリが全然足りないというところ。まぁ、ここまでは少し考えればわかります。 そこで隣接が途切れているところだけをsetなりmapなりで持つことを考えるわけですが、今度はデータが増えてくると隣接頂点の探索に時間がかかりすぎてTLEになってしまいます。 最大のポイン ...

先日開催されたUTPC2012 (東京大学プログラミングコンテスト)のB問題の答えです。 解説をはじめたはいいが全部はたぶんできないし、いったいどこまで続くか・・・ http://utpc2012.contest.atcoder.jp/tasks/utpc2012_02 気を取り直して解説していくと、この問題はある文字の並びが、実は小説の8つの章であるのだけど、章が進むことに使える文字が減っていくので、小説を見てどういう順序で使える文字が減っていったかを答えよ、というものです。 実はこの問題は最後の8文字だ ...

ブログ開設記念に先日行われたUTPC2012 (東京大学プログラミングコンテスト)の問題を解説してみたいとおもいます。まずはA問題から。 与えられた年月日の西暦4ケタと月日の4ケタを並び替えて一致させられるかどうかを答える問題。 http://utpc2012.contest.atcoder.jp/tasks/utpc2012_01 基本的なアイディアはとても単純で 適当にscanfなりScannerなりを使って西暦4ケタと月日の4ケタを取得 それぞれを1ケタずつ配列に入れて、西暦は西暦、月日は月日でソートす ...