AtCoder Beginner Contest 173 振り返り

B - Judge Status Summary

正）AC x 10

誤）AC × 10

良い子のみんなはちゃんと文字を確認しような！

そもそもデフォルトの掛け算記号は＊なのだから気づくべき

C - H and V

H×Wの行列がある．列あるいは行を選んで塗りつぶすことで，#の数をK個にする．

方針：

最大でも2^6*2^6の4096通りなので，itertools.combinationsで気軽に全探索

    ans = 0

    for i in range(H+1):

        for j in range(W+1):

            for n in itertools.combinations(list(range(H)),i):

                for m in itertools.combinations(list(range(W)),j):

                    count = 0

                    for a in n:

                        for b in m:

                            if(C[a][b] == "#"): count +=1

                    if(count == K):

                        ans += 1

Submission #14998600 - AtCoder Beginner Contest 173

E - Multiplication 4

N個の数からK個の数を選び，その積を求める．

もっとも大きい積を10^9 +7で割ったあまりを求めよ．

解法：非負の状態を保ちながら積を最大化

正の数を二個，負の数を二個加えれば，非負の状態を保つことができる．

流れとして，Aを読み込みsort() したのち，

①a. Kが奇数の場合かつ最大値が負の場合

右から順にかけることで絶対値最小の解が出る

①b. Kが奇数の場合かつ最大値が正の場合

最大値をかける．以降，K-1については偶数と同じように扱える

②Kが偶数の場合

並べ替えられたAについて，右側2つと左側2つの積を比べ，大きいほうをかける．

これを K//2 回分行うことで，K個選んだ際の最大の積が求まる．

Submission #15061788 - AtCoder Beginner Contest 173

別解：最後に符号を合わせる

絶対値の順にソートして，大きい順にかけた後，負であれば

・正の数を一つ除き，負の数を一つ加える

・負の数を一つ除き，正の数を一つ加える

取り除く要素はなるべく小さく，加える数はなるべく大きいほうが良い．

片方の操作しかできない場合に注意．

 F - Intervals on Tree

N頂点からなる木を描き，1≦L≦R≦Nとする

L以上R以下の頂点からなるSについて，部分グラフがいくつあるかを f(L,R)とする．

これをすべてのL, Rについて足し上げる．

解法：各辺が何回数えられるかを考えれば良い．

選び方は最大で N * (N+1) * (N+2) // 6

各辺（u,v） (u < v) が選ばれるごとに，u以下のLとv以上のRに影響

1回ごとに，u*(N - v+1)を引けばよい

Submission #15090381 - AtCoder Beginner Contest 173