■ [others]UTPC2010 
2010-07-04 12:00-17:00
昨年に引き続き参加しました。結果は7問正解で14位とまあ妥当なところです。
去年のKMCoder Monthlyでボコボコにされて以来wataさんらの問題には苦手意識があったのですが、通すべきものは通せてよかった。
東京大学のコンテストなのに京大（出身）の人が2連覇しちゃってるので、来年はmiracさんやir5さんあたりが勝ってくれると期待
懇親会にも参加させてもらいました。初対面の方だらけで「誰だこの謎の人は」みたいな感じでしたがKY力を活かしてそこそこ交流できたのではないでしょうか。
主催者の皆さん、参加者の皆さん、ありがとうございました。
以下ログ
練習セッション
- A
- 問題文の中に載っている解答例を見ずにテキトーに書いてサブミット
- WA。なんだと…
- 半径を二乗しないといけないのをやり忘れていた。こんなところで普通に間違えてしまうとは
- D
- これはまあ引っかけ的な何かがあるに違いない
- このグラフの作り方だと、枝の始点のノードが決まると終点のノードが決まってしまう。つまり、あるノードから出て行く枝は1つしかない、ということになる
- なので、1つのノードから見ていったとき、その先がどのようなグラフになっているかは1本道
- 入ってくる方は複数ありえるが、それはその前のノードからスタートするときに考慮されるので大丈夫
- ループがない場合は2色で塗れる、ループがある場合はサイズが奇数ならば3色必要になる
- あと枝が1つもない場合は1色
- 最初、3色になるのはループのサイズが3の場合のみと思っていて1回WAした後にAC
- 本番で出ていてもおかしくない問題だった
本番
- A
- やるだけ。AC
- B
- C
- そこそこ面倒そうだったので一旦とばす
- D
- Cよりはこちらの方が早く書けそうかな…？
- まず、べき乗の差を枝の重みとするグラフを作る
- 各ノードからDFSして、他のノードに到達したとき、通過した枝の重みの合計が以前に別の経路で来たときと同じかどうかを確認する
- WA。うげ。
- 無限ループを防ぐための訪問済みフラグが悪さをしてそう。もう少しシンプルな方針にしよう
- とあるノードに到達するときの経路が複数あるというのは、自分に戻ってくるループ経路があるというのと同値
- なので、自分に戻ってきたときに枝の重み合計が0になるかどうかを判定してやる
- TLE。うげ。
- この方針では上手くいかんのかなー。元に戻して訪問済みフラグを調整してみる
- WA。うーむ
- あ、解答の出力は"Yes"か"No"で出さないといけないのに、全部大文字の"YES"と"NO"にしてた…
- そこを直したらAC
- E
- 簡単な規則がありそうだけどすぐにはわからなかったのでCに戻る
- C
- BFSなどして地道に書く
- サンプルが合わない
- 盤面の上下が逆になっていた。ありがちなミスだ
- AC。Dよりも先にこっちをやるべきだったな
- F
- 残りを全部読む
- 当然すぐにわかるようなのはない
- このへんでEをちゃんと考えよう
- E
- 去年のEと似たように、決めつけてしまえば通っちゃうようなものなのでは
- たぶん一意に決まってしまう場合ってかなりレアですよね
- 列ごとに見ていって、一意に決まらない列があったらその時点でだめなんじゃないか
- ちゃんとした証明じゃないけれど
- どこかの列に余裕があったとき、他にも余裕がある列が存在する
- その列同士で玉の位置を入れ替えられるという自由度ができてしまう
- AC
- G
- 幾何は好きじゃないが、これはやればできそうだったのでやる
- まず、基本の直交座標をとる
- 天頂方向：z軸、地平線上真北：x軸、地平線上真東：y軸
- 北極星向きの軸を中心に回転させたいので、次の新しい直交座標系を考える
- 北極星方向：z'軸、z'軸を天底方向に90°回転させた方向：x'軸、地平線上真東：y'軸
- 調べたい星に向かうベクトルの、x'軸y'軸z'軸それぞれに対する射影を取ることで、xyz座標をx'y'z'座標に変換する
- x'y'平面内でz'軸中心に必要な角度だけ回転させる
- 元のxyz座標に戻して、z>=0だったら見えている
- しかしサンプルが合わない
- degreeをradianに変換し忘れているところを発見したけどまだ合わない
- 1行目の日付をパースするところが間違っていた…
- 直すとAC
- この時点で残り90分、あと1問いけるか
- H
- 解かれてる数からすると選ぶべきはHかIで、ひらめいてしまえば実装は楽そうなこちらで
- 数十分考えたが進展なし
- 問題文中に「ねこは貪欲なので…」とあったので貪欲解法も考えたがうまくいきそうになかった
- I
- 残り時間わずかになってきたので、たぶんMLEするだろうがとりあえず単純なBFS解法を書いておくか、とこちらに移る
- 状態は、盤面上の位置と、各禁止パターンの何文字目まで当てはまっているかをビットで記録したlong値の組で
- いろいろバグってサンプルが通るところまでも到達せず
- いずれにせよこれは想定誤解法でしたね
