2016/1 Solved (2)
1/16
はじめてyukicoderコンテストに参加
yukicoderの★が少ない方簡単な方を解きまくった(研究室説明会の間ヒマで、かといって集中できるような場ではなかったので)
1/17 ~ 20
yukicoder★1埋め。
その中で気になったもの１つ： - yukicoder No.123 - カードシャッフル
今回のサイズだと愚直なシミュレーションでもACできる(submission)が、逆順に追いかけることでO(M)で求めることが可能である(submission)。
1/21
Educational CF #6に参加
ABCの3完
1/22
この数日でyukicoder★1埋めをしていて、それが終わり★2に突入
久々に実装が疲れる問題だった。といっても100行程度なのでなんだかなあ...
中間を省略して、まとめて計算して時間短縮するという考え方２問：
うるう年の周期は大きく見れば400年なので、400年で切って途中を省略して計算できる。
最初の１周で買う数bと、あたりがストックされる数stをメモすれば次から1週ごとに買う必要があるか、それとも1週ごとにあたりのストックが増えていくのかがbとstの大小比較によって分かる。
1/23
dwangoプロコン2016予選に参加
ABの2完、Eで部分点。ダメです
Eは部分点だけどDPかけたのはちょっとホッとした(Dも部分点はDPでなんかできるんじゃないかとか思ったけど投げてしまった)
1/24
「ピタゴラス数」だな、とすぐに思って効率よくピタゴラス数を列挙する方法はないものか...と思ったらこんな性質が有るらしい(http://izumi-math.jp/sanae/MathTopic/py_num/py_num.htm)。b=2*m*nはm,nが異なれば異なる値になるので、列挙可能になる。初めて知った
1/25
浮動小数点型を使うと明らかにバグりそうなサンプルがあったので、なんとかそれを避ける方法...と考えて、片隅にそういえばPythonでは固定小数点型があった気がすると冬休み読んだ本の内容を思い出し、decimalについて調べながら実装(submission)。書く量がすくねええ
小数点以下10桁までを表示させたいときはformatというの使うと良いらしい。formatに関してはなんかもっと幅広そうな感じが公式ドキュメントから伝わってくる...
1/26
パスカルの三角形使って組合せ求めよう。
1/27
1/28
1/29
SRM 680 Div1に参加
自分は、まずupToの値をキーにしてソート、それで隣り合う区間を見てそこで区間の幅が0ならupToの値は一致してないとダメで、もし区間の幅があるときにはその区間に入っているべき数字の数がquantityの差から分かるのでまずあるべき個数より幅が狭ければアウト、あるべき個数の2倍以上の幅があれば選ぶ数字はすべて偶奇を自由に決められる、その間の時はあるべき個数が幅の2倍になるまで幅と個数を1個ずつ狭めていってodとevにそれぞれ絶対に偶奇が決まる個数を記録しておく。これらがn/2よりも大きかったら残りの自由に決められるやつをどうがんばっても偶奇の数字がそれぞれがちょうど半分になるという条件を満たせないのでアウト(Submission)。 でもどうやらパッと解いてる人はdp書いてて、dpできるのか...って思った。結構Easyが今回落ちてたので、残ってホッとした。Div2に落ちなくてよかった...
1/30
DDPC2016 予選に参加
むずかった、A+部分点...Bは面白さに見る中心を据えるってとこにきづけなかったのはちょっとヤバいと思った
1/31
最初はSegtreeなのかなうーーんとか悩んでたけど、あれこれDPで行けるんじゃねってなって書く→O(n2)でn=50000だからメモリが足りない→よく考えると全部を保存しておく必要は内ないので１つ次元を落とせた→実行時間は超ギリギリ間に合った
ホントは平方分割とかして解くらしい...解説見たけどそっちはよくわからない。
