問題概要 アルファベットからなる文字列を'A'→1、'B'→2、……、'Z'→26のように数字に置換し、それを並べてエンコードすることを考える。(例:BZ→226) 復号方法は何通りあるのか答えよ
解法 セグメント木を永続データー構造化し,その上で二分探索する. 割と遅め. 実装(C++) #include <vector> #include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> using namespace std; struct Persistent_Segtree{ int n; struct Node{ Node *left,*right; int val</cstring></cmath></algorithm></cstdio></iostream></vector>…
問題概要 日本語なので略
問題概要 日本語なので略
問題概要 日本語なので略
解法 枝刈りしつつ全探索する. 実装(C++) #include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <climits> #include <queue> #include <stack> #include <algorithm> #include <list> #include <vector> #include <set> #include <map> #include <iostream> #include <deque> #include <complex> #include …</complex></deque></iostream></map></set></vector></list></algorithm></stack></queue></climits></cstdlib></cstring></cmath></cstdio>
解法 2次元累積和を用いる.人が住んでいる場所は10^8以上の数字にすればよい. 実装(C++) #include <cstdio> using namespace std; typedef long long lli; const lli INF=1000000001; lli MAP[1000][1000],SUM[1001][1001],_SUM[1001][1001]; int W,H; int a,b; in</cstdio>…
解法 nに√nよりも大きい素因数が含まれていたらそれが解.そうじゃないのならmod n=0になるまで階乗を計算する 実装(C) int n,m,t,mod=1,i; int main(){ scanf("%d",&n); t=n; for(i=2;i*i<=n;i++) while(t%i==0) t/=i; if(t++==1) for(;mod;t++) mod=(long …
解法 ヒストグラムを作り,各点数の順位を求める 実装(C++) #include <cstdio> int n,hist[101],s[100000],res[101]; int main() { scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",s+i); hist[s[i]]++; } for(int i=100,j=1;i>=0;i--){ res[i]=j; j+=hist[i]; } for(int i=0;i</n;i++){></cstdio>
解法 行の開始文字と空行の有無に応じて分岐をする.Javaの場合はStringBuilderを使わないと間に合わない. 実装(Java) import java.util.*; import java.math.*; import java.io.*; import java.util.regex.*; import static java.lang.Math.*; import stat…
問題概要 n人の市民からなる街がある.デモがあり,それが認められるためにはy%の人が参加しないとならない. n人のうちx人がデモに参加するとして,後何人いればデモが認められるか求めよ
問題概要 Σ(i=0…∞) [v/(k^i)]がN以上になるような最小のvを求めよ.
問題概要 論理式が与えられる.この式を満たすような変数の値の組み合わせの数を求めよ.ただし,同じ変数は一度しか表われない.
問題文 Rabbit Plays Games! | Aizu Online Judge
問題概要 悪魔のエディタを作った男が居た.悪魔のエディタは次の独特の機能を持っている. 文字列(空白を持たない連続した文字の並び)の下に何も文字列が無い場合,その文字列は落下する.下に文字列がある状態になるか,一番下に辿り付くまで落下は継続す…
問題概要 木を図示せよ. ただし出来る限りハイフンの数が少なくなるようにすること.
問題概要 x+mk=y+nk (mod L)を満す最小のKを求めよ.存在しない場合"Impossible"って出力せよ.
問題概要 1〜Kの数字を含んだN項の数列が与えられる.数列の部分列とならないような最小の部分列の長さを求めてください.
解法 Σ[0 実装(Ruby) def solve(w,h) w*(w+1)*h*(h+1)/4 end p solve(3,2) x=1 ans=1 max=4000000 target=2000000 loop do break if solve(x,x)>target+(target-ans).abs for y in x..1000000 if (target-solve(x,y)).abs<(target-ans).abs ans=solve(x,y) p…
解法 分割数 - Wikipediaを参考にして漸化式を作りました. 実装(C++) #include <iostream> #include <algorithm> using namespace std; typedef long long lli; const int MOD=1000000; //五角数を求める int pentagonal(int i){ return (i*(3*i-1))/2; } int p_memo[1000000]; i</algorithm></iostream>…
Problem 204 - PukiWiki
練習です. Massive Number(Div2 Easy) 指示通りに比較する class MassiveNumbers { public: typedef pair<int,int> P; P get(string s){ int a,b; sscanf(s.c_str(),"%d^%d",&a,&b); cout<</int,int>
問題 Problem 206 - Project Euler
Problem 172 - PukiWiki
問題概要 N個の数のK番目の順列のうち,以下の条件を両方満たす桁は何桁あるか ・前から見てlucky_numberな番号の桁である ・数値がlucky_numberである
練習として全問解いてみました A問題 大きい順に使っていく貪欲法 k=gets.to_i a=gets.split.map(&:to_i) a=a.sort.reverse t=0 ans=0 a.each{|s| break if t>=k t+=s ans+=1 } ans=-1 if t
問題概要 0と1からなる二つの画像A,Bが与えられる. Bの任意の行と列を消して画像Aが作り出せるかを求めよ.
問題概要 X0=S Xn=(A×Xn-1+B)%C で表わされる数列Xの各Bitについて,0しか取らない,1しか取れない,0と1のどちらも取り得るの3種類のうちどれに当て嵌まるか答えよ.
問題概要 赤,緑,黄色,青のブロックをN個並べたい. ただし,赤と緑は偶数個並べたい. この時並べ方は何通りあるか.
2138 -- Travel Games 問題概要 牛さんが "travel games"というゲームをして遊ぶことにした. "travel games"はある牛が作った単語に一文字足して次の単語を作るということを繰り返していくゲームだ. さて辞書が与えられた時に最も最終結果の単語がながくな…