keidaroo’s diary

底辺系競プロer

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に声をかけて頂ければと思います!!

ABC-041-D

abc041.contest.atcoder.jp

概要

N匹のウサギがいて、それを矛盾せずに並び替える方法はなんとおり?
頂点(ウサギ)には特徴がある場合とない場合があるぞい。

よかったところ

解説をちらってみてしまったが、大体のところは自分でくみたてられた。

反省点

解くのに時間をかけすぎてしまった。解法を変えることも大事って一番いわれていること(適当)
bit &ってやるとき、powで累乗してしまっていた。シフトした方がいいので、次からはシフトを使ってみる。
構造を理解したつもりであまり理解してないのでだめ

やりかた

bitDPというものでやります。私は、dp[vコメの頂点][どの頂点に行ったのかを表したbit]
という風にやりました。

その後、条件があるところは、たとえばxがyより先にあるとしたら、次の頂点がxのとき、すでにyが含まれていたら、return というようにやります。

ここが一番引っ掛かった部分なのですが、私は次の頂点がyのとき、もしxが逆に含まれていないときはreturnというようにやりました。

これはなぜダメなのかが分かりませんが、確かにこの方法は正解法を逆向きで同じようにやったときと同じなんですね・・・

多分、1つずらしたらなんとかなるとか?そんな感じだと思います。この度、あきらめるという方法を思いついたのでそこについてはゆっくり考えさせていただきます。


ソース

#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef long long int ll;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
 
//------------------変数-----------------------//
ll n, m;
typedef pair<ll, ll> P;
 
ll dp[20][100000] = {};//vコメの頂点のとき、どの頂点に行ったか
vector<vector<ll>> G(50001);
ll maxa = 0, moto = 0;
queue <ll>q;
ll bitmax = 0;
//-------------------関数----------------------//
 
ll DP(ll vertex, ll bit) {
	ll cnt = 0;
	if (bitmax == bit) {//もしすべての頂点に行ったなら
   		return 1;
	}
	if (dp[vertex][bit] >= 0) { return dp[vertex][bit]; }//return dp
	REP(i, n) {
		ll hoge = pow(2, i);
		if (!(hoge&bit)) {//行ったことが無かったら
			bool flag = true;
			REP(j, G[i].size()) {//その前に行かなければならない頂点はいくつあったか
				ll piyo = pow(2, G[i][j]);//そこに行ったことがあるかどうかを確かめるため
				if ((piyo&bit)) {//ここ、もし行ったことがあるなら逆に条件通るだろ
					flag = false; break;
				}
			}
			if (flag) {
				cnt += DP(i, bit + hoge);
			}
		}
	}
	//cout << vertex << endl;
	return dp[vertex][bit] = cnt;
}
 
int main() {
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	bitmax = pow(2, n) - 1;
	REP(i, m) {
		ll x, y; cin >> x >> y;//yのほうが 速くつくって言いたいの?
		x--; y--;
		G[x].push_back(y);//yコメの頂点はxより後じゃないとだめ!
	}
	ll cnt = 0;
	REP(i, n) {
		ll hoge = pow(2, i);
		cnt += DP(i, hoge);
	}
	cout << cnt << endl;
	return 0;
}

これなんですが、G[x].pushback(y)のxとyを逆にしても、同じことが起きます。なぜならもらうDPと同じようになるからです。私が考えていたことは、結果的にもらうDPになっていました。。。
精進します。

最後に

最後まで教えて下さったSatanicプロ、本当に有難うございます!おかげさまでACしました!

ビット演算についての疑問及びメモ

0x100とか0b100とかいうのは、何進数か
xは十六進数
bは二進数

10進数を二進数に変える方法は、to_binString(100)

ビット演算子 - 演算子 - C言語 入門
演算子はこちら

疑問点としては、
「各ビットを指定した数だけ右へシフトします。右端からはみ出した部分は削除され、シフトしたことによって空いた左端は「0」が格納されます。結果として11を1ビット右へシフトすると5となります。プログラムで実際に記述する場合は次のようになります。 」

これ、int型とかだと自動的に消されませんか?0が左側につくと死ぬと思うのですが...
あと、何桁目が1か0か確認するのって10,100,1000,10000とか割って毎回余りを出すのですが?わかりません。もしよければ、教えて下さい!