忍者ブログ
  • 2019.09
  • 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
  • 2019.11
XORとは
えっ、そこ?みたいな観点でつづっていきたいと思わなくもないこともない
nwpfhがお送りするブログです。
PR
【2030/12/31 23:59 】 | 未選択
                                    
AGC039 Graph partitionを解いてみた
AGC039に参加して問題Bが解けなかったのだけども、解き方が分かったので解説

問題としては、同じVnに辺があってはいけないというもの。

幅優先探索法で、既に探索済みのノードに出会った場合、次のレベルか前のレベルかしかないということに気づけば後はもっとも長いパスを見つければOK


うーん、時間中には思いつかん。。。
【2019/10/06 20:17 】 | atcoder | 有り難いご意見(0)
                                    
赤黒木をgoで実装してみた
作ったのはこちら
https://github.com/doshiraki/rbtree_bygo/blob/master/rbtree.go


赤黒木

やっぱり削除は難しい。。。
ポイントは、delete case 3,4がまったく同じ結果というようにまとめられること。
	Node := delNode
	for {
		parent := Node.parent
		if parent == nil {
			//case 1
			break
		}

		dir := Node.dir()
		dirOther := dir ^ 1
		sibling := parent.children[dirOther]

		if sibling.isRed {
			//case 2
			parent.flip(dirOther)
			sibling.isRed = false
			parent.isRed = true
			sibling = parent.children[dirOther]
		}
		//sibling is Black

		nephew := sibling.children[dirOther]
		if nephew == nil || !nephew.isRed {
			//far nephew is Black
			nephew = sibling.children[dir]
			if nephew == nil || !nephew.isRed {
				//near nephew is Black
				sibling.isRed = true
				if parent.isRed {
					//case 4
					parent.isRed = false
					break
				} else {
					//case 3
					Node = parent
					continue
				}
			}
			//case 5
			//near nephew is Red and far nephew is Black
			sibling.flip(dir)
			sibling, nephew = nephew, sibling
			sibling.isRed = false
			nephew.isRed = true
		}
		//case 6
		//sibling is Black && far nephew is Red

		saveColor := parent.isRed
		parent.flip(dirOther)
		sibling.isRed = saveColor
		parent.isRed = false
		nephew.isRed = false
		break

	}

【2019/09/23 10:24 】 | go | 有り難いご意見(3)
                                    
KMPアルゴリズム
atcoder141Eを解いていたら良い方法が思い浮かばず、解説読んでKMPアルゴリズムを知った。

E - Who Says a Pun?


KMP法(by wikipedia)
これの面白いところは、BM法と違いは何文字一致したかまで確認出きるという点かな。
勉強になったなり。
ちなみに、解説にはZアルゴリズムとあったのだけども、すべての部分文字列について知りたいわけではないので、KMPのテーブル生成のみに着目したほうがパフォーマンスは良さげ。
しゃくとり法を使うともっとシンプルに解けていることが衝撃である。
【2019/09/16 18:44 】 | atcoder | 有り難いご意見(0)
                                    
javascriptのflatMapとpythonの内包表記
javaでflatMapを覚えてから奇妙だなと思っていた。
これって何に使うのだろうかと。

結論から言うと直積を求めたいときに使うのである。

もし、組み合わせを求めたい場合、どのように求めるだろうか。

■pythonソース
teams = range(5)
[(x, y) for xi, x in enumerate(teams) for yi, y in enumerate(teams) if xi < yi]
■python結果
[(0, 1),
 (0, 2),
 (0, 3),
 (0, 4),
 (1, 2),
 (1, 3),
 (1, 4),
 (2, 3),
 (2, 4),
 (3, 4)]

実はこれと同じことをflatMapでも行える。
■javascriptソース
range = (x)=>function*(){ for(var i = 0;i<x;i++) {yield i;}};
teams = range(5);
Array.from([[]])
.flatMap(x=>Array.from(teams()).map(y=>x.concat(y)))
.flatMap((x, xi)=>Array.from(teams()).filter((y,yi)=>xi<yi).map(y=>x.concat(y)))
■javascript結果
(10) [Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2)]
0: (2) [0, 1]
1: (2) [0, 2]
2: (2) [0, 3]
3: (2) [0, 4]
4: (2) [1, 2]
5: (2) [1, 3]
6: (2) [1, 4]
7: (2) [2, 3]
8: (2) [2, 4]
9: (2) [3, 4]
length: 10
__proto__: Array(0)
おもしろいなあ。
【2019/06/16 18:19 】 | Python | 有り難いご意見(0)
                                    
| ホーム | 次ページ>>