スポンサーサイト

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

IJPC #1, #2, #3

IOIer Japan Programming Contest 2012
IJPC #1 : 2012/5/20 13:00~18:00 (JST)
IJPC #2 : 2012/6/24 13:00~18:00 (JST)
IJPC #3 : 2012/7/22 13:00~18:00 (JST)

まとめて書く。

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

IJPC #1

45 + 30 + 100 : 7 位タイ (銀)

A.
木の頂点削除クエリ

いつもの感じだとクエリを逆から見て Union-Find したくなるけど、grader をはさんでいるのでそうはいかない。
オンライン~
小課題 1 は毎回素直に DFS して最大サイズの連結成分をみつければいい。
小課題 2 はちょっと悩んだけど、set をつかって何かやった。( 覚えてない )
小課題 3 は全然わからなかった。あとで解説を見て一応解いたけどかなり難しかった。Euler tour, segment tree, BIT など、JOIer, IOIer 御用達のテクニックが満載。

B.
銀メダル

適当にスイープして解いたらしい。あんまり覚えてない。
座標圧縮とか imos 法とかやった形跡がある。

C.
転倒数クエリ

小課題 2 までは、よくある BIT でやるやつ。
以降はやばい。
解説を読んで書いた。小課題 4 は値を変えるとどこがどう変わるのかを詳しく観察する必要がある。

ソースコード
A ( 小課題 1 )
A ( 小課題 1, 2 )
A ( 満点 )
B ( 小課題 1 )
B ( 小課題 2 )
B ( 満点 )
C ( 小課題 1 )
C ( 小課題 1, 2 )
C ( 満点 )

IJPC #2

100 + 100 + 0 : 6 位タイ (金)

A.
IMO

グラフが一直線のときは、数列の転倒数を数えるのと同じなので、小課題 1 はバブルソートで、小課題 2 は Fenwick tree で。#1 でもあったよね。
小課題 3 は、結局、各連結成分が一列になってないと解なし ( 解説とほぼ同じ証明をした ) なので、小課題 2 と対して変わらない。ほかの問題に比べると単調でちょっとだけがっかりした。これくらいのもあったほうがいいのかもしれないけど。
解説にある、昇順の転倒数 + 降順の転倒数 = N*(N-1)/2 というのは不思議だった。なんでこうなるんだろう。

B.
迷路

特におもしろいと思った。
小課題 1 は、迷路の情報および taro の位置をナイーブに全部送って、jiro の位置もナイーブに全部調べることで特定して、最後に BFS すればいい。
小課題 2 は難しくてなかなか気付かなかったけど、迷路をじっと見ていたら全部を送る必要はないことに気付いたのでそれで。他は小課題 1 と同じ。
小課題 3 以降は、少ない質問で二人の位置が特定できればよくて、変な乱択とかやってたけど規則的な入力で簡単に撃墜できてしまった。さらにじっと迷路を見ているとうまく二分探索で位置が決められることに気付いて、それを書いた。query(dx,dy) の dx, dy に 1000 以上の値を指定していて、なかなかそのことに気付かず RE を出しまくった。

C.
ポーター

小課題 1 は、いわゆるやるだけだけど、条件分岐を間違ってバグがとれなかった。
小課題 2 以降は解説を読んだ。複素数の mod を使う問題にははじめて会ったので斬新だと思った。
( 一応、代数の講義で整域とかユークリッド互助法の一般化とかの話は知ってた )
ただ、解説どおりのコードを書いたつもりでもテストケース 1 つあたり 9sec くらいかかって TLE するので、この方法だと解けないんじゃないかと疑ってる。時間を計ってみると long long の割り算が遅い。
小課題 3 はユークリッド互助法。方針としては素直だと思った。ガウス整数クラスはライブラリ行き。

ソースコード
A ( 小課題 1 )
A ( 小課題 1, 2 )
A ( 満点 )
B ( 小課題 1 )
B ( 小課題 1, 2 )
B ( 満点 )
C ( 小課題 1 )
C ( 小課題 1, 2 ) ( 2 は TLE する )
C ( 満点 )

IJPC #3

16 + 100 + 62 : 4 位 (金)

A.
最小全域木のクエリ

V 回 Kruskal するだけの自明な解法で小課題 1 はクリア。
最初に一回だけソートしておけば O(VEα(V)) になって、定数倍改善すれば小課題 2 もできそうな気もしたけどそんなに甘くなかった。TLETLETLE
作問チームがチームだし、最後の 1 点は動的木なのだろうなぁと思っていた。

B.
三次元幾何 ( のふり )

問題文の gif アニメがすごかった。

ろうそくの位置や影の位置を好き勝手に決めると、ほとんどの場合、解なしになる。
ようするに、明らかな過剰決定系で、与えられた全部の情報を使わなくてもよさそう。

小課題 2 が考えやすそうだったので、そこから考え始めた。
対応するろうそくと影を線分で結ぶと、お化けを中心としたくさび形みたいな形が浮き上がる。
一番左にある影は ( 気分的には ) 一番右にあるろうそくに対応していて、逆もしかり。
だから、
「一番左の影と一番右のろうそくを結んだ直線」と
「一番右の影と一番左のろうそくを結んだ直線」の交点がお化けの位置になる。

ろうそくたちの x 座標が異なるので、一番右(左)にあるろうそくというのは一見してわからない。
なので、ろうそくの位置を x 軸に直交する直線 ( x=1 とした ) 上にそろえて考えた。
ここまでで小課題 2 が正解。

小課題 2 でお化けの x, y 座標が求まっていて、もう少しで小課題 3 も取れそうな気がした。
公式の解答がとてもシンプルでいいけど、それは思いつかなかったので、z 座標を三分探索で決めることにした。
どのろうそくとどの影が対応するかは大体わかる ( ちょっとはまったけど ) ので、
Σ_i | ( ろうそく i の影の z 座標 ) - ( ろうそく i の影が来るべき位置の z 座標 ) |
を最小化すればいい。最小値は 0 になるはず。
この関数は z について凸 ( 凸関数の和は凸! ) だから、三分探索で最小化できる。
これで小課題 3 も正解。コンテスト終了 30 秒前だった。

C.
しょうじきなきつね

あらかじめ n 回 question(1,0,・) をしておけば、
「 0 番目の人が正直か嘘つきかわかれば、残りの人は自動的に決まる」
ということに最初に気付いた。
なので、小課題 3 まではいきなり解けた。
嘘つきに question(2,・,・) をすると、偶然、嘘つきの人数が答えられることがあって、それに気付かずに
5
1 1 0 0 0
2 2 3 0 0
というケースで impossible を返してしまって、ずいぶんはまった。
サブミットデバッグしていた。

小課題 4 は一向に解き方が浮かばなかった。そもそも√という発想がなかった。

ソースコード
A ( 小課題 1 )
A ( 小課題 1, 2 )
B ( 小課題 2 )
B ( 満点 )
C ( 小課題 1, 2, 3 )
C ( 満点 )
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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