2018-06-02

CSAcademy Subarray Partition

csacademy

＜問題＞
長さ $N$ の配列 $A$ が与えられる。
$A$ を、同じ数は全て１つの連続する部分列に含まれるように分けるとき、最大でいくつに分割できるか。
(たとえば5が $A$ の 5,9, 12番目に含まれるとすると少なくとも5~12番目を１つの部分列に含める必要がある。)

＜解説＞
事前にmap[ $i$ ]で $i$ の現れる最大のindexを指すようにmapを構築します。
$i(0<=i<=N-1)$ を調べながら、それまで出てきた最大のmap[ $i$ ]を持ち、
$i==index$ になれば(現在までの数が全て含まれている)答えを１インクリメントしていきます。

＜コード＞

int main() {

	int n;
	cin >> n;
	vi a(n);
	rep(i, n)cin >> a[i];

	map<int, int> m;
	rep(i, n) {
		m[a[i]] = i;
	}

	int ans = 0;

	int max_i = 0;

	rep(i, n) {
		max_i = max(max_i,m[a[i]]);
		if (i == max_i) {
			ans++;
		}
	}
	P(ans);
	return 0;
}

＜感想＞
問題文と公式解説（こっちは理解していない）が難しかった。

2018-05-29

CSAcademy Equal Sums

csacademy

csacademy.com

＜問題＞
$N × N$ の行列 $A$ が与えられる。
$A_{ij}$ に1加えるという操作を考えるとき
$A$ のすべての行の和・列の和を等しくするとき、
操作は最低何回必要か。

＜解説＞
元の[tex : A]の行の和・列の和の最大値を $A_{max}$ とするとき、
すべての行の和・列の和を $A_{max}$ にすればよいです。（シミュレーション）
(時間が遅いので証明はTODOとさせてください。。。)

特に難しいことはないですが、
$A_{ij}$ に足す値は $i$ 行目の和と $j$ 列目の和を考える必要がありますが、
毎回計算していてはTLEしてしまうので、事前に行・列の和を計算しておき、
$A_{ij}$ の更新とともに、更新しましょう。

＜コード＞

int a[1005][1005];
int main() {

	int n;
	cin >> n;
	rep(i, n)rep(j, n)cin >> a[i][j];

	int maxa = 0;
	rep(i, n) {
		int tmp = 0;
		rep(j, n)tmp += a[i][j];
		maxa = max(maxa, tmp);
	}
	rep(i, n) {
		int tmp = 0;
		rep(j, n)tmp += a[j][i];
		maxa = max(maxa, tmp);
	}
	int sumr[1005], sumc[1005];
	MS(sumr, 0);
	MS(sumc, 0);
	rep(i, n)rep(j, n) {
		sumr[i] += a[i][j];
		sumc[j] += a[i][j];
	}
	rep(i, n)rep(j, n) {
		int diff = max({ 0,min(maxa-sumr[i],maxa-sumc[j]) });
		a[i][j] += diff;
		sumr[i] += diff;
		sumc[j] += diff;
	}
	rep(i, n) {
		rep(j, n) {
			if (j == n - 1) {
				printf("%d\n",a[i][j]);
			}
			else {
				printf("%d ",a[i][j]);
			}
		}
	}
	return 0;
}

＜感想＞
1000^3ギリギリ通りそうだと思ったけど、普通にTLEでした。

2018-05-27

CSAcademy Prefix Matches

csacademy

csacademy.com

<問題>
長さ $N$ の文字列 $S$ 、サイズ $N-1$ の配列 $A$ , $B$ が与えられます。
$A_i$ は $S$ の $i$ 番目の文字から何文字が $S$ のprefixと一致するかを表します。
$B_i$ は $S$ の $i$ 番目で終わる部分文字列のうち何文字が $S$ のprefixと一致するかを表します。

$A$ が与えられたとき $B$ を答えよ。

＜解説＞
$B$ の更新方法には2種類あります。
１．
$i$ 文字目から $A_i$ 文字が $S$ のprefixと一致するので、 $B[i+A_i-1]=max(B[i+A_i-1],A_i)$ となります。
（Ａから○文字がprefixと一致するなら逆からみても一致します。）

２．
$B_i = max(B_i,B_{i+1}-1)$
（ $i$ から $j$ 文字目が $s$ のprefixと一致しているなら $i$ から $j-1$ 文字目も一致します）

＜コード＞

int main() {

	int n;
	cin >> n;
	vi a(n), b(n);
	for (int i = 1; i < n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i < n; i++) {
		b[i + a[i] - 1] = max(b[i + a[i] - 1], a[i]);
	}

	for (int i = n - 2; i > 0; i--) {
		b[i] = max(b[i],b[i+1]-1);
	}

	for (int i = 1; i < n; i++) {
		if (i != n - 1) {
			cout << b[i] << " ";
		}
		else {
			P(b[i]);
		}
	}

	return 0;
}

＜感想＞
問題文を理解するのに時間がかかった

2018-05-25

CSAcademy Max Substring

csacademy

csacademy.com

＜問題概要＞
文字列 ${S}$ が与えられます。 ${S}$ の連続する部分列のうち、その文字列の出現回数が最大のものを見つける。
ただし、そのような部分列が複数ある場合には、長さが最大のものを、
それでも複数ある場合には辞書順最小のものを答えなさい。

＜解説＞
a~zの26のアルファベットの出現回数のうち、最も多いものを ${MAXCOUNT}$ 回
とすると、答える部分文字列はすべて ${MAXCOUNT}$ 回現れるアルファベットで構成されます。
${MAXCOUNT}$ 回以外の出現回数のアルファベットが含まれていると、部分文字列として出現回数が最大になりません。
また、すべてのアルファベットの出現回数が１の場合は単純に ${S}$ が答えになります。

答えるべき文字列 ${T}$ を探索する方法ですが、 ${T}$ に含まれる文字列はすべての出現場所で ${T}$ を構成している必要があります。
${T}$ の最初のアルファベットを全探索し、各アルファベットごとに、文字列 ${T}$ の2文字目のアルファベットの出現箇所が１文字目の出現箇所に比べて１増加していれば、
２文字の候補を作れます。（すべての出現箇所で連続になっているかどうかチェックします）
同様に３文字目、４文字目と作っていき、それぞれの最大文字数のうち、辞書順最小のものが答えになります。
コードでは ${ d[i][j] }$ でアルファベット $i$ の $j$ 番目の出現場所として、チェックしています。
また、 ${T}$ には同じ文字は出現しないので、 ${O(26*26*len(S))}$ になります。
＜コード＞

int main() {

	string s;
	cin >> s;
	int n = s.length();
	vi d[26];

	rep(i, n) {
		d[s[i] - 'a'].pb(i);
	}

	int max_count = 0;
	rep(i, 26) {
		max_count = max( max_count, (int)d[i].size() );
	}
	if (max_count == 1) {
		P(s);
		return 0;
	}
	string ans="";
	int max_length = -1;
	rep(i, 26) {
		if (d[i].size() != max_count) continue;
		
		int tmp_length = 0;
		while (true) {
			bool ok = true;
			rep(j, max_count - 1) {
				if (d[i][j + 1] + tmp_length >= n || s[d[i][j] + tmp_length] != s[d[i][j + 1] + tmp_length]) {
					ok = false;
					break;
				}
			}
			if (!ok)break;
			if (max_length < tmp_length) {
				max_length = tmp_length;
				ans = s.substr(d[i][0], tmp_length + 1);
			}
			else if (max_length == tmp_length) {
				ans = min(ans, s.substr(d[i][0], tmp_length + 1));
			}
			
			tmp_length++;
		}
	}
	P(ans);

	return 0;
}

＜感想＞
すべての文字列の出現回数が１の場合でハマっていた。。。
解説の日本語が冗長ですみません。

2018-05-23

chmod遅すぎ問題

linux

chmodが遅すぎる問題が発生したので、chmodに関して色々実験
(virtual boxからクリップボード共有ができなかったので、virtual boxで書いてます。すでに重い・・・）

＜環境＞

アーキテクチャ:                      x86_64
CPU 操作モード:                      32-bit, 64-bit
バイト順序:                          Little Endian
CPU:                                 2
オンラインになっている CPU のリスト: 0,1
コアあたりのスレッド数:              1
ソケットあたりのコア数:              2
ソケット数:                          1
NUMA ノード数:                       1
ベンダー ID:                         GenuineIntel
CPU ファミリー:                      6
モデル:                              69
モデル名:                            Intel(R) Core(TM) i7-4510U CPU @ 2.00GHz
ステッピング:                        1
CPU MHz:                             2593.998
BogoMIPS:                            5187.99
ハイパーバイザのベンダー:            KVM
仮想化タイプ:                        完全仮想化
L1d キャッシュ:                      32K
L1i キャッシュ:                      32K
L2 キャッシュ:                       256K
L3 キャッシュ:                       4096K
NUMA ノード 0 CPU:                   0,1

シェルスクリプトの名前が変わらないのは許してください。
まずは普通にfor文書いてみます。

kou6839@kou6839-VirtualBox:~$ cat for.sh 

for i in `seq 10000`
do
	:
done

・計測

kou6839@kou6839-VirtualBox:~$ time ./for.sh 

real	0m0.050s
user	0m0.031s
sys	0m0.016s

普通に早い

・次にtouch 10000回

kou6839@kou6839-VirtualBox:~$ cat for.sh 

for i in `seq 10000`
do
  touch a 
done

計測

kou6839@kou6839-VirtualBox:~$ time ./for.sh 

real	0m10.846s
user	0m6.315s
sys	0m2.582s

まぁまぁ遅い

次にchmod 10000回

kou6839@kou6839-VirtualBox:~$ cat for.sh 
touch a
for i in `seq 10000`
do
  chmod 777 a
done

計測

kou6839@kou6839-VirtualBox:~$ time ./for.sh 

real	0m10.470s
user	0m6.161s
sys	0m2.473s

touchとほぼ同じくらい

次にchmodでモードを変えてるのと変えてないのでは時間がかわるのか実験
ループ回数を半分にして中の処理を2つにしています

kou6839@kou6839-VirtualBox:~$ cat for.sh 
touch a
for i in `seq 5000`
do
  chmod 777 a
  chmod 444 a
done

計測

kou6839@kou6839-VirtualBox:~$ time ./for.sh 

real	0m10.332s
user	0m7.440s
sys	0m3.075s

別に変えても変えてなくても時間は同じっぽい

・次にchmodの引数を複数にするとはやいらしいので、その準備
ファイルa, bのモードを変えます

kou6839@kou6839-VirtualBox:~$ cat for.sh 
touch a
touch b
for i in `seq 5000`
do
  chmod 777 a
  chmod 777 b
done

計測

kou6839@kou6839-VirtualBox:~$ time ./for.sh 

real	0m10.408s
user	0m7.395s
sys	0m3.209s

１個１万回と２個５０００回ずつなのであまりかわりません。

引数を２つにします

kou6839@kou6839-VirtualBox:~$ cat for.sh 
touch a
touch b
for i in `seq 5000`
do
  chmod 777 a b
done

計測

kou6839@kou6839-VirtualBox:~$ time ./for.sh 

real	0m5.311s
user	0m3.700s
sys	0m1.595s

はやい！

最初の２つ(touchや１ファイルのchmod)と比較すると２つのファイルのchmodだと引数に関わりなく、timeコマンドの結果からIO待ちが少ないことがわかります。
さらに、引数を増やすと並列なのかforkが少なくなるのかわからんが、とにかく早い！

5000回chmodすることはないかと思いますが、再帰的に(-R)chmodするときには、使えるかもしれません。
そもそもchmod以外でも使える技なので、使ってみてください！

[参考]
シェルスクリプト高速化のツボ - 新・日々録 by TRASH BOX@Eel

2018-05-19

CSAcademy Lonely Points

csacademy

csacademy.com

<問題概要>

要素数 ${Ｎ}$ の数列 ${A_0,A_1,...A_{N-1} }$ が与えられる。

数列Aは昇順にならんでおり、 ${N}$ 点のx座標を表している。

一度だけ、数列Aの数字１つを選び、好きな座標(数字）に書き換えることができる。

このような操作をし、隣り合った(N-1つ)の座標の差の最大値を最小にしたとき、その値はいくつか。

<解説>

一番差が大きいところに、どこからか数字を持ってきて2つの数字の真ん中に置き、差を半分にします。それと、２番目に大きいものを比較し、大きいほうが答えになります。 (コードではpriority_queueで管理しています)

一番差が大きいもの以外の間においても答えは変わらないので、その必要はありません。

次に、どこから数字を持ってくるのかということを考えますが、両端のどちらか隣との差が大きいほうになります。

端の数字を持ってくる場合は、その隣との座標の差そのものがなくなるため、差の最大値が増えることがありません。

一方、端ではない数字 ${A_i}$ を移動させる際には ${A_{i+1}-A_{i-1}}$ が増加してしまい、移動する際のペナルティが発生します。

後者でも答えに影響がないこともありますが、ペナルティがない方を選んだほうが実装も楽です。

<コード>

int main(){

int n;
cin >> n;
vi a(n);
rep(i, n)cin >> a[i];

//[tex:{A_0}を移動させる場合]
priority_queue<int> pq;
for (int i = 1; i + 1 < n; i++) {
pq.push(a[i + 1] - a[i]);
}
int maxp = pq.top(); pq.pop();
pq.push((maxp + 1) / 2);
int ans = pq.top();

//[tex:{A_{N-1}}を移動させる場合]
pq = priority_queue<int>();
for (int i = 0; i + 1 < n-1; i++) {
pq.push(a[i + 1] - a[i]);
}
maxp = pq.top(); pq.pop();
pq.push((maxp + 1) / 2);
ans = min(ans, pq.top());
P(ans);
return 0;
}

2018-05-13

LPIC レベル2取得

日記

今日の午後にLPIC 202試験に合格したので、LPIC level2取得になりました。

LPIC japanのマイページの履歴によると

2018/2/19 101 score 750

2018/3/4 102 score 740

2018/4/30 201 score 600

と取ってきており、今回

2018/5/13 202 score 680

ということになります。

そもそも、なぜ取ろうと思ったかというと、業務知識獲得のためです。

(正確な名称がわかりませんが、)ナビを動作させるマイコンをlinuxでのtftpブートやnfsマウントなどで起動させる必要があるが、linuxの経験が、scp,コンパイル,ELF実行くらい（研究）しかなかったため、さっぱりわかりませんでした。

毎回毎回ググってやるのも面倒だなと思い、体系立てて勉強できるLPICの受験を決心しました。

ただ、勉強を始めるとオプション暗記ゲーで面倒だな・・・と思ったことも多かったです。

レベル2に関しては、スコアも低く、実際にサーバーを立てたのもDNS,apache,メールサーバーの３つしかありません。。。

ですので、レベル２の一部、実務とは逸れていますが、基本的には勉強してよかった資格だったと思っています。

たとえば、systemdやディレクトリ知識などはとても役立っています。

（ただし、ウチの会社だと試験費・昇給一切出ないので、レベル１レベル２受験料と教材費合わせて８万近く自腹で払ってます！！(-.-)）

最後に、他のサイトでお世話になったので、勉強法をすこし。

すべての試験で、ping-tとスピマスの２つで勉強しました。

割合的には7:3くらいで、問題数が多い分ping-tに時間を割いたと思います。

ping-tに関しては、すぐに答えを見ながら一度すべて金にし、そこからもう２週くりかえしました。（金の問題をALLで解いて銅におちたやつをすべて金に戻すと一周)

１週するのに、５時間はかかったような。

コマ問はなんか、ずれているような気がしたので全くやっていません。

スピマスについては大体３週くらいしました。

こちらは模擬試験はやっていません。

単純に、タブレット（電子書籍）でやると、問題と答えの一門一答がやりづらかったからです。

試験勉強を通してlinuxの知識はやるだけついたのですが、基本的なネットワークの知識が足りないことに気づきました。

ということで、今後の目標は、一度CCNA routing & swithingを取ってからレベル3を取ろうと思います。

頑張って６月中にレベル３まで目指します。

kou6839の日記

c++ 競プロ(特にcsacademy)　linuxについて書きます。普段は自動車屋さんでナビ開発してます。転職先を探しています！！。

CSAcademy Subarray Partition

CSAcademy Equal Sums

CSAcademy Prefix Matches

CSAcademy Max Substring

chmod遅すぎ問題

CSAcademy Lonely Points

LPIC レベル2取得