2012-01-18
Codeforces Round #103 (Div. 2) 反省
Codeforces | | 
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~と例示されたケースは一致するとは限らない
