第3回はAOJにジャッジがないので少し飛びまして「When Can We Meet?」を解説したいと思います。いつものように参考ページは 「ACM/ICPC国内予選突破の手引き」 「AOJの問題ページ」 になります。 さてこの問題はどういう問題かといいますと、 ある会議を行うために複数人の人が集まれるもっともよい日を調整する 会議の構成メンバー数Nと必要最低出席者数Qが与えられる 会議は今日から100日後までに行われる とい ...
前回に引き続きACM/ICPC国内予選突破ページに紹介されている過去問を全力で解説します。参考ページは http://www.deqnotes.net/acmicpc/ になります。今回は第2回目の「Ohgas’ Fortune」という問題。僕はAOJでやっているのでAOJのリンクを貼っておきます。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1135 この問題は利息の計算をシミュレーションする問題。注意するべきと思われるポイントは次の2つ。 問題文だと若干分かりづらいが、単利と複利が途中で入れ替わることはなく、どちら ...
どうもtatsyです。 GCJのQualification Roundが2週間後に迫ったということで、 http://www.deqnotes.net/acmicpc/ のページに書かれているACM/ICPC国内予選突破の手引きにある問題を僕なりの全力で解説してみたいと思います。 第1回の今回は「Hanafuda Shuffle」という問題です。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1129 この問題は特定枚数与えられている数字が書かれたカードをシャッフルしたときに一番上のカードが何かを出力するプログラムを書く、と ...
続いてはE問題です。 この問題はなかなかの曲者で、一見「なぁんだ、どうせ二分探索じゃん」と思うのですが、実はそれではうまくいきません。このような議席の割り振り問題ではアラバマのパラドックスという矛盾が起こることが知られてるらしいです。アラバマのパラドックスとは、得票数が変わらなければ総議席数が増えたときに獲得議席数はどの政党も増えるはずという予想に反して、獲得議席が減ることがあるというパラドックスで ...
さて次は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ケタずつ配列に入れて、西暦は西暦、月日は月日でソートす ...
