https://www.spoj.pl/problems/CARDSHUF/ 問題 [1,N]までの数列に対して、i番目の数値をj番目に移動するという操作をM回繰り返す。最終的にできた数列を元の数列に戻すのに何回操作を行わないといけないか答えよ。 1 解法 平衡二分木でO(logN)で操作を行い最…

http://www.spoj.pl/problems/BOXES/ 問題 n個の箱が円形にならんでいる。各箱にはki個のボールが入っている。ボールを箱から一つ取り出して隣の箱に入れる操作のみが行える。全ての箱に1個以下のボールが入っている状態にするためには何回操作を行わないと…

http://www.spoj.pl/problems/QTREE3/ 問題 頂点数nのツリーが与えられる。以下の2つのクエリを捌け。 頂点iの色を反転させる。(初期状態は白) 頂点1からvまでで黒い頂点で頂点1に最も近いものを答えよ。無い場合は-1。 n クエリの数 解法 ツリーのdfs順序(…

http://www.spoj.pl/problems/QTREE/ 問題 頂点数Nのツリーが与えら、次のようなクエリがq個与えられるので処理しろ。 i番目の辺の重みをtiに変更する。 頂点iと頂点jを結ぶパスの中で最大の重みを答える。 N qはたぶん数万 解法 ツリーを鎖に分解して考える…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4871 問題 高さの違う高層ビルをN個建てる。ただし、i 解法 DP[n][pos]を考える。DP[n][pos]はn番目までのビルを置いたときにhi

https://www.spoj.pl/problems/TOURS/ 問題 頂点数nの有向グラフが与えられる。このグラフを閉路に分割したいのだが、全ての頂点を使って、なおかつ各閉路の使用する頂点は重なってはいけない。そのような分割の仕方で最小のものを求めよ。 1 解法 各頂点を2…

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

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手以内で元に戻せない場合は-…

http://www.spoj.pl/problems/NGM2/ 問題 1〜Nまでの数字がある。1〜Nまでの数字でxの約数になっている物を取り除くという操作をk回行う。最後に残っている数字は何個かという問題。 N 解法 kが小さいので全ての組み合わせに対して包含原理を使って計算すれ…

http://www.spoj.pl/problems/SUMMUL/ 問題 nを二つ以上の足し算で表しその数字を掛け合わせる。そのような物を全て足すといくらになるかという問題。答えがでかくなるのでmod 1000000007を取る。1 解放 答えの数値+nを考える。 すると というような式になる…