2017-07-27

全然分かりません

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

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

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

本題

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

$(h+w-2)!/(h-1)!*(w-1)!$ % 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でもなんでもいいので教えて下さい！

2017-07-13

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さん、本当に有難うございます！

2017-07-11

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

以上です

2017-07-11

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;
}

ごめんなさい、復習のために直接打ち込んだので、汚いです。。

2017-06-18

チーズ

joi2011yo.contest.atcoder.jp
あと少しでAGCなので雑に書きます

割と気力なさげな感じで解きました。もちろんバグ出ました

@Keidaroo
・問題文をよく読む
・関数分けする
・コメントを書く
・一文字変数をやめる
・要らないものは消す
・コンパイラの警告を見る
あたりをやりましょう（割と適当に言っています）
— eiya@受験競プロC++ (@eiya5498513) 2017年6月18日

プロからの助言です、以後バグにひっかかったらこうします

あとVSのエラーの度合い見たいなやつを設定できたというのも進捗の一つ（途中からなぜか表示されなくなったのは気のせい、多分もうすでにその時には治っていたのか（は？））

バグの原因

工場があったとき、そこを通り抜ける場合を入れ忘れていた（数字があっても、条件が満たされない場合、そこから移動する）

あと、別の道で通ったときでチーズ食った時も、countとして足されてしまうので、それぞれにqueueを足さないとだめ

Submission #1359274 - 第１０回日本情報オリンピック予選（オンライン） | AtCoder

はいよ（雑

しっかりとコメント書いて行ったり、丁寧に解くことがバグ解決のためになるようです

最近バグ直すのが昔より速くなった気がして多少の喜びを感じています（たまたまの模様

2017-06-16

暑い日々のオーバーキル解法の詳しい説明

（詳しいとか言いながら雑です、質問があったらしてくださると助かります）

arukuka.hatenablog.com

私がかけた６日間という長さに比べて、一日/inf時間で解いたアルクカさんはプロです。

本題に入ります

オーバーキル解法の雑解説

f:id:keidaroo:20170616204028j:plain

字が汚くて申し訳ないですがこんな感じです。
つまり、バウンドの高さが問題になっています。

書き忘れていたのですが、バウンドなしの場合、最大をとっても最小をとってもその間をとっても結果は変わりません。

なので、結局最大または最小をとっていけばいいことが分かります

分かりやすいオーバーキル解法の解説
eiya5498513.hatenablog.jp

あ、あと「イキっているとか思わないでください」
とかいうのは、記事を書き始めたその時は感情が嬉しさによって狂っていて、その結果書いたものなのでそう深く考えないでください（）

というか確かにdpテーブルの次元減らせる。。その発想はなかった

2017-06-16

暑い日々AC

※はじめに言っておきますが、皆さんにとってはこの問題は楽勝だというのは知っているので、決してイキリとかそういう風に思わないでください。誰だって自分が解けなかった問題が解けるようになると嬉しいのです。（たとえどんなに簡単な問題であろうと）

感想枠（無駄）

先ほどACしたのですが、泣きそうなくらいうれしかったです。
なぜなら、答えを見ずに最後まで自分で解けたからです（eiyaさんなど他の大先輩からの手は借りさせていただきましたが、直接的な解法は教えてもらってません）

こんなに問題が解けて嬉しいことはなかったので、競技プログラミングのなかで自分にとって最も大きい成功体験だったと思います！

解いている途中は、こんなに時間を無駄にしていいのかとか思っていたのですが、今思えば、そこで解答を見ていた方が時間の無駄だったと思います。

なんか偉そうで申し訳ないのですが、本当に最後まであきらめずに解けて良かったです

はい、偉そうですね（なかったことにしてください）

問題の概要、自分の大まかな考え方

問題の概要

JOI 2012-2013 予選問題４

自分の考え方

大きな方針

DP
その日の最大、最小の派手さを決める
DPの中でもメモ化再帰

注意するべきところ

それぞれの差の最大値を求めていれば、最適解が求まるとは限らない（何枚目かという違いがあるから）
深さ優先探索は価値はあとで足さないとdpテーブルに入れる時に死ぬ

自分の解答、および方法

Submission #1356472 - 第１２回日本情報オリンピック予選（オンライン） | AtCoder

変数の説明

d←日にち　　k←服の枚数
maxi,mini←その日に着れる服の派手さの最大値、最小値
dp←dpテーブル
n←何日目かを表す
previous前日の値を入れる

関数DP内の説明および罠

もしn==dの場合0を返すなので、max[d]とかは関数で用いられないので安心

n==0のとき、最初は一個前との差を比べられないのでpreviousに今の値を入れる

ちなみに、previousに今の値を入れることによって、再帰したとき、n+1となるので前の日の値という風になります

f:id:keidaroo:20170616172149j:plain

手書きですみません。

いろいろ

まず、dpテーブルに計算し終わる前に代入しないこと
dpというのは、基本全探索だっていうことも頭に入れておきます

割と単純なのかもしれないです、ACできて本当に良かったです

keidaroo’s diary

底辺系競プロer