keidaroo’s diary

底辺系競プロer

ABC-4 D マーブルポイント

解法

DPですね、枝狩り全探索でもできますが、コードを書くのが面倒です。(枝狩りは10^6ぐらいではいけそう)

ポイント1

この状況、ありえなくね?って思ってもとりあえずDPにぶちこむ!!

→もし状況自体がありえなくても、それが最適解になる可能性もありえないのであればDPにぶちこめる!!
 

ポイント2

簡単なDPから考える!!

ミドリムシ君の練習を見ているとこれをしていて、難しいDPから簡単なDPに落とし込めるなあ、と

ポイント3

順序だっているものは省略できる!!

今回の場合は色で順序付けできます、それをつかって合計数で省略をしましょう

サプリメント解説(ABC17-D)

DPの尺取りをやったことがなかったため、難しく感じました。forDPじゃないと解けないDP多すぎませんか。
あと高橋君、サプリメント10^5個飲むのは飲みすぎ。

解説

部分点解法

部分点解法は明らかにDPです。ここでは満点解法につなげるためにもらうDPを書きます
dp[i]=a(i=何個目の薬か、a=i個目の薬を選ぶとき、その前の薬から考えて何通りの選び方があるか)

dp[i]=(dp[i-1]+~dp[i-k])(i-kは同じ味の薬がでない最大の範囲)

こんな感じでもらうDPが書けます。
しかし、遷移の計算量含めるとO(N^2)となり、間に合いません。

満点解法

f:id:keidaroo:20171215234541j:plain
この画像の通り、同じ区間を何度も計算するのは無駄となります。
このようなときに使えるアルゴリズムには「尺取り法」と「累積和(いもす法)」というのがあります。
尺取り法→

www.slideshare.net

累積和→
累積和手法 - sataniC++

今回は尺取法を使います。

尺取法はその時その時で前にある値を削り、新たに新しい値を追加することで成り立ちます。
iを更新していくごとに、そのiの前でどれだけの範囲をかぶることなく選べるかというのを考えると、尺取法のような形になるのがわかります。
なので、
for(n個目までの薬){
while(かぶっている間は){
i個目の時に適応できない薬は合計から減らす
}
配列にi個目の時の選び方の通りを保存
i+1個目の合計にはi個目の合計が含まれるので、合計を二倍する
}
というようになります。

Fractionの別解について

別解とか言ってますが、この解法の人も結構いて安心しました。

joisc2008.contest.atcoder.jp
この問題、想定解だとファレイ数列というのですが、僕はその解法ではなかったので雑に解説します。

注目するべき点

k<=200000

これで、0からkまでループさせればいいということがわかりますね。
ここからは発想です、そのまま解を載せます

1/nから1/2までsetにいれる

i/a<(i+1)/aは自明なので、i/aが消去されれば(i+1)/aをsetにいれる

これだけでなんとかなります。
あとは、i+1とaの最大公約数が1出ないといけない、とかありますが、そこら辺は実装して気づくと思います。
時間に非常に焦っていたので、残念ながら雑になりました。申し訳ないです。

25個の整数の反省文。

自力で解けなかったので反省しています。この問題で使ったテクについてメモします。
間違っていたら教えてね!
あとこれは解説じゃないです。

大小関係が定まっているかつDPの問題は小さい方から見てけ!

これはもちろん思いつきました。ただ使えませんでした。

使ったテク2

bitDPは制約から判断しろ

これももちろん出来ました。ただこれも使えませんでした。
xi,j≠0 を満たす整数組 (i,j)(1≦i≦5,1≦j≦5) は 5 個以上存在する。
これで一発でbitDPとわかるだろ、20といえばbitDP

使ったテク3

bitにおいて、forループで計算されたあとたされることはない

これは初めて気づきました。
これはどういうことかというと、
dp[101(2)]+=dp[100(2)]で、101はもうすでに計算されて二度とforループが回ってこない、ということはないということです。
それはそうだけれども、まあいいでしょ、僕は驚いたので。

使ったテク4

座標をbitDPで保存する

うん、これは驚いた。
テク1を使うことによって、何が省略されるか、を考えるべき。

使ったテク5

適さないものを除外

適したものを足すより適さないものを足すほうが簡単にかけることがあります。

ぼくがやるべきこと

綺麗にノートにまとめる

整理しないとだめだってn回言ってる

2009年春合宿 ビンゴ

この問題、非常に難しく感じた上に、解説の需要がありそうなので書きます。
日本語が下手なので、twitterで質問してください。

問題

JOI 2008-2009 予選 問題6

問題概要は省略させていただきます(わからない人はその前に考えましょう)

解説

ポイント1

ビンゴの表は一列の数列に表せる!

これはほとんどの人が分かったと思います。左の列より右の列のほうが大きいかつ同じ列で昇順になっているので、それはそうですね。

ポイント2

これはDP!w

これもまた暫く考えていると予想はついてくるのではないでしょうか。ついてきますね。

ポイント3

とりあえずDPの構想を練ってみる!

この解説の続きを見る前に自分でDPを組み立ててみましょう。これ無理じゃん!wって気づいたらこの解説を見てください(もうDPの構想を練った人は続きを読もう)

DPの構想(仮)

必要な情報を考えてみます。
場所(何個目の整数か)//max50
今まで使った中で最大の値(要するに一個前の値)//max2000
今までの合計//3000
残念ながら、これだと50*2000*3000=3*10^8個の配列(メモリ)が必要になります。もちろん通りません。
ここでforDPでしかできない裏ワザ的な何かを使います。

使うと思った値を、使わずに済ませる→ループの順番を工夫して、その値を使わなくても自明な状態にする

ここで使わずに済ませる、自明にできる値は、予想がつくとは思いますが、今まで使った中での最大の値です。
最大の値が果たす役目は2つあります。
1.一個後の値を超えなければいけない。
2.制約で決められた値を超してはならない←これがなければ再帰でできます。
この役目2つを果たすためには、使う値を1からmまで順番に組み立てればいいです。そうすれば、3を組み立てたあとにそれより小さい1が来ること(これは例です)はなくなります。

最初のfor文で1からmまでループさせよう!

これで解決です。こうすれば、最大の値を考慮する必要があります。

もうこの先は、普通のDPです。頑張ってください!

No need

ブログもNo needでしょうが自分のために書いているので許して><

問題
D: No Need - AtCoder Beginner Contest 056 | AtCoder

解答
Submission #1631478 - AtCoder Beginner Contest 056 | AtCoder

この問題、難しかった。
嘘解法ばかり思いついて、自分には少し早すぎたのではないか、と思っています。(自分の忍耐力で何とかAC出来て嬉しい)

解説

まず、kより小さい状態からkより大きくなる、という遷移が起こっている状態を考えます。(ギリギリ集合、と呼ばせていただきます)
この時、制約とかを見るとわかる通り、何を使ったか、という情報は記憶することが不可能なことが分かります。
なので、それを使わない方法を探しました。
→既に使った数も、まだ使っていない数も同じようになる共通の性質を探しました。
ここでギリギリ集合を入れ替えることを考えます。
ギリギリ集合を入れ替えるとき、ギリギリ集合の中のどのような数を抜いてもkより小さくなることが前提となります。
このためには、大きいものから順に選んでいけば、ギリギリ集合を作ることが可能となります。
ギリギリ集合の最も小さい数をメモり、それより大きい数は入れ替えることができるため、必要な数となります。このとき、ギリギリ集合の中にもともと含まれていた数は最小値以上の物だけなので、これが共通点となり、成り立ちます。

まとめると

DPでギリギリ集合を作る(逆順ソートして)
ギリギリ集合の最小値をメモり、更新していく。
それより小さいものは、必要ない数字なので、countしておく。

分かりにくくてすみません(自分のことしか考えていない人の例

ゲーム「PERVERSE」について

利用規約

ゲーム「PERVERSE」の著作権は@keidarooと@simauma1203に帰属します。複製、販売、配布等の行為は一切禁止します。

言いたいこと

手伝ってほしい!!!

目標はこのゲームをiOSで公開することです。ただ、そのための費用が高いため、自分たちでその分の資金を稼ぐ必要があります。
このゲームはまだ面白さもいまいち、デザインもいまいちで、実際のところ、年一万円稼げるレベルの出来ではありません。
そのため、このゲームを共に開発してくださる方を募集します!(多分いないけど)

条件

ゲームPERVERSEのさらなるクオリティ向上に興味がある方。
技術のレベルは問いません。一切ゲーム開発及びその周辺の経験がない方でも構いません(私もゲーム開発の経験ないようなものなので)

仕事の内容

自分がやりたいことをやっていただいて結構です。
今のところ考えている仕事内容は、
・アニメーション(キューブ等の)
・動画制作(PR)
・ゲームシステム(つまらないので)

こんな感じです!緩い感じでやるので、気軽に@keidarooに声をかけて頂ければと思います!!