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~と例示されたケースは一致するとは限らない