ABC053 4AC!

競技プログラミングコンテスト3回目。初めて全問解けた!

今回はごりごり実装というよりはじっくり考えることによって非常にシンプルなコードに落とし込めるという感じだった。

それほど新しく得たものはないけど、std::stringの扱い(検索とか)はチェックしといた方がいいなと思った。

 

問題Dをどう解いたか書いとく。

問題文

すぬけくんはカードゲームで遊ぶことにしました。 N 枚からなるカードの山があり、上から i 枚目のカードには整数 Ai が書かれています。

すぬけくんはこのカードの山に対し 0 回以上、以下の操作を行い、残ったカードに書かれた値が互いに異なるようにしたいです。最大で何枚のカードを残すことが可能か求めなさい。なお、N は奇数であり、少なくとも 1 枚のカードを残すことが可能であることが保証されます。

操作:カードの山から任意の 3 枚のカードを抜き出す。抜き出したカードのうち書かれた値が最大であるようなカード 1 枚と最小であるようなカード 1 枚の合計 2 枚を選んで食べる。その後残った 1 枚をカードの山に戻す。

制約

  • 3≦N≦105
  • N は奇数
  • 1≦Ai≦105
  • Ai は整数

最初にソートして数iの枚数niを算出する。

niが3以上の奇数ならそのカードのみ3枚選べば2枚消せる。-2, -2…を繰り返していけるので最終的に1枚に出来る。つまりniが奇数のものは1枚に出来る。

niが偶数のものも-2, -2を繰り返して2枚まで減らせる。2枚にしたら、その2枚と他の数のカード1枚を消して1枚消せる。つまりniが偶数のものが2つあれば両方を奇数に出来るので偶数ペアも1枚に出来る。

最後に偶数枚のカードがペアにならずに残っていたら1枚になっているカードを犠牲にして消さざるを得ない。

まあこういう感じの考え方。

 

ひとつ収穫があった。

数列中に含まれる各数の個数をカウントするときに数列をソートしてやったんだけど、他の人のコードをみたら

count[10001]={0}を用意して数列を走査しながらcount[n]++を繰り返してた。

なるほど、数列に現れる数の上限が小さければこういうことが出来るのか。

業務ではあんまりこういうことはしないよなー。

ジャジャガッチ | C/C++ | 23:21 | comments(0) | trackbacks(0) |

sphinxいいよ

アルゴリズムについてまとめるためsphinxを使ってwebサイトを作ったわけだが、sphinxいいよ。

書くのにそれほど覚えることはないし、数式もシンタックスハイライトもいける。

cuiで完結するのもいい。軽い。

ソースコードもドキュメント中にコピペしたわけではなく、別ディレクトリにあるcppファイル名を指定して表示している。

このおかげでcppソースを変更してもmake htmlしなおせばhtmlの方も変更が同期される。

図の挿入が面倒くさそうなので、図がいっぱいの文書には不向きかもしれないが、テキストメインの技術文書には使いやすいんじゃないかな。

ジャジャガッチ | Linux | 23:42 | comments(0) | trackbacks(0) |

アルゴリズムをまとめたwebサイトを作りたい

競技プログラミングでよく使うアルゴリズムをまとめたwebサイトを作りたい。

問題を解く時や、仕事で必要なときに適宜このブログを参照しているが、自分の知りたい情報を得るのに時間がかかる。

そこでもう少しちゃんとした技術文書として新しくwebサイトを作りたい。

シンタックスハイライトもちゃんとしてくれてlatexによる数式表示もサポートしてるようなものないかなー、と探してみたら、あった!

その名もSphinx。

 

とりあえずインストールする。

pipというツールでインストールするのが楽だ。新しめpythonには同梱されているらしいのでまずは最新のpythonをインストールする。

あ、ちなみに環境はCentOS7ね。

 

python3.6.0落としてきて、

./configure -> make -> make install

でpythonをインストール。

 

sphinxは

pip3.6 install sphinx

でok。

 

数式のため

yum install *tex*

でtex関連片っ端からインストール。

 

文書作成のためにはまず

sphinx-quichstartを実行して適当に質問に答えていけば雛形が作られる。

数式表示のためにはconf.pyで

extensions += ['sphinx.ext.mathjax']

と記述すればOK。

 

公開する手段は色々あるが、今回はお手軽そうなGitHubを利用した方法を採用する。

手順は次の通り。

まずhithubにユーザ名.github.ioというレポジトリを作成する。

次にlocalで生成したhtml群をgit addする。(htmlのあるところでgit add . でok)

.nojekyllという空ファイルを作成し、git add する。

git remote add origin ***.git

でリモートリポジトリにoriginという名前をつけて

git push origin master

でリモートにpushする。

これでhttp://ユーザ名.github.ioに公開される。

ほい===> https://jajagacchi.github.io/index.html

 

ジャジャガッチ | Linux | 22:27 | comments(0) | trackbacks(0) |

ABC052-C Factors of Factorial

ABC052も参加出来ました!

前回と同じくA, B, Cは出来たけどDは出来なかった。

これが今の実力か。

Cは勉強した剰余計算が大いに役に立った!

問題文

整数 N が与えられます。 N! の正の約数の個数を 109+7 で割った余りを求めてください。

 

次のようにすればOK。

例えば6!なら素因数分解すると2が4個、3が2個、5が1個出て来る。これらを使うか使わないかの組み合わせで5×3×2通りの約数がある。

さて、問題は素因数分解したことがないということだ。

ぐぐってみると、効率は悪いが試し割りという方法がシンプルでよさげ。Nも最大1000とさして大きくないし。

#include <iostream>
#include <vector>
const int MOD = 1000000007;

void countPN(int n, std::vector<int> &count)//nを素因数に分解し、countを更新
{
	int m = n;
	for(int i=2 ; i*i<=n ; ++i)
	{
		while(m%i == 0)
		{
			m /= i;
			count[i]++;
		}
		if(m==1) break;
	}
	if(m!=1) count[m]++;

}

int main()
{
	int N; std::cin >> N;
	std::vector<int> count(1024);
	for(auto &x : count) x = 0;
	for(int n=2; n<=N; n++) countPN(n, count);

	long long ans = 1;
	for(int n=2; n<=N; n++)
	{
		if(count[n] != 0)
		{
			ans *= count[n]+1;
			ans %= MOD;
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

ほれ、剰余計算もばっちしじゃ!

素因数分解とか約数の列挙とか素数の列挙とか抑えとかないかんかな。

ジャジャガッチ | C/C++ | 23:23 | comments(0) | trackbacks(0) |

ABC046-C AtCoDeerくんと選挙速報

それほど難しくはないんだけど細かいところで詰まった。

それは切り上げ処理。

ceil((double)a/b);
a/b + (a%b==0 ? 0 : 1);

最初は前者でサブミットしたんだけど、一部でWAとなる。

誤差が生じないように後者の方法を使えばok。

ジャジャガッチ | C/C++ | 23:11 | comments(0) | trackbacks(0) |

ABC048-C Boxes and Candies

問題文

N 個の箱が横一列に並んでいます。 最初、左から i 番目の箱には ai 個のキャンディが入っています。

すぬけ君は次の操作を好きな回数だけ行うことができます。

  • キャンディが 1 個以上入っている箱をひとつ選び、その箱のキャンディを 1 個食べる。

すぬけ君の目標は次の通りです。

  • どの隣り合う 2 つの箱を見ても、それらの箱に入っているキャンディの個数の総和が x 以下である。

目標を達成するために必要な操作回数の最小値を求めてください。

 

まず、どの箱もx以下になる必要があるので、とりあえずそれをしてしまう。

その後が問題。

真ん中から考えると難しいので端から小問題を順次解く感じでできないかなと考えてみる。

左端二つに注目する。もしこれらの和がxよりも大きいならキャンディを食べる必要があるが、左を食べるよりも右を食べるほうがいい。右を食べておけばその右の箱との和が有利になるから。なので右の箱を食べて条件を満たすようにする。これを繰り返せばok。貪欲法というやつか。

#include <iostream>
#include <vector>

int main()
{
	int N; std::cin >> N;
	int x; std::cin >> x;
	std::vector<int> a(N);
	for(auto &z : a) std::cin >> z;

	long long ans = 0;
	for(auto &z : a)
	{
		if(z > x)
		{
			ans += z-x;
			z -= z-x;
		}
	}
	for(int n=0; n<N-1; n++)//n:端の番号
	{
		int sum = a[n] + a[n+1];
		if(sum > x)
		{
			ans += sum-x;
			a[n+1] -= sum-x;
		}
	}
	std::cout << ans << std::endl;

	return 0;
}

 

ジャジャガッチ | C/C++ | 12:42 | comments(0) | trackbacks(0) |

ABC049-C 白昼夢

これから解いた問題全ての解答を上げるのは面倒くさいので、お、というものだけ上げていきます。

しばらくはABCのC問題を埋めていくか。

アルゴリズムの基礎が問われるレベルらしいし、やってみた感じ今の僕にちょうどいい感じ。

ちょっと考えればそんなに難しくはないけど、どの問題も何かしら経験値が溜まる感じ。

 

問題文

英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。

  • T の末尾に dream dreamer erase eraser のいずれかを追加する。

 

前から探索すると、例えばdreamなのかdreamerなのか判別するのが難しいけど、後ろからやれば簡単。後ろからやれば後ろ3文字で判別できる。判別できたら文字列から除いてやればok。

#include <iostream>
#include <string>

int main()
{
	std::string str; std::cin >> str;
	std::string ans("YES");
	while(!str.empty())
	{
		if(str.size() < 5)
		{
			ans = "NO";
			break;
		}
		std::string s = str.substr(str.size()-3);
		if(s=="eam")//dream
		{
			if(str.substr(str.size()-5)=="dream") str.erase(str.size()-5, 5);
			else
			{
				ans = "NO";
				break;
			}
		}
		else if(s=="mer")//dreamer
		{
			if(str.size() < 7)
			{
				ans = "NO";
				break;
			}
			if(str.substr(str.size()-7)=="dreamer") str.erase(str.size()-7, 7);
			else
			{
				ans = "NO";
				break;
			}
		}
		else if(s=="ase")//erase
		{
			if(str.substr(str.size()-5)=="erase") str.erase(str.size()-5, 5);
			else
			{
				ans = "NO";
				break;
			}
		}
		else if(s=="ser")//eraser
		{
			if(str.size() < 6)
			{
				ans = "NO";
				break;
			}
			if(str.substr(str.size()-6)=="eraser") str.erase(str.size()-6, 6);
			else
			{
				ans = "NO";
				break;
			}
		}
		else
		{
			ans = "NO";
			break;
		}
	}
	std::cout << ans << std::endl;
	return 0;
}
前からが難しければ後ろからね。
ジャジャガッチ | C/C++ | 12:37 | comments(0) | trackbacks(0) |

剰余演算練習

atcoderのとある問題がきっかけで剰余演算を勉強することになったわけだが、その問題では2^{N/2}を10^9+7で割った余りが必要になった。

剰余演算部分のコードは次の通り。

	long long ans = 1;
	for(int i=0; i<N/2; i++)
	{
		ans *= 2;
		ans %= 1000000007;
	}
	std::cout << ans << std::endl;
ジャジャガッチ | C/C++ | 22:39 | comments(0) | trackbacks(0) |

剰余演算

競技プログラミングの問題見てると時々解が非常に大きな数になるためある数の剰余を出力せよ、という形式のものがある。

これまではこりゃ無理だと思ってスルーしてたのだが挑戦してみた。

剰余演算と呼ばれるものの知識がいるらしい。

剰余演算の性質はwikipediaの剰余演算の項にまとまっている。

 

剰余演算の世界における積、和の性質を見てみる。

なお、数学ではa mod pと書いてaをpで割った時の余りと定義するようだが、なじまないのでC言語風にa%pと書くことにする。

 

(a%p)%p = a%p

(ab)%p = {(a%p)×(b%p)}%p = {(a%p)×b}%p

(a+b)%p = {(a%p)+(b%p)}%p = {(a%p)+b}%p

 

%p%p=%pのように考えて%pをくくり出しているようにみれば覚えやすいかな。

これが基本であるが、積、和が3つ以上になる場合は注意。

(abc)%p = {(ab)%p×(c%p)}%p = {(ab)%p×c}%p = [{(a%p)×b}%p×c]%p

のようになる。aの剰余をとる→bを掛けて更に剰余をとる→cをかけて更に剰余をとる、の手順でok。4つ以上も同じ。

 

aの逆元は

{(a%p)(b%p)}%p = 1%p

を満すbとして定義される。

逆元を使って

(a/b)%p = {(a%p)×(b^-1%p)}%p

が成り立つ。

逆元はフェルマーの小定理を使って計算できる。

a^{p-1}%p = 1%pよりaa^{p-2}%p = 1%pであるため

a^-1%p = a^{p-2}%p

となる。すなわち、

(a/b)%p = {(a%p)×(b^-1%p)}%p = {(a%p)×(b^{p-2})%p}%p

と積に帰着する。

例えば

(143/13)%7 = (143*13^5)%7

となるわけである。

ジャジャガッチ | C/C++ | 22:35 | comments(0) | trackbacks(0) |

yukicoder No47

 

元ネタと思われる童謡の歌詞では叩いた回数分と同じだけ増えるらしい。元ネタの方が問題としてははるかに簡単だ。

コレ面白い。面白いのでネタバレを避けるため解説は続きに書く。

続きを読む >>
ジャジャガッチ | C/C++ | 22:27 | comments(0) | trackbacks(0) |
1/3PAGES | >> |

01
--
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
--
>>
<<
--
PR
RECOMMEND
RECENT COMMENT
MOBILE
qrcode
OTHERS
Since 2013/09/17
LATEST ENTRY
CATEGORY
ARCHIVE
LINKS
PROFILE
SEARCH