FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ABC082参加した感じ

なんか深秘録の大会やってたのでロビーで対戦してたら開始に遅れました。(12分くらい?)
そんなわけで今回は1WAの三完でした。言語はC。
dpの扱い方があまりにも下手・・・。


A問題beta.atcoder.jp/contests/abc082/tasks/abc082_a

入力の正整数a,bの平均値を切り上げしたものを出力。
(a+b+1)/2


B問題beta.atcoder.jp/contests/abc082/tasks/abc082_b

文字列s,tが与えられる。それぞれの文字順を好きに入れ替えてs',t'にしたときに辞書順でs'<t'にできるか。
要するにsを最小、tを最大になるように並べ替えた時にs'<t'になるか見るだけ。
ソートして比較して終わり。
比較がstrcmpで済むところをif文書いて判定したのを気にしてなんかいない。いない。
あとWA出したのはこいつでYesをYESにしていた。


C問題beta.atcoder.jp/contests/abc082/tasks/arc087_a

長さNの正整数の列aを良い数列にする。
数列bが良い数であるとは、次の条件が成り立つこと。
・bの各要素xについて、bに値xはちょうどx個含まれる。
aを良い数列にするために取り除くべき要素の個数の最小値を求める。

ABC081にも出現数を数える問題が・・・うっ、頭が。
今回aiは最大109なので出現数[ai]をインクリメントしていく方法は使えない。
Nは最大105なのでこちらはたいした数ではない。
つまり前回の頭悪そうな数え方が正攻法のはず。
そういうわけで入力を全部配列に突っ込んでソートし、頭から出現数を数えていく。

出力としては取り除くべき要素の個数なので、今見ている値をcとすると
cの出現数<cの時、cはすべて取り除くため答えに出現数を足す。
cの出現数>cの時、cはの出現数をcにするために答えに出現数-cだけ足す。


D問題beta.atcoder.jp/contests/abc082/tasks/arc087_b

二次元平面上の原点から命令列sに従い移動した時(x,y)に移動できるか。
sは次の2文字。
・F : 今向いている向きに長さ 1 だけ移動する。
・T : 時計回りまたは反時計回りの好きな方向に 90 度だけ向きを変える。
最初はx軸の正の向きを向いている。

まず最初にTが出るまでのFは必ずx軸の正の方向へ移動することになるので移動し終わった場所を原点として(x-(先頭のFの個数),y)へ移動する問題にできる。
この後がいろいろ迷走して、最初の方針の回答がx軸方向、y軸方向に全部で何回移動できるか調べて(x-x軸移動数)%2==0&&(y-y軸移動数)&2==0ならいけるのでは!?と書いてWAが5/49のところまでなまじ行けてしまったので余計悩むことに。
当然TFFで(0,0)が行けることになってしまうので間違いなわけで。
じゃあやっぱりdpだなということでdp[xの位置][yの位置][指示の回数][向いてる方向]・・・16000*16000*8000*4・・・w
その後xとyを分けたりしてとかなんやかんやしてても正解にたどり着けなかったので解説を見ることに。

正解としてはxとyは独立していてi回目の移動距離をdiとすると、
dp[0][8000]=1
dp[i][x+8000]=dp[i-1][x+8000-di] || dp[i-1][x+8000+di]
の漸化式からdp[移動回数][x+8000]=1になるかどうかを考えればいい。yも同様


そんなわけでレート推移。


開始遅かったのが悪い(自業自得)

余談ですが今回D問題AC後に他の方でC言語でD問題をACした提出を見てみたわけなのですが、
コメントを見ると貪欲法でやってる・・・?実際にコード見ても貪欲法。
TTFFFFFFTTFFFFFTTFFFF(x軸方向に6,5,4移動できる)
3 0
という入力があったとすると貪欲法では解けません。
twitterを見ても同様に言及している方がいましたので嘘解法が通るテストケースだったようですねぇ。
スポンサーサイト
11 | 2017/12 | 01
Su Mo Tu We Th Fr Sa
- - - - - 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31 - - - - - -
プロフィール

yy

Author:yy

最新記事
最新コメント
月別アーカイブ
カテゴリ
リンク
検索フォーム
ブロとも申請フォーム

この人とブロともになる

QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。