250 One-time pad？ああ使い捨てパッドのことね。 平文と暗号文の組合せで暗号を一つ作ってvalidか確かめるだけじゃね。 書いた。submit。 500 英文がちょっと分からん。 大小関係をてきとうに決めてindexの合計を最小にする問題か。 同じ文字はマージしたと…

lukcy number回。いつもと比べて問題文が読みやすい。 ところで7はともかくなんで4もluckyなんだろうか。 A問題 これって答えめちゃくちゃでかくならない？ 4の数、7の数だけ考えればいいから別にいいのか。 ある一定の数を超えると常に作れそう。どう作る？…

参加資格は無いんでコンテスト終了後に解かれてない問題を解いてみた。 問題 略 解法 直前の場所と行く場所が被ることを想定して状態を4倍+はまり状態を作成して状態遷移の行列を作成する。あとはその行列をt乗するだけ。

http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=328 東方回。なんとなく出てみた。 Aya 3クリークができないように辺を最大何本引けるか？ 4,5,6頂点くらいで試してみたけど、よう分からん 2部グラフで考えればいいんじゃね？ 証明し…

問題 略 解法 α世界になる→その数の約数の個数が奇数個→平方数。なんで平方数を順番に列挙するだけ。

問題 略 解法 ポリゴンが張る平面は平面の方程式によって表現でき、簡単に表にあるか裏にあるか判定できる。あとはメモ化再帰とかやればok。

けっこう知ってる人がいる。 250 時計の長針と短針の問題か。 めんどくさいんで2重ループ回してしまえ。 合わない…。問題文見たら開始位置は30度ごとって書いてあるじゃないか。 修正。modとり忘れてた。修正。一致したのでsubmit。 550 アイテム屋さんのル…

http://poj.org/problem?id=2546 問題 2円の共通部分の面積を求めよ。 解法 ライブラリを使って終了。 ライブラリは続きを読むに置いてみた。

http://poj.org/problem?id=2545 問題 素数p1,p2,p3から構成される数値の列でn番目の物を答えよ。 p1,p2,p3,n,答えは全て10^18未満 解法 10^18未満にそのような数値は64^3個も存在しないので、オーバーフローに注意しながら全て列挙すれば良い。

http://poj.org/problem?id=2543 問題 エクセルの表っぽいやつが与えられるのでA1の値を計算せよ。 解法 最初に入力を全部読んで、メモ+構文解析。 空行があり、N行分の入力が存在しない場合があるので注意。

http://poj.org/problem?id=2542 問題 トランプの6〜Aを使ってカードゲームを行う。まず先手がカードを1枚場に出す。以降次の操作を繰り返す。 後手はそのカードに勝つカードを1枚場に出す。その次に先手は場に出ているカードと同じランクのカードを出す。 …

http://poj.org/problem?id=2541 問題 魔法使いが天気予報を行う。a日からのt日間が最近t日と同じ天気の変動をしている場合、明日の天気はa+t日目の天気と一致する。そのような列が複数ある場合は最も最近のものを採用する。そのような列がない場合はt=13,12…

問題 略 解法 DPで解く。普通に考えるとだが、Mに関しての総和を持っておくとに落ちる。さらに途中ででかい数値を使うとどう頑張ってもSを超える場合があるので、その場合をスキップすることにより枝刈りが効いて間にあうようになる。 MLEも厳しいのでDPの配…

http://www.codeforces.com/blog/entry/2446 なんぞこれ。ディスガイアはやったことが無いんだけど。 A問題 元ネタがあるせいで問題文が長くなってる…。 転生するらしい。 やるだけっぽい。ただしdoubleは怖いので100倍してintにした方が良さそうだ。 書いた…

250 ループする区間の問題 てきとうに実装すればいいんじゃないの これって端はどうなってんの？よく見たら左端は入らずに右端が入るとか変なことになってるし…。 しかも実数だからbestとworstが一致するときだけコーナーケースになってる…。 実装に時間がか…

250 やるだけっぽい。 書いた。サブミット。ac。 簡単すぎて本当にdiv1か確認してしまった。 500 なんか去年の模擬地区予選に出てたような気が。 てきとうにダイクストラを書いて終了。 1000 グラフとツリーの問題。 とりあえずツリーのノードに番号はつける…

最近メインの練習場所がTopCoderのPractice Roomになっているので書くことにする。Easyを15分(200pts)、Mediumを30〜60分(200〜300pts)程度で解くのが目標。Hardは解いてる人が多そうなら時間をかけたり、解説見ながらやる感じで。 250 nナイトの問題。どっ…

KUPCのジャッジをやっていました。主に問題の作成とテストをしてました。てきとうに感想などを書きます。 大規模なコンテストの主催者側に回るのは初めてなので割と楽しめました。特に本番中は他の人の解答を見て遊んでた気がします。 コンテストの問題に無…