2010-10-25

■ [others]JAPLJ contest 00:21

2010-10-25 13:00-16:00

http://judge.imoz.jp/?cid=8

http://d.hatena.ne.jp/JAPLJ/20101025/1288013176

問題文の冗長すぎない程度なストーリー性ときれいな図のおかげて取り組みやすかったです。

• A
  • グラフを描いてみる→なるほど再帰的に同じ図形が2倍の個数ずつできていくのか
  • p=0の場合に気をつけつつ適当に実装して提出
  • 60点…
  • 1ターンごとに上下が反転していくものだと思いこんでいた。修正して100点
• B
  • 優勝者がルートになるツリーを作って、ルートから見ていく
  • 勝者側の子の中から上位K人、敗者側の子の中から上位K-1人を集める、というのを再帰的に
  • 入出力とツリーを作るところでやけに苦戦。そこだけで20分くらいかかってしまった
  • やっと完成して提出したら70点…
  • 配列の長さが足りてなくてREしてた。修正して100点
• C
  • 図を眺めて、2種類の花の数が同じになる範囲だったら必ず結ぶ方法がある、と把握
  • 最初テキトーに書きすぎててO(N^2)になってしまってたので50点
  • スタック使ってO(N)にすると100点
• D
  • 2次元BITとかのデータ構造で矩形範囲に対する加算を効率的にできないかと考えるもわからない
  • 時間に対する2分探索も考えたが結局↑の加算を速くできないとどうしようもない
  • パターンの大きさがd*dで固定な事が鍵になってそうだけどそれをどう使うかわからなかった
  • 終了間際にとりあえず部分点取っとくかと全探索を書いてみたらPE
  • 出力の末尾に改行を付けないといけなかった。そこを直して30点
• E
  • 面積がN"以下"というのがちょっといやらしくてうまく考えられなかった
• F
  • 適当なノードをルートにしてツリーを作って、
  • 各ノードに対して、そいつの子ツリーそれぞれが自身の中でいくつ経路を持つかを求めて、
  • ボトムアップにDPするような感じでいけるんじゃないかと思ったが
  • 今着目しているノードをまたぐような経路をどう取り扱うとよいか整理できなかった
  • 解説を見ると大まかな方針は良さそうだが正解まではまだけっこう距離があった

結果は330点で15位/70人くらい

解けなかった問題の部分点を狙う気分にならなかった人が多いだろうので、順位はあてにはならないでしょうね。

前半で変なミスをしまくって後半の問題をじっくり考える時間がなくなってしまったのが残念です。

C++だと「うまくいかなくてもまあ慣れてないしなー」とつい思っちゃうのが駄目だ