http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2325 問題 図にあるようにフリップの操作とシフトの操作ができるトラックが存在する。黒のディスクと白のディスクを分離できるか？ 10 解法 よく見るとフリップの操作は1つ飛ばしのスワ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2324 問題 2つのDNAを与えるので類似度を求めよ。 1 解法 DP。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2323 問題 係数が0か1しかないd次関数f(x),g(x)が存在する。h(x)=f(x)g(x)としたときh(x)を求めよ。ただし、係数はmod2をとる。 d 解法 多項式ライブラリを使って普通に多項式のかけ算を…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2322 問題 木の棒がn本存在する。木には長さlと重さwが存在する。この木を整形する機械があるのだが、機械の準備をするために1分かかってしまう。しかし、直前に整形した木よりも長さも…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2321 問題 カレンダーを使って二人でゲームを行う。手番のプレイヤーは現在の日付を1日進めるか、もしくは次の月の同じ日付が存在すればその日に日にちを進めることができる。そうして交…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2928 問題 小文字からなる長さNの文字列Sがある。SからK個以下の文字を変更した回文文字列Pは何個存在するか。 1 0 解法 奇数の場合の中心を…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2925 問題 ある会社のネットワーク上にはコンピュータとサービスがN個あり、各サービスは全てのコンピュータで動いている。ハッカーがいてそ…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2923 問題 DAGがある。ノードが重複しないように取った2つのパスを考える。その2つのパスで使用したノードの合計の最大値を求めよ。ただし、…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2926 問題 仕事の行き帰りに音楽を聞くことにした。ミュージックプレイヤーにはシャッフルモードが付いていて、1回シャッフルすると全ての曲…

https://www.spoj.pl/problems/ODDDIV/ 問題 奇数kが与えられる。lowからhighの範囲で約数がちょうどk個ある数値の数を答えよ。 1 解法 前提として、約数の個数は奇数なので素因数分解したときに素数piは偶数個しかなく、素因数分解した際に大きな素数が残る…

後輩が試験のことを書いていたので書いてみる。向こうにはゲームのことしか書くつもりはないのでこっちで。 試験前日 TCO Round5の500で1行ミスをしてon siteを逃してやる気が無くなる。実質的には一日開いてるけど前日。 試験前 てきとうに出る所を予測して…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2203 問題 素数以外のある数値を素因数分解した結果の各桁の和と数値そのものの各桁の和が同じになる数値をスミス数と呼ぶことにする。nより大きい最小のスミス数を求めよ。 n 解法 スミ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2200 問題 朝S時以降に出発する電車を乗り継いで行って目的地まで行きたい。最も早く辿りつける時間と、その時間にたどり着くための最も遅い出発時刻を答えよ。 都市の数 列車の数 各列…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2201 問題 どの場所からnの長さの数値を取り出してきても全て違う数値になっている2^nの長さの円順列をウロボロス数と呼ぶことにする。最小のウロボロス数のk番目の位置の数値をは何か？…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2336 問題 1から20までの数字がある。各プレイヤーは自分の番で数値を一つ選び、その数値の倍数とその倍数にすでに消された数値を足した値になっている数値を消す。そして、数値を選べな…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2205 問題 エルデシュ数を求めよ。 解法 グラフを作って幅優先探索をする。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2184 問題 矩形がn個与えられる。それらの和集合をとった時の面積を求めよ。 1 解法 出現したx,yの座標で矩形を区切って調べた。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4370 問題 シーズンのレースの結果が与えられるのでソートして出力せよ。 解法 やるだけ。チーム名にはスペースが入ってることがあるので注意。あとサンプルアウトプットの名前と得点の…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4369 問題 Walsh行列が与えられる。大きさ2^NのWalsh行列の列Rの行SからEの合計値を求めよ。 0 0 0 E-S 解法 Walsh行列の(y,x)の値はy&xの立っているビットの数が偶数なら1、奇数なら-1…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4368 問題 ヨセフスの問題で最後に残る人を答えよ。 解法 ヨセフス数。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4367 問題 銀行の貸し借りのグラフが与えられる。それを簡約化するとグラフの辺の重みの合計はいくらになるか。 銀行の数 解法 max(0, 頂点から出ている値の合計 ー 入ってくる値の合計)…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4366 問題 有向グラフと壊れた車の場所が与えられる。壊れた車をトラックでガレージまで運びたい。最短経路の長さはいくらになるか。ただしトラックは最初ガレージに存在し、壊れた車は…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4365 問題 存在し得る得点の取った順序の数と得点の合計は同じか？ 解法 どちらか一方が1ならば同じ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4364 問題 中に数値の書かれたn列の三角形が与えられる。三角形の値とはその中に書かれている数値の和である。部分三角形の値で最大の値を求めよ。 n 解法 てきとうに列の和を保持してお…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4363 問題 #と*と数値からなるパターンが存在する。#は奇数個、*は偶数個の任意の数値とみなせる。 パターンと数値が与えられるので数値がパターンにマッチするか判定せよ。 パターンの…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4362 問題 7SEGの形でエンコードされた足し算が与えられるのでそれを計算せよ。 解法 やるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4361 問題 図のようなパズルがあり、1手ごとにA,B,C,Dのいずれかを90度回転させることが出来る。 ある局面を与えるのでその手が何手で初期状態に戻せるか？y手以内で元に戻せない場合は-…

ICPC国内予選に参加してきました。 結果は残り1分くらいでE問題を解いて7位、学内1位となりました。残り1分でE問題が解けた時は(学内1位ってことは気づいてなかったけど)我を忘れて喜びました。本番の感想としてはC問題まではさくさく進みましたが、それ以降…

32bit版Windowsの一つのプロセスは2GBまでしかメモリを確保できないという制限が厳しくてUbuntu10.04の64bit版を使うことにした。32bit版のことしか考えてないのか、ちょっとめんどかったけど動いたのでメモとしてどうやれば動くのかを書いておく。64bitに対…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1023&lang=jp 問題 略 解法 平面走査を行う。 各点のイベントとしてx-2*rの位置にinイベント、x+2*rの位置にoutイベントを挿入してx座標でソートしておく。 イベントが起こるとy座標で…