http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1314 問題 matlabの演算を実装しろ。 解法 やるだけ。indexed-primaryとtransposed-primaryはprimaryの直後にwhileループで実装する。スカラーも行列型で実装すると楽。

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=521&page=show_problem&problem=3735 問題 二部探索木がdfs順序で与えられる。その二部探索木をdfsで戻る時順に値を出力せよ。 ノード数 ノードの値 解法 dfs順序か…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=521&page=show_problem&problem=3740 問題 20*20の盤面に最大5個の長方形の大陸がある。大陸の大きさの合計は25である。大陸を動かして正方形を作りたいが最小何回…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=521&page=show_problem&problem=3737 問題 t以下の素数しか無いと考えた時にn桁の双子素数となる物の小さい方を答えよ。 3500 t 解法 tが小さいのでn桁目の最初の1…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=521&page=show_problem&problem=3736 問題 変数がn個、集合がm個ある。各集合Siのサイズは2または3である。変数に0または1を割り当てる時、全ての集合に0と1の両方…

250 素数の問題 素数じゃなかったら1回で終了。素数だったら1引けばいいだけ。 素数判定するだけじゃん…。ミラーラビンをコピペする。 おっと3の場合は答えが3になるな。 とりあえず書いた。submit。 1000 どうせ1000か500のどちらかしか解けないんで両方開…

codeforces見たら昼間からあったので参加してみた。 A問題 問題が読めない。 なんかおかしいと思ったらstatuesをstatusと読んでた。 やるだけ。submit。pretest WA。 移動しない場合を忘れた。submit。pretest AC。 C問題 こっちの方が簡単そうなんで手をつ…

本番 いもすさんがテンプレ打ち込んでいる間にAとBを読む。Aが先に読めて少しめんどいやるだけ問題だったんでいる君にやってもらう。その間にBが読めてBの方が簡単だったのでBに移行して書く。AC。 Cは計算量が分かんないけど探索で解けそうだったが、Dが拡…

前日に国際会議用のスライドを作ってて寝ずに参戦。いる君もほとんど寝てなかったらしい。 始まるまで なんかPC^2の調子がおかしいらしくて開始時間がずるずる伸びる。しまいにはatcoderですることに。その間はだべったり、自己紹介したりで時間をつぶした。…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=22&page=show_problem&problem=2000 問題 遺伝子がn個あり、それぞれの長さはliである。共通部分の長さの最大値を答えよ。 li 1 解法 間に0,1,2,...と挟んで各文字…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=285&page=show_problem&problem=2036 問題 モーションセンサーがk個ある。モーションセンサーはマンハッタン距離でdの位置まで有効である。このdは全てのセンサーで…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=285&page=show_problem&problem=2040 問題 無向中国人郵便配達問題を解け。 2 1 解法 一般の最小重み完全マッチング。のはずだけどなぜか2部グラフの最小重み完全マ…

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=285&page=show_problem&problem=2042 問題 人を2つのグループに分けたい。人同士の間には仲の良さがあり、その人の幸福度は同じグループに入っている人の中の良さの…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3552 問題 半径Rの円盤に半径rのドリルでn個の穴を開ける。重心を求めよ。 0 解法 穴がかぶることが無ければ普通に重心の公式で求めれば良い。穴がかぶってしまうので穴の形を考えて厳密に面…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3559 問題 矩形の毒沼がn個ある所でスタートからゴールまで行きたい。毒沼に入らず(境界含む)にゴールまで行くには最低何回曲がらないといけないか答えよ。 0 座標 解法 座標圧縮してダイクス…

問題 B進数を16segで表示する。180度回転して一致するK番目の数値を答えよ。 1 1 解法 反転して一致するものが0のみでK!=1のときは解が無い。他の場合は適当に反転して一致しない物が存在しない数をスキップしながら1ずつ足して順番に見つけていく。

問題 数列がN個ある。また数列に関してという制約がM個ある。この制約をすべて満たす数列は存在するか？存在する場合は辞書順最小の数列を求めよ。 N M 0 解法 強連結成分分解しグラフを縮約する。制約を満たすためには同じ強連結成分に含まれるもの同士の間…

問題 長さNの数列Aがある。Aのsubsequenceで単調増加でも単調減少でもない物の数は何個？ 1 解法 O(n^2)のDPをするだけ。無駄にTLEがきつい。

問題 のサイズを求めよ。 1 1 解法 やるだけ。

問題 andoroidとかのロックで押した順番が与えられる。同じ番号を押していて、線の形が同じになる押し方の数を答えよ。 解法 やるだけ。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3555 問題 h*wの盤面のアイスクライマーで一番上にたどり着くまでの最小の時間を求めたい。ルールは以下のとおり。 左右に進むのにt1かかる 敵がいる場合は無理 進んだ先に足場がない場合も無…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3558 問題 略 解法 答えは[tex:\sum_{a=1}^{n-1}\sum_{x=1}^{{\rm floor}*1ので間に合う。 *1:n-1)/a)}(n-ax)]となる。高速化するためにまず内側のsumを等差数列の和の公式で展開する。外側の…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3557 問題 略。 解法 答えは(n - m + 1)Cmになる。考え方としてはn個の中からm個を選ぶが、連続した物は取らないように(m-1)を引いておく感じ。 分母と分子の両方にpの倍数が入っていることが…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3556 問題 略。 解法 答えは(2^m-1)^nになる。考え方としては1が含まれる集合、1は含まないが2が含まれる集合、…とやっていけば良い。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3554 問題 部品の工作機械が3台あり、作りたい部品がn個ある。それぞれの部品は各々の工作機械で作るのに必要な時間が分かっている。3台の工作機械を同時に動かし始め、途中で全く止めずに作…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3551 問題 n-1人の普通の人と1人の吸血鬼がいる。一日ごとにある二人が出会ってその二人が吸血鬼と普通の人であった場合、その普通の人は確率pで吸血鬼になる。全員が吸血鬼になるまでの日に…

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3549 問題 略 解法 答えが大きくなるのは少ないのでmod10^xで愚直に計算。long longでは収まらない奴が稀にあるっぽいんでそこだけは多倍長で計算した。(m=64,n=781251でのみ答えが10になる。…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2289 問題 略 解法 解説通りにてきとうに多めに候補点を取れば良い。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2287 問題 略 解法 同じ高さの水槽で連結成分を作って有向グラフを作る。あとは各クエリに対して、その時間まで高い水槽からいっきに水を流す。

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=364&page=show_problem&problem=2507 問題 n個の電球がある。集合Siのon/offを切り替えるという操作をm回行い最初のv個だけがついてる状態にしたい。ただし、Si=Sj…