I hadn't been studying for the graduate school to do, but I couldn't solve it almost every day. I want to do my best so that both can be compatible, and as soon as I solve it every day, I will remember to write an article as a review.

Day 4

I solved the ABC172-E that I couldn't pass during the contest. This is a problem of the inclusion principle and was explained in this article.

Day 5

ABC137-D Summer Vacation

Time taken

14 minutes

Consideration

It's a relatively simple problem, so I solved it without much consideration.

The $ i $ day laborer part-time job (hereinafter abbreviated as part-time job) receives the reward $ B \ _i $ after $ A \ _i $ days, so if you do not work part-time before $ MA \ _i $ days, you will receive the reward. I can't. Therefore, the bytes that can work and receive rewards on the $ j $ day are the bytes that can receive the reward within $ M-j $ days. In other words, you can see that ** there are few candidate bytes that can be created in the later days . Therefore, consider the bytes that can be done on the $ M-1 $ day (reward within 1 day), the bytes that can be done on the $ M-2 $ day (reward within 2 days), ... ** Reward If you greedily choose from high-ranking bytes ** ( The basis of reward-related problems is the greedy method! **) You will find that it is good.

Python code

`abc137d.py`


from heapq import *
n,m=map(int,input().split())
#How many days it will take(1-indexed)
ab=[[] for i in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    #Do not exceed
    if a<=m:
        ab[a-1].append(b)
x=[]
l=0
ans=0
for i in range(m-1,-1,-1):
    for j in ab[m-1-i]:
        heappush(x,-j)
        l+=1
    if l:
        l-=1
        ans+=heappop(x)
print(-ans)

Day 6

ABC130-E Common Subsequence

Time taken

I couldn't do it for more than 30 minutes, so commentary AC

Cause of mistake

Index mistakes and common subsequence solutions could not be sorted out.

Consideration

Explanation Although it is AC, it was only a ** mistake in the index **. Python allows negative indexes, so I'd like to get into the habit of checking subscripts.

First of all, you may feel that it is DP-like, but ** common subsequences ** are very difficult to handle. Actually, the problem of the most typical pattern of subsequences is ** LCS (Longest Common Sequence) **, and it is easy to solve this time if you follow a similar policy.

Therefore, the array when used in DP is ** $ dp [i] [j]: = $ (up to $ i $ character ($ S_i $) of S and $ j $ character ($ T_j $) of T). The number of common subsequences that can be created from up to) **. Based on this, in order to consider the transition of DP, we will consider how to determine $ dp [i + 1] [j + 1] $.

I couldn't get the idea of the problem of common subsequences, but it depends on whether ** $ S_ {i + 1} $ and $ T_ {j + 1} $ are included in the common subsequence **. It is easy to understand if you think about it.

(1) When both $ S_ {i + 1} $ and $ T_ {j + 1} $ are included in the common subsequence

The end of the common subsequence must be ** $ S_ {i + 1} = T_ {j + 1} $ from $ S_ {i + 1} $ and $ T_ {j + 1} $ ** , $ Dp [i] [j] $ can be thought of as the common subsequence plus $ S_ {i + 1} (= T_ {j + 1}) $.

(2) When only $ S_ {i + 1} $ is included in the common subsequence

Common subsequences from $ S_ {i + 1} $ and $ T_j $ ($ dp [i + 1] [j] $) to $ S_i $ and common subsequences from $ T_j $ ($ dp) All you have to do is exclude [i] [j] $).

(3) When only $ T_ {j + 1} $ is included in the common subsequence

Common subsequences from $ S_ {i} $ and $ T_ {j + 1} $ ($ dp [i] [j + 1] $) to $ S_i $ and $ T_j $ All you have to do is exclude ($ dp [i] [j] $).

(4) When neither $ S_ {i + 1} $ nor $ T_ {j + 1} $ is included in the common subsequence

Consider the common subsequence ($ dp [i] [j] $) that starts from $ S_ {i} $ and $ T_ {j + 1} $.

From the above,

dp[i+1][j+1] = \left\{
\begin{array}{ll}
dp[i][j]+(dp[i+1][j]-dp[i][j])+(dp[i][j+1]-dp[i][j])+dp[i][j]=dp[i+1][j]+dp[i][j+1](S_{i+1}=T_{j+1})\\
(dp[i+1][j]-dp[i][j])+(dp[i][j+1]-dp[i][j])+dp[i][j]=dp[i+1][j]+dp[i][j+1]-dp[i][j](S_{i+1} \neq T_{j+1})
\end{array}
\right.

It will be.

Also, $ dp [i] [0], dp [0] [j] \ (i = 0 $ ~ $ N, j = 0 $ ~ $ M) $ has ** only an empty string as a common subsequence * * So it can be initialized as 1.

With the above, the answer can be obtained by determining $ S_i $ and $ T_j $ in order by a two-dimensional loop. You also need to divide by $ 10 ^ 9 + 7 $.

Python code

`abc130e.py`


mod=10**9+7
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
for i in range(m+1):
    dp[0][i]=1
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1])%mod
        else:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
print(dp[n][m])

Day 7

ABC131-E Friendships

Time taken

It took more than 40 minutes and I couldn't AC, so I explained AC

Cause of mistake

I couldn't sort out the typical patterns of graph construction.

Consideration

** For the time being, I decided to draw various graphs and search for them discoverably **, but I couldn't easily construct the logic. As a result of the experiment, when there are edges between all the vertices, the number of vertex pairs whose shortest distance is 2 is 0, so the number of vertex pairs whose shortest distance is 2 by reducing the edges one by one. I tried to find a way to increase one by one. Also, at this time, I didn't realize that a concatenated graph requires at least $ N-1 $ edges, but ** I got lost **.

(The following is a consideration after seeing the explanation etc.)

First of all, it seems that it is easy to make a policy that ** in a construction problem where the minimum case and the maximum case are decided, the minimum case and the maximum case are considered and it can be configured well between them **. In other words, if there are edges between all the vertices, K will be the minimum (0), so consider the case where it is the maximum.

Here, ** concatenated graphs require $ N-1 $ edges and the shortest distance between the vertices is 1 **, so $ K> \ frac {N (N-1)} {2 }-(N-1) = \ frac {(N-1) (N-2)} {2} $ Concatenated graphs cannot be constructed. Therefore, it is expected that $ K $ will be the maximum at ** $ K = \ frac {(N-1) (N-2)} {2} $ . Here, considering a graph (star graph) that has an edge between vertex 1 and any other vertex, between any two vertices other than vertex 1 ($ \ frac {{(N-1)} {(N) -2)}} {2} $ The shortest distance is 2 and you can construct a concatenated graph that satisfies $ K $ ( Shortest to increase the distance between vertices where the shortest distance is 2) It may be easier to think of it as ** eliminating the distance between vertices with a distance greater than 3.).

Then, ** consider increasing the edges one by one from the star graph and decreasing the vertices with the shortest distance of 2 one by one , but by connecting the edges between two vertices that are not connected by the edges () You can reduce the distance between the vertices by one without affecting the shortest distance between the other vertices **). Also, the reason why it does not affect the distance between the other two vertices is that the shortest distance between the two vertices is 1 or 2 in the graph with some edges added to the star graph, so the change in the shortest distance is 2 when the edges are added. Because there is only one from.

From the above, the graph of the subject is constructed by performing the operation of increasing the edges by $ \ frac {{(N-1)} \ times {(N-2)}} {2} -k $ times from the state of the star graph. can.

In addition, ** it seems better to remember typical graphs that have distinctive shapes when building graphs **. The following three are especially famous.

Python code

`abc131e.py`


n,k=map(int,input().split())
if k>(n-1)*n//2-(n-1):
    print(-1)
else:
    ans=[(1,i) for i in range(2,n+1)]
    lestnum=(n-1)*n//2-(n-1)-k
    for i in range(2,n):
        for j in range(i+1,n+1):
            if lestnum!=0:
                ans.append((i,j))
                lestnum-=1
    print(len(ans))
    for i in ans:
        print(" ".join(map(str,i)))

8th day

I couldn't do it because I had a lot of classes and it was full from the morning. I will not do it in the future.

Day 9

I told him not to do it, but I missed the timing to do it because I was too particular about the issues.

Day 10

ABC134-E Sequence Decomposing

Time taken

I don't think it's bad for about 30 minutes.

Consideration

It is quite difficult to prove it as the answer says, but I think it is not so difficult to solve it with a reasonable policy.

First, consider painting $ A \ i $ in order from the smallest $ i $, but when it becomes $ A \ i \ geqq A \ j (i <j) $, you cannot paint the same color. You need to paint with a new color. Now, paint up to $ A_i $ with $ k $ color, ** to think about which color to repaint next **, the maximum number of $ A_1 $ ~ $ A_i $ for each color ($ \ leftrightarrow $) Save the last number) (colors). At this time, if there is no number smaller than $ A {i + 1} $ in colors, $ A {i + 1} $ is inserted in colors as the number to be painted with a new color. Conversely, if there is a number smaller than $ A {i + 1} $ in colors, rewrite the largest number in it (remove that number from colors and then $ A_ {i + It's easy to see that (inserting 1} $) is optimal ** by considering a counterexample **.

Also, to find a number smaller than 〇〇, it must be ** sorted **, ** insert and delete must be done at high speed **, and ** elements with the same value may exist *. If you also consider *, you can see that ** colors should use multiset **. Also, numbers smaller than XX can be rephrased as to the left of numbers greater than XX (lower \ _bound) when sorted in ascending order. In addition, it should be noted that it is necessary to ** specify it with an iterator ** because it is possible to delete multiple elements if it is specified by a value when performing erase.

C ++ code

`abc134e.cc`


//For compiler optimization
#pragma GCC optimize("O3")
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array

using namespace std;
typedef long long ll;

//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() //I want to omit arguments such as sort
#define SIZE(x) ll(x.size()) //size to size_Change from t to ll
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
#define Umap unordered_map
#define Uset unordered_set

signed main(){
    ll n;cin>>n;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    multiset<ll> colors;
    colors.insert(a[0]);
    FOR(i,1,n-1){
        auto ne=colors.lower_bound(a[i]);
        if(ne==colors.begin()){
            colors.insert(a[i]);
        }else{
            colors.erase(--ne);
            colors.insert(a[i]);
        }
    }
    cout<<SIZE(colors)<<endl;
}

[PYTHON] Competitive professional devotion diary 4th to 10th days (6/28 to 7/4)

Day 4

Day 5

Time taken

Consideration

abc137d.py

Day 6

Time taken

Cause of mistake

Consideration

abc130e.py

Day 7

Time taken

Cause of mistake

Consideration

abc131e.py

8th day

Day 9

Day 10

Time taken

Consideration

abc134e.cc

`abc137d.py`

`abc130e.py`

`abc131e.py`

`abc134e.cc`