スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

The 2nd COJ Progressive Contest

2011/12/14 20:00 ~ 12/16 22:00 ( 現地時間 )
COJ でコンテストがあった。

日本人は自分しかいなくてあまりモチベーションがあがらなかった。
問題は 17 問あって、TC や Cf に比べれば簡単なものが多い。
あと、純粋な典型問題が多いのも特徴。

5 時間くらいまったりやって全完した。

Tags : プログラミング COJ

問題

各問題に level が割り当てられていて、簡単な問題を解かないと難しい問題に進めないというルール。
問題数が多いので適度に省略しながら書く。

問題セットの原文はここを参照。

A. Finding Powers

N, M, Y が与えられるので XN = Y mod M なる X ( 0 ≦ X < Y ) をすべて求めよ。

B. Xtreme Encription

2 つの文字列 A, B が与えられるので、A が B の部分列かどうか判定せよ。

C. Error Correction

N × N のパリティチェック用 0-1 行列が与えられる。
誤りがあるかどうか判定し、訂正できる場合は訂正せよ。

D. WERTYU

与えられた文字列が英字キーボードでキー 1 つ分右にずらして打たれたとしたときに、本来打たれるべきだった文字列を答えよ。

E. Hanoi Tower I

ハノイの塔の最短手順を示せ。
最初はすべてのペグが左にある。

F. River and Cows

N 頭の牛が川のこっち側にいるので、すべてを向こう側に移動させたい。
移動に使えるいかだが 1 つだけあり、いかだには同時に何頭でも乗せることができる。
各 i に対して、いかだに i 頭同時に乗せた場合に向こう側に移動するのにかかる時間が与えられる。
向こう側からこちら側に帰ってくるのにも一定時間がかかる。
すべての牛を向こう側に移動させるための最短時間を求めよ。

G. Longest Increasing Subsequence (LIS)

数列の LIS の長さを求めよ。

H. Run-Length Encoding-Decoding

ランレングス圧縮された文字列が与えられるので元の文字列を復元せよ。

I. Ringroad

xxx

J. Bessie Weight Problem

N 個の藁束があって、各藁束の重さが与えられる。
藁束をいくつか選んで、それらの重さの和を H を超えないように最大化せよ。

K. Checking an Alibi

xxx

L. Brick Wall Patterns

W × 2 の長方形を 1 × 2 のブロックで敷き詰める方法は何通りあるか?

M. Hanoi Tower II

ハノイの塔の最短手数を求めよ。
ただし、通常のハノイの塔のルールに加えて、「隣接する棒にしか移し変えられない」 というルールを追加する。
最初はすべてのペグが左の棒にある。

N. Knights of Ni

H × W のフィールドに、自分といくつかの苺と 1 人の騎士がいる。
少なくとも 1 つの苺を経由して騎士の下に着くまでの最短距離を求めよ。
騎士の上は通過できない。

O. Sin(NA)

自然数 N に対して Sin(NA) を Sin(A) の多項式で表せ。
ただし、N が偶数のときは各項に Cos(A) をかけること。

P. Finding Minimum

数列 a[1..N] に対して、Q 個のクエリ
「 min{ a[L], a[L+1], ..., a[R] } を求めよ 」
を処理せよ。

Q. Mirko_Slavko New Game

2 つの数列 a[1..n], b[1..n] が与えられる。
各 i = 1, 2, .., n に対して、
b[1], b[2], .., b[i] を並べ変えたものを b'[1], .., b'[i] とするとき
max{ a[1] + b'[1], a[2] + b'[2], .., a[i] + b'[i] }
を最小化せよ。

1 ≦ N ≦ 10^5
1 ≦ a[i], b[i] ≦ 100

解答

コードを見たい人がもしいれば、コメントか twitter で言ってもらえれば対応します。

A.
全探索。
繰り返し二乗法とかしなくても間に合う。

B.
O(length) でなめる。

C.
ふつうにやる。

D.
埋め込む。
strrchr をはじめて使った。

E.
再帰の練習問題。

F.
DP.

G.
O(n log n) でやったけど O(n^2) でも間に合うサイズ。

H.
シミュレーション。

I.
なんとかふぉーしーずで最近解いた問題なのでコピペ。

J.
ナップサック問題。
入力サイズ的に DP.

K.
Dijkstra。
POJ で解いたことがあった。

L.
有名問題。
Fibonacci sequence.

M.
何年か前の阪大の編入問題で見たことある。
漸化式に直してぽん。
多倍長がいるので Perl で書いた。

N.
自分から BFS して、騎士から BFS する。

O.
de Moivre の定理と二項定理からがんばって求めた。

P.
RMQ.
Segment Tree のライブラリを貼り付けたら TLE したので、蟻本片手に Sparse Table を実装した。
あとで整形してライブラリに加えておこう。

L > R の入力があるのが邪悪。

Q.
唯一の考えさせる問題(

まず、a を昇順に並べ替えたとき b は降順に並べるのが最適だということは直感的にはすぐにわかる。
証明も難しくない。

数列の値が 1 以上 100 以下というのが重要。
バケットソートの要領でやれば、各 i について 100 回のループで処理できる。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。