Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2011-08-08

[]KUPC 01:23 はてなブックマーク - KUPC - TopCoderの学習のお時間

http://atcoder.jp/contest/17/detail

初めてのオンサイトでのコンテスト参加。緊張感ありました。


開始前

10:40頃に京都駅に着く。

バス乗り場に大量の人がいるのを見て、地下鉄を選択して今出川まで。そこから京大まで歩こうかと思ったけど、体力使いたくないので百万遍までバス乗った(正解だった。京都は暑い)。

集合時間ぴったりに集合場所に着いたらもうほとんど全員集まっていた。すごい

会場の建物7年ぶりくらいに入った。すごく懐かしい

コンテスト開始10数分前くらいに全員の自己紹介が始まって「えっこれ時間大丈夫なの」と思ったけどさすが皆さん計算されてて非常にサクサク進んで問題なかった


A

数えるだけ


B

DPやるだけ


C

'a'はめ。哀れなAI


D

完全に詰まった。まったくわからない。UTPCでの悪夢(同じような雰囲気の問題にはまって4時間何もできなかった)がよみがえる

他の問題を一通り見た後で戻ってきて、「制約緩そうだし、いっぱい解かれてるし、テキトーにgreedyすればいけるんじゃないの?」と思って出したら通った。


戦略は、

bitを3N/8個立てる。まだN/8に達していないカードの中で最もたくさん使われている数字を順に使っていく。

という感じ。


E

最初FoxNumberを列挙してしまう。全然終わらない。

実質A+B以下の数を全列挙するのと同じことをやっているのだからそれはそうだ。

泥沼っぽくなってきたので「1問に1時間以上はまらない!」という目標のもと、いったん飛ばす


最後に戻ってきたら、「いやこれは制約から明らかに区間ふるいではないかー」と突然見えてあっさり正解できた。こんなことってあるんですね


F

幾何パートは書くだけで、本質的には区間の最大被覆に帰着される。

始点か終点かでソートでもしてやってDPなのかなあ、と思ったくらいのところまで。時間使えなかった。

典型問題っぽそうなので復習しておかねば


G

たいへん面白そうな問題。


しばらく考えていたけど、構成的に作ろうとばかりしていてランダムという発想は全く頭の片隅にも上らなかった。完敗。

ので、とくにランダムが良い悪いというのは思わなくて、頭のシワがひとつ増えたなーという感想


H

とりあえず全部同じ温度にするのを書いてみたけど、さすがにサンプル3ではねられた。

凹みたいな形になるとうれしそう? というのはちょっとだけは浮かんだものの、それが合っている自信もないし、ともかくDやEを通しておきたいしで、これも時間使えなくて残念だった。


DやEがすんなり通せていたら、直感解を試してみる余裕があったのかも


I

多くの人が通していたので、単純な解があるのかととりあえず行ごと、列ごとに大小関係が一様かどうかだけを調べるのを出してみた。

→(たぶんリジャッジで追加されたテストケースによって)WA


それでも大きく外してはいない直感はあって、その解を改変していって正解できた。


列について見ていくものとすると、一番高い点がある列の左右どちらかに他の列を一列ずつくっつけていく。

これまでくっつけたもののうち、端に来る可能性がある列はどれかを覚えておいて、全部の列がくっつけられるかを調べる。DP的?

単純なループの数はO(N^3)だけども本当にN^3回ループが回ることはありえないので計算量的には十分だった。


最初Javaで書いたのが、大きなケース(整数100万個読み取らないといけない)でTLEしてしまった。

Integer.parseInt(Scanner#next()) で読んでたのを Scanner#nextLine() で1行まとめて取って自前でパースするようにしたけど、まだ1ケースだけTLE

C++に書き換えると5倍くらい速くなって通った。


書き換えたときに、long使ってたところをlong longに直し忘れててあやうく謎はまりするところだった。すぐ気づけて良かった。


J

観賞用。

DPと見せかけて実は探索」というのは一度作ってみたかった問題だった



結果

6問AC/10問

8位/130人くらい


オンサイト組の中では一番上だったけど最上位との大きな大きな差が…



懇親会

問題制作の裏話などを聞く。

計算量の解析が「こいつらの項をいいかんじに足していくと…小さい!!!」みたいなので愉快だった

(何が言いたいかというと、脳内の解法を解説のスライドに落とすのは大変な作業なんだろうなということです)。


いもすさんのiPadを見て欲しくなったので注文してしまった。(前から買おうかと思っていたものではある)


焼かれたうなぎが出たのでおいしく頂きました。


たいへん楽しい1日でした。準備してくださったスタッフの皆さん、参加者の皆さん、ありがとうございます。

やっぱりオンサイトで参加するコンテストはひと味違いますね〜。

 |