問題概要 01からなる長さ100以下の文字列が与えられる。0or1が7つ以上連続する箇所があるかどうかを判定する問題。

問題概要 文字列が二つ与えられるので大文字小文字を無視してstrcmpした結果を出力する問題。

問題概要 長さL(最長共通部分列を求める問題。 解法 片方の数列に現れる順序で数字に番号を振りなおして、もう片方の数列で最長増加部分列を求めればよい。

問題概要 N

問題概要 4近傍でflood fillして池の数を数える問題。

問題概要 長さN(sign[i]*A[i] = Fとなるような符号の付け方に関して、一意に定まるものは正か負かを、定まらないものはその旨出力する。どうやってもできないときはその旨出力する。 解法 今いくつの数字を持っているかをキーにしてDP。詳細はコード参照。 …

問題概要 N*N(N 解法 前処理で累積和を持っておいて全探索する。トーラス云々は4倍にしたテーブルの上でやっておけば特に意識せずに処理できる。計算量はO(N^4)で危ないがそんなに複雑な処理をしてるわけではないので何とか間に合う。

問題概要 長さN( 解法 余りの値といくつ使ったかを見ながらDP。オーバーフローや、値の重複に注意すること。

問題概要 都市がN( 解法 (i日目、どの都市にいるか)を状態のキーにしてDPするだけ。

問題概要 D(入れ子にして最大いくつ詰めることができるか求める問題。どの順に積めるかも出力する。 解法 ソートして順序を適切に定めた上でLIS。

問題概要 長さN( 解法 連続する区間を残すので[from, to)型のDP。 入力がファイル読み込みって書いてあったけど実際は標準入力からの読み込みだった。

問題概要 長さL( 解法 愚直だとO(N^2 * L)かかるが、DPの状態をあまり時間のみにすることで計算量をひとつ落とせる。

問題概要 重複のない要素N(クイックソートでソートしたい。ピボットを越えて値をスワップする際にコストが1加算される。また、ピボットの左側と右側ではそれぞれ相対順序が保存される。ソートするのに必要なコストの期待値を求める問題。 解法 状態を(今考え…

問題概要 レジスタが一つしかない。レジスタには今ある値sが入っている。sに対してs:=s*s, s+s, s-s, s/sの操作だけでsをtに変えたい。sをtに変えるコマンド列で最短かつ辞書順最小のものを求める問題。0 解法 幅優先探索する。到達可能なノードは2のべきだ…

問題概要 長さN( 解法 貪欲に小さい二つを選んで合併していく。これでうまく行く理由は、小さいものほど後に残す影響を小さくできるから。

結果。 easyだけ解いた。mediumは普通に難しかったし、どれだけ時間をかけたとしても解ける気がしない。

日程は未確定(おそらく3月18日)ですが3月18日に、大阪大学プログラミングコンテスト(OUPC)を開催します。 気軽にご参加下さい。 日時 (おそらく)2012年3月18日(日) 13:00 - 18:00 ジャッジ Aizu Online Judge 時間 5時間 問題数 12問程度 問題文 日本語問題…

問題概要 ノード数N(最小全域木を構成したときに必ず含まれるか、含まれる場合もあるか、必ず含まれないかを判定する問題。 解法 重みごとに辺を管理する。重みの小さい辺から処理する。ある重みの辺に限定して考えると、各連結成分を潰して考えたときに自己…

問題概要 長さ2*N(N全単射を作れるか判定する問題。 解法 ソートして前から比較するだけ。 Lucky Ticketの定義とかまったく必要ない情報が書いてあって混乱した。

問題概要 長さN( 解法 ソートしておく。第一要素が何かはすぐに分かる。第二要素が何かは第一要素の個数が分かれば分かる。

結果。 3/5完。A問題はどうでもよいので、それなりに解けた方だと思う。橋検出アルゴリズムが必要になったけど書いたことがなかったので困った。サンプルが親切だったのでミスに気づいて何とかなった。

問題概要 これのk=2版。入力はN 解法 MOD 3で場合分け。多倍長整数とか使う必要はなく、各桁の和のMOD 3を見れば良い。

問題概要 牛がN( 解法 夏合宿10とかSRMとかで出たタイプの貪欲。i->jの場合とj->iの場合の損失の式を比べると、-T[j]*D[i] jの順に処理した方がよいことが分かる。あとはこれをキーにしてソートするだけ。

問題概要 N( 解法 全探索。

問題概要 長さL( 解法 rotateさせる系の問題は同じものをつなげるのが定石。このときsuffix arrayを構築してやればよい。複数あるとき最小のものを答えたいので末尾に大きい値を加えておく。

問題概要 N( 解法 1単位量あたりの仕事をこなすのに必要な料金について、平均最小化の問題に帰着させる。蟻本にも載っている問題。

問題概要 2つの正整数x,yのgcdとlcm(ともに10^12以下)が与えられる。このときx+yのとりうる最小値を求めよ。そのようなx,yが存在しないときはその旨指摘。 解法 x=gcd*p, y=gcd*qとすると視界が開ける。解が存在しないのはlcmがgcdの倍数でないとき、あとはl…

結果。 2連続2完で嬉しい。3連続2完はまだないから次も2完したい。 250はgcdとlcmを見た瞬間x*y=lcm*gcdを連想して(よく出てくる)解法に気づけた。10^12という制約もルートで解けといわんばかりだし。実装もシンプルだったけど、1箇所int64をintと書き間違え…

問題概要 N( 解法 真面目にDFSで書く。ビット演算を使って多少高速化してやる。手元だとN=14で1秒以上かかっているのでアウトっぽいけどテストケースが弱いらしく制限時間ギリギリで通った。

問題概要 最長共通部分文字列の長さを求める。文字列長 解説 連結した文字列のLCPを用いる。コード略。