ABC-041-D
概要
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)
疑問点としては、
「各ビットを指定した数だけ右へシフトします。右端からはみ出した部分は削除され、シフトしたことによって空いた左端は「0」が格納されます。結果として11を1ビット右へシフトすると5となります。プログラムで実際に記述する場合は次のようになります。 」
これ、int型とかだと自動的に消されませんか？０が左側につくと死ぬと思うのですが...
あと、何桁目が1か0か確認するのって10,100,1000,10000とか割って毎回余りを出すのですが？わかりません。もしよければ、教えて下さい！
全然分かりません
abc034.contest.atcoder.jp
この問題なのですが、満点解法が全く分かりません。
たんちゃんさんのコードを参考にさせて頂いています
Submission #1435215 - AtCoder Beginner Contest 034 | AtCoder
毎回一瞬わかって、そのあとなぜか忘れて分からない状態が続くの、どうにかしてほしい
本題
フェルマーの小定理というものを使うらしい。
それの内容と証明自体はわかった。
% mod(10e9)という風になる
ここで、たんちゃんさんのコードによると、はじめのfor文で、h-1!を割っているように私には見えます。。これは本当なのでしょうか？←疑問点ポイント１
また、次のfor文で、iがh-1までループしていて、そこで、あれ？これh-1!で割ってね？ってなって更に疑問です
また、calc関数は、aのb乗をpで割ったあまりだそうですが、これについては何となくコードの内容も理解できました。ただ、コードを見ないと分からないので、本当に理解しているわけではないです。でも解説聞いたらうんうんって行くぐらいになっているとは思います。
自分用にメモっておくと、
- フェルマーの定理より、 a^(p-2) ≡ a^(-1)(mod p)
- なので、aのm-2乗でかける！これをそのあとmodであまり求める！答え同じ！
うーん、でもこれ使ってどうして上手くいくのだろうか
なぜかって、これ一つ一つの余りであって、全体の余りじゃないから、感覚てきに違う気がする。。←疑問点２
やっぱりフェルマーの小定理が良くわかっていない。。ここはリアルで誰かに聞きます。。
あと、一回目のfor文で掛け算したものの余りを求めたじゃないですか
余りを割るのってだめじゃね？とかなったので、これも教えて下さい！←疑問点三
疑問点２以外を教えて下さい！！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[今調べようとしているもの]に１をたす（一個前の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さん、本当に有難うございます！
tupleについて
tupleの分かりやすいサイトなどなかったので、自分用にまとめます
#include <tuple> tuple<ll,ll,ll> tup;//宣言 tup.make_tuple(1,1,1);//これで代入 get<0>(tup);//参照 swap(get<0>(tup),get<1>(tup));//swap
以上です
Union Findの練習及び、テンプレ
//llとはlong long の略です ll parent[100000],depth[100000] ll init(ll n){ REP(i,n){ parent[i]=i; depth[i]=0; } } ll find(ll x){ if(par[x]==x){return x;} else{return par[x]=find(par[x]);} } void merge(ll x,ll y){ x=find(x);y=find(y); if(x==y){return;} if(depth[x]>depth[y]){ par[y]=x; } else{ par[x]=y; if(depth[x]==depth[y]){ depth[y]++; } } } bool same(ll x,ll y){ if(find(x)==find(y)){ return false; } return true; }
ごめんなさい、復習のために直接打ち込んだので、汚いです。。
チーズ
joi2011yo.contest.atcoder.jp
あと少しでAGCなので雑に書きます
割と気力なさげな感じで解きました。もちろんバグ出ました
@Keidaroo
— eiya@受験競プロC++ (@eiya5498513) 2017年6月18日
・問題文をよく読む
・関数分けする
・コメントを書く
・一文字変数をやめる
・要らないものは消す
・コンパイラの警告を見る
あたりをやりましょう（割と適当に言っています）
プロからの助言です、以後バグにひっかかったらこうします
あとVSのエラーの度合い見たいなやつを設定できたというのも進捗の一つ（途中からなぜか表示されなくなったのは気のせい、多分もうすでにその時には治っていたのか（は？））
バグの原因
工場があったとき、そこを通り抜ける場合を入れ忘れていた（数字があっても、条件が満たされない場合、そこから移動する）
あと、別の道で通ったときでチーズ食った時も、countとして足されてしまうので、それぞれにqueueを足さないとだめ
Submission #1359274 - 第１０回日本情報オリンピック 予選（オンライン） | AtCoder
はいよ（雑
しっかりとコメント書いて行ったり、丁寧に解くことがバグ解決のためになるようです
最近バグ直すのが昔より速くなった気がして多少の喜びを感じています（たまたまの模様
