Hatena::Grouptopcoder

iwbtr - kmats このページをアンテナに追加 RSSフィード

2012-01-18

Codeforces Round #103 (Div. 2) 反省

| 05:18 | Codeforces Round #103 (Div. 2) 反省 - iwbtr - kmats を含むブックマーク はてなブックマーク - Codeforces Round #103 (Div. 2) 反省 - iwbtr - kmats Codeforces Round #103 (Div. 2) 反省 - iwbtr - kmats のブックマークコメント

Rank: 1129/1365

Score: 430

Solved: 2 (A: 480, 00:10)

Hack: -1

Rating: 1418 -> 1350 (-68)


なんというか色々と散々な回.

144A

配列から最大値かつ出来るだけ左にある要素と,最小値かつ出来るだけ右にある要素を探し出し,それらをスワップで移動するのにかかるコストを計算.最大要素と最小要素が入れ替わる際にスワップ1回分得するのを忘れなければいいだけ.


144B

はじめに与えられるテーブルの対角線上の2頂点がどの組み合わせか分からないので,何が来たとしても(xa, xb)は左下,(xb, yb)は右上(即ちxa < xb and ya < yb)になるように頂点の値をスワップしておく.

その後vector< pair<int, int> >にテーブル上の頂点を全て格納し,各頂点毎と各ストーブの距離がストーブの範囲内か調べる.範囲内だとわかった時点で答えを+1してbreak.

・・とすればいいはずなのに,pretest 7で落ちる.距離とストーブの半径の比較の際にdoubleの誤差が問題なのかと,色々試してみるが落ちる.どこかの変数でintを使うとオーバーフローするのかと,全てlong longにしてみるが落ちる.何故だし.

で,よくよくコードを読み返してみれば,(xa, xb)と(ya, yb)のスワップの部分でケアレスミス・・orz

今にして思えば,距離distと半径rの比較の際は,dist^2とr^2で行えばわざわざdoubleにキャストして,誤差を考えて・・という必要はなかった.これも反省.


144C

2つの文字列s, pが与えられ,pのアナグラムはsのsub stringの中にいくつ含まれるか?という問題.前者の中には'?'が含まれており,どのアルファベットに置き換えてもよい.

見るべきはpのアナグラムなので,p中の文字の順番は関係ない.なので,pに各文字がいくつ含まれるかをa[26]に保存しておく.あとは,sの先頭から,pの長さと同じ分だけ切り出しては文字数を数えてaa[26]に保存し,はじめに保存したa[26]の値を上回らなければ答えを+1.

これを愚直に2重ループで実装したところTLE

過去に出たsub stringは再調査しなくてもいいように,sub stringをキー,結果を値としてmap<string, int>を使ってDPしてみてもTLE

test結果を見ると,ひたすら??????????????????が続く入力の時にやられていたので,sub stringが全て?で構成されているときは特別に別途処理するようにしてもTLE.なん・・だと・・?

どうやら考え方が根本的に間違っているようなので,後日改めてチャレンジ.

条件にs.size() < p.size()もあり得ると書いてあったので,それを考慮していないように見えるコードをHackしてみたら返り討ちにされた・・

Cを解き始めた時,a[26]の初期化ミスのおかげで,a, b, c以外の文字が含まれていると正常動作しないバグがあった.が,例示されたテストケースではa, b, cしか用いていなかったので気付かなかった.これをsubmitするとpretest1でWA.この時点で,pretest1~は例示されたケースと同じと思い込んでおり,手元では正しいのに何故pretestは通らんのだ?バグ??としばし混乱した.pretest1~と例示されたケースは一致するとは限らない・・と考えていいんだよね?

144D

みてない.

144E

みてない.


反省点

  • ケアレスミスに気付かなかった
  • a^1/2とbの比較を直接行おうとした
  • pretest1~と例示されたケースは同じだと思い込んでいた

教訓

  • ケアレスミスこそ最大の敵.問題文だけでなく,コードを一からくまなく追いかける
  • a^1/2とbの比較は2乗してaとb^2で行う
  • pretest1~と例示されたケースは一致するとは限らない