読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

今日の競プロ(2015/04/06)

ちょっと忙しいので今のうちに予約投稿…

ところでまず,昨日のARCの結果から…

arc036.contest.atcoder.jp

順位表 - AtCoder Regular Contest 036 | AtCoder

運良く,B問題までサクサクと解くことができました.
そしてC問題の部分点狙いもなんとか….

その結果,初めて二桁の順位が取れました.びっくりデス.
そして5級になりました! やったね.

ARC 036 A, B

A問題は出力ミスで一回出し直した.もったいない.
連続する3つの配列を足して~ みたいな問題でしたので,こんなかんじでsum使って簡単にチェック.

if sum(tlist[i-3:i]) < K:
        print(i)

わざわざ配列を3つ書かなくてもさくさくと書けるのが良いですね.


B問題も基本的にはさくさく.
はじめから100点解法に近い発送ができたので,良かった.

ただ,データの最後の方で切れている山(と表現すればいいのだろうか)の処理や,データがひとつしかないときの処理を忘れており,二回出し直しました.
*1

右上がりなのか,右下がりなのかを判断しつつ,右下がりが終わったところで山とみなして更新,ループが終わったら最後の山のデータっぽいところを更新.

ARC 036 C

総当りで10点だけでは確保.
結果としてこの10点が順位に大きく影響し,ぱっと見れば好成績っぽく見える結果になりました.


で,ここの10点分を作ったところで終了だったんですが….

とりあえず解説を聞いて,dpのテーブルがどう更新されるか,とか理解した上で,大体手本をpythonに変える形で提出し続けたんですが….

f:id:kawasumi_yume:20150405191053p:plain

(pythonじゃ実行速度が足らなくて)ダメみたいですねえ….

一応,Javaも書けるので,Javaでほぼ同じアルゴリズムを書き直したところ,無事にACしました.

ちょっと納得がいかないですねえ^^^^^^;;;;

探索回数を減らすためにif文を挿入したりして,頑張ったけどそれも無駄でした(でも最初の実行時間に比べれば,最終的に 1 / 2 の時間になりました)

考えうる原因としては,リストの精製コストじゃないかなと個人的には思い当たっています.
内包表記と言えど,for文だからねえ…
それを何百回も作っていたらそりゃ遅くなりますよ.

実行速度的なところの考察としては,組み込み関数便利だけど,if文の方が良い動きしている時もあるなーとか.
sumはそこそこ早そうなので,今後も使える機会があれば使おう.
あと,3次元配列より2次元配列使ったほうが早いみたい.

何十万回,何百回と処理を行うに連れ,少しの改善でも全体の処理時間に大きく影響するんだなあと実感したコンテストでした.

で,最後逃げ(?)でJavaで通しておきましたけど,pythonで通すことは出来るんでしょうかねえ….

機会があればリベンジしたいですね.


D問題に関しては,解説を聞いてわかったようなわからないような…
生放送で3分で解いてるの怖すぎていみわからなかったですね.


で,ここまででARC 036の話は終わりです.C問題時間内に解けるようになりたいね!

ABC 013 C

総当りでいいなーと思って,総当りのソースコード出したら失敗したのでおとなしく解説スライドを読む.
すると,食いだめ!みたいな考え方があり,最初自分が考えてたのそのままでよかったんだなあと納得.
100点の回答はそれを考慮した上で書いたら,すぐ解けました.

abc013.contest.atcoder.jp


101点の方は,Yの表現方法がよくわからなかったので,他の人のソースコードを参考にしつつ通す….

abc013.contest.atcoder.jp

で,ABC 013のD問題取り組んでいるところなのですが,現在の進捗としては30点の問題を解き終わった程度です.

数学的に環みたいになるのかなあと思ったら,満点の別解がその方法みたい.
ダブリングを使うようですが,今まで考えたこともなかったので,うまくいくかどうか….

数学的に考察すると解けるような問題にも,慣れていきたいですね.


明日から少し忙しくなるので,取り組む問題が若干簡単になってしまうかもしれませんが,引き続き毎日解くことをやめないようにがんばります.


ちなみに,ABCはいまこんな感じ.D問題以外はだいたい埋めてあります.

AtCoder Problems

f:id:kawasumi_yume:20150405192939p:plain

(ありがとう,AtCoderProblems!)

*1: サンプル2って山って言えるんですかね….それと右上がりで終わるデータとかも山なのか?