はまやんはまやんはまやん

hamayanhamayan's blog

Count Arrays [CSAcademy #65 D]

https://csacademy.com/contest/round-65/task/count-arrays/

Q個の区間がある。
i番目の区間は[L[i],R[i]]の区間に少なくとも1つは0が含まれるという条件。
全ての区間の条件をみたす長さNのバイナリ列は何通りあるか。
※バイナリ列 : 0と1からなる文字列

続きを読む

Count 4-cycles [CSAcademy #65 B]

https://csacademy.com/contest/round-65/task/count-4-cycles/

2つのN頂点の木がある。
それぞれの木の同じ頂点間に辺を追加で張り、2つの木を合成する。
この無向グラフの中で長さ4のサイクルの個数を答えよ。

続きを読む

Parititon the numbers [CodeChef January Challenge 2018 E]

https://www.codechef.com/JAN18/problems/PRTITION

1~Nの数が1つずつある。
この中でxだけ除外する。
残った数を2グループに分け、各グループの総和が等しくなるように出来るか求めよ。
等しく出来ないならImpossible、出来るなら、どのように分けるかを示せ。
テストケース数は最大10^5

続きを読む

String Merging [CodeChef January Challenge 2018 D]

https://www.codechef.com/JAN18/problems/STRMRG

N要素の文字列A、M要素の文字列Bがある。
これをマージして文字列Cを作る。
マージルール

  • AとBから全ての文字を使う
  • Aの文字列の順番、Bの文字列の順番は崩さすマージする

 
関数Fを用意する
F(S) := 文字列Sの中で文字が同じ隣接する文字を1つと考えた時のグループ数
F("aaabbbaa") = 3 (aのグループ,bのグループ,aのグループで3つ)
F("abcabc") = 6
F("aabbccab") = 5
 
作れる文字列Cの中でのF(C)の最小値は?

続きを読む

K-Concatenation [CodeChef January Challenge 2018 C]

https://www.codechef.com/JAN18/problems/KCON

N要素の配列Aがある。
これをK個繋げたNK要素の配列をBとする。
配列Bの連続部分列の中での総和の最大値は?

続きを読む

Maximum Score [CodeChef January Challenge 2018 B]

https://www.codechef.com/JAN18/problems/MAXSC

N*N要素の行列Aがある。
各行から数を1つずつ選んで数列Eを作る。
数列Eを狭義単調増加するように選ぶとき、数列Eの総和の最大値は何か。
もし、狭義単調増加するように取れないなら-1を出力する。

続きを読む

Rectangle [CodeChef January Challenge 2018 A]

https://www.codechef.com/JAN18/problems/RECTANGL
長さa,b,c,dが与えられる。
この長さを全て使って長方形が作れるか判定せよ。

続きを読む