keidaroo’s diary

底辺系競プロer

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とか割って毎回余りを出すのですが?わかりません。もしよければ、教えて下さい!

全然分かりません

abc034.contest.atcoder.jp
この問題なのですが、満点解法が全く分かりません。

たんちゃんさんのコードを参考にさせて頂いています
Submission #1435215 - AtCoder Beginner Contest 034 | AtCoder

毎回一瞬わかって、そのあとなぜか忘れて分からない状態が続くの、どうにかしてほしい

本題

フェルマーの小定理というものを使うらしい。
それの内容と証明自体はわかった。

(h+w-2)!/(h-1)!*(w-1)! % mod(10e9)という風になる
ここで、たんちゃんさんのコードによると、はじめのfor文で、h-1!を割っているように私には見えます。。これは本当なのでしょうか?←疑問点ポイント1

また、次のfor文で、iがh-1までループしていて、そこで、あれ?これh-1!で割ってね?ってなって更に疑問です


また、calc関数は、aのb乗をpで割ったあまりだそうですが、これについては何となくコードの内容も理解できました。ただ、コードを見ないと分からないので、本当に理解しているわけではないです。でも解説聞いたらうんうんって行くぐらいになっているとは思います。
自分用にメモっておくと、

  • フェルマーの定理より、  a^(p-2) ≡ a^(-1)(mod p)
  • なので、aのm-2乗でかける!これをそのあとmodであまり求める!答え同じ!

うーん、でもこれ使ってどうして上手くいくのだろうか
なぜかって、これ一つ一つの余りであって、全体の余りじゃないから、感覚てきに違う気がする。。←疑問点2

やっぱりフェルマーの小定理が良くわかっていない。。ここはリアルで誰かに聞きます。。

あと、一回目のfor文で掛け算したものの余りを求めたじゃないですか
余りを割るのってだめじゃね?とかなったので、これも教えて下さい!←疑問点三

疑問点2以外を教えて下さい!!twitterでもなんでもいいので教えて下さい!

ABC-Dへんてこ辞書

abc030.contest.atcoder.jp
いろいろバグりました+満点は取っていません(多分満点解は実装力のNasaで死ぬ)

問題概要+方針

配列の中をどんどん移動するパターンです。こういう複雑なの、苦手なのでいい経験になりました。(といっても完全に自分でとけたわけではない)
規則性を見つけて、そこから計算量を減らすって感じです。
具体的には

  • メモする配列を用意、i番目の辞書に何回目に調べたかを代入しとく
  • もうすでにメモってあったならば、その時点で閉路ができてるので終了
  • もし閉路の開始地点よりkが小さければ、シミュレーション

こんな感じです。

まいコード

#include<iostream>
#include<algorithm>
#include <string>
#include<cstdio>
#include<vector>
#include<queue>
typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
using namespace std;

int main() {
	ll n, a, k, b[10000] = { 0 };
	ll memo[10000] = { 0 };
	cin >> n >> a >> k;//代入
	ll nextsiraberu, count = 1;//調べようとしているもの、何回目かのカウント
	REP(i, n) { cin >> b[i]; }//代入
	nextsiraberu = b[a - 1];//次調べようとしているものを代入
	ll soremade, shuuki;//それまで何回作業したか,周期
	while (1) {
		memo[nextsiraberu] = count;//memo[今調べようとしているもの]に1をたす(一個前のwhile文で、もしもうすでに調べられていたらその時点でbreakされてるのでそこは心配しなくておけ)
		nextsiraberu = b[nextsiraberu - 1];//次に調べようとするもの(いまのcount+1)を代入
		if (memo[nextsiraberu]) {//もしもうすでに次に調べようとしているものが調べられていたら
			soremade = memo[nextsiraberu]-1;//周期に達するまで何個あったか
			shuuki = count - soremade;//最後のカウントから、最初-1のカウントを引き、周期の長さを求める
			break;
		}
		count++;//countをたす
	}

	if (k < soremade) {//もしkが周期に達する前で終わってたら
		bool b = true;
		REP(i, 100001) {
			if (memo[i] == k) {
				b = false;
				cout << i << endl; break;
			}
		}
		if (b) { cout << nise << endl; }
	}
	else {
		k -= soremade;//ここ忘れてたし
		k %= shuuki;
		REP(i, 100001) {
			if (memo[i] == k + soremade) {

				cout << i << endl; break;
			}
		}
	}
	return 0;
}

こんな感じです。このような問題は演習量かなあとか思っているので、理解はしているがまだもやもやしている今の状況は許容範囲と自分で勝手に決めます。
教えて下さったarukukaさん、本当に有難うございます!