スポンサーサイト

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

Autumn Fest 2012

2012/10/21 13:00~18:00
秋の祭典

Tags : プログラミング AtCoder 未解決

結果

A : AC(30/30)
B : AC(50/50)
C : AC(60/60)
D : AC(90/90)
E : AC(100/100)
F : AC(100/100)
G : AC(110/110)
H : AC(120/120)
I : 40/120
J : -
K : -

五時間がっつり取り組めて楽しかった。7 位だった。

解答

A.
与えられた規則にしたがって、合計点数を計算する問題。
難しいアルゴリズムは使わないけど、A 問題にしては実装が難しかった。
いきなりバグって出遅れた。

http://autumn_fest.contest.atcoder.jp/submissions/49667

B.
ぷよぷよっぽいルールでつながっているかたまりが何個あるかを求める問題。
Union-Find でやった。
1. 縦方向に 3 つ以上並んだ同色をくっつける
2. 横方向に 3 つ以上並んだ同色をくっつける
3. サイズ 2 以上の二つの同色のかたまりが隣接していたらくっつける
とやって、最後に
( 連結成分の個数 ) - ( サイズ 1 の連結成分の個数 )
を出力した。

http://autumn_fest.contest.atcoder.jp/submissions/49698

C.
カードを何回かめくって、カードの裏に書かれた数の和の期待値を求める問題。
カードをめくる操作はちょうど N-1 回繰り返されて、どのカードがめくられる確率も等しい ( 特別なカードはないんだから当たり前! ) のだから、カード i の期待値への寄与は X[i]・(n-1)/n くらいで、これを全部の i について足せばいい。
とか大雑把に考えて、書いてみると最後の大きいサンプルが合ったので提出したらあっさり通った。

( キタイチノセンケイセイらしい。100回以上は耳にしているし、何回も使ったことあるけどいまだにピンと来ない・・・ )

http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_03

D.
漸化式で定義される変な整数列の第 n 項を mod で求める問題。
部分点は M が小さいのでまともに解ける。
鳩ノ巣原理で隣接する二項の状態は O(M^2) 通りしかないことがわかるので、はじめてその状態に到達するのはいつかをメモっておくと、周期がわかって、周期の分は一気に飛ばして計算できるので OK みたいな。

満点解法は見た瞬間にはわからなかったけど、ネタ枠という注意書きがあったので気付けた。
ローカルで時間をかけて計算した結果を、適当に間引いて埋め込む。
ソースコード長の制限がわからなかったけど、特に問題なく通った。

部分点はまともに解いている。

部分点
http://autumn_fest.contest.atcoder.jp/submissions/49832

満点
http://autumn_fest.contest.atcoder.jp/submissions/50002

E.
1 歩、2 歩、3 歩、と上下左右好きな方向に動いていって、複数人が同時に原点に着く最短時刻を求める問題。
D の部分点解法を書いたあとに一旦こっちをやってたけど、全然わからなくて D に逃げ戻るとかやってた。
たくさん解かれているので簡単なはずだと信じて、全探索で規則性を探してみたら、シンプルが規則があったので助かった。
t 秒後に原点に着くルートがあるなら t+2 秒後に原点に着くルートもあって、結局、偶奇だけに注意して、最初に原点に着く時刻を求めればいい。
最初に原点に着く時刻は、コンテスト中はちょっと変なことを考えていた ( 詳しくは忘れた ) けど、解説スライドによると単に
1 + 2 + 3 + ... + t
がマンハッタン距離以上になる最小の t を求めればいいらしい。

http://autumn_fest.contest.atcoder.jp/submissions/50076

F.
連分数 (っていうんだっけ) の横線の長さを自由に決めて値を最大化する問題。
なんとなく、ad-hoc にうまいことやれば O(n) とか O(n^2) でいけるだろうという雰囲気が漂っていたので、その方針で考えていた。
まず、マイナスの数を数えておいて、偶数個なら最大化問題、奇数個なら最小化問題と考えることで、a[i] > 0 と思うことにする。
最大化問題を考える。
気持ちとしては、a[i] < 1 なら分母に、a[i] > 1 なら分子に持っていきたい。
小さいケースを全生成してみると、a[1] は必ず分子に、a[2] は必ず分母に置くしかないけど、それ以外の a[3], ..., a[N] は好きな方に置く方法があることがわかった。
もし a[N] < 1 なら、a[N] の真上に一番長い横線を入れると、a[N] が分母に来て嬉しい。なのでそうする。
a[N] > 1 なら a[N] は一旦無視して、a[N-1], a[N-2] と順に見ていく。
a[i] > 1 となる i があったら、a[i] を分母におきたいので、a[i] の真上に一番長い線を入れる。
すると問題は a[1..i-1] についての最大化問題と a[i..N] についての最小化問題に分割できる。
これを再帰的に解けばいい。
( 正当性の証明はしていない。)

最小化問題についてもいっしょ。

コンテスト中に書いたコードは少し冗長だったので書き直した。
http://autumn_fest.contest.atcoder.jp/submissions/50985

G.
bit 演算で定義された整数から整数への写像を短く書き直す問題。
定義式に bit 演算しか出てこないので、bit ごとに独立に見ればいいのはすぐに気付いた。
すると、入力が二通り(0or1)で出力も二通り(0or1)なので 4 通りしかバリエーションがない。
(1) 01 -> 00 となる bit は and を取る
(2) 01 -> 01 となる bit は 何もしない
(3) 01 -> 10 となる bit は xor を取る
(4) 01 -> 11 となる bit は 1 との or を取る
という風にすれば、求める出力が得られる。

具体的な bit 演算の式を作るところで
f(x)=(((x&A)|((x&B)^B))|C)
という式を作っていて、文字列長が 60 くらいになって苦しんだ。
( A は (2) に、B は (3) に C は (4) に相当する bit )

冷静に考えれば
f(x)=(((x^A)|B)&C)
という式でも同じことが表現できていて、これだと 50 文字に収まった。
( A は (3) に、B は (4) に C は (1) に相当する bit )

部分点解法がほぼすべてで、満点解法は f^(n) を f^(n mod 2) に置き換えるだけでいい。
n == 0 だけは例外というのに少しはまったけど。

部分点解法をまず書いていて、それを満点解法に拡張したので、変数名がややこしいことになっている。

部分点
http://autumn_fest.contest.atcoder.jp/submissions/50439

満点
http://autumn_fest.contest.atcoder.jp/submissions/50487

H.
区間の集合から包含関係で結ばれた長さ D の chain を数える問題。 ( ←日本語がおかしい )
満点解法は取っ掛かりがつかめなかったので、D=2 の部分点に絞って考えていた。
D=2 だとわりと何とかなって、区間を左端の昇順でソートしておいてスイープしながら BIT で足しこんでいけばいいということに気付いた。
部分点がわかると、満点は単にそれを D 回くり返す DP だということに気付いて、意外と何とかなった。

部分点
http://autumn_fest.contest.atcoder.jp/submissions/50259

満点
http://autumn_fest.contest.atcoder.jp/submissions/50289

I.
全然わかんなかったので、ほんとにナイーブにやって部分点だけとった。
10^9 だけどタイムリミットが 5 秒もあるし処理も軽いので間に合う。

部分点
http://autumn_fest.contest.atcoder.jp/submissions/50330

J.
時間がなくて考えられなかった。
どうせ DP だろうなーとか。

K.
楽しそうなリアクティブだったけどこっちも時間がなくて手付かず。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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