Language: C++

lccccccc
#9625

tmwilliamlin168Yesterday at 9:29 PM
AtCoder Beginner Contest 160:
tmwilliamlin168Yesterday at 9:40 PM
A:

This should be pretty simple.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;
    cout << (s[2]==s[3]&&s[4]==s[5]?"Yes":"No");
}
B:

We should take as many 500-yen coins as we can, then take 5-yen coins for the rest. Calculate y = number of 500-yen coins and z = leftover yen. We can form z/5 5-yen coins with the leftover yen.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int x;
    cin >> x;
    int y=x/500, z=x%500;
    cout << 1000*y+z/5*5;
}
C:

We can try every starting house.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int k, n;
    cin >> k >> n;
    int a[n];
    for(int i=0; i<n; ++i)
        cin >> a[i];
    int ans=a[n-1]-a[0];
    for(int i=1; i<n; ++i)
        ans=min(a[i-1]+k-a[i], ans);
    cout << ans;
}
D:

The easiest solution (without thinking) would be to run BFS from all nodes. However, this problem can be solved without BFS. We can iterate through all pairs (i, j) and calculate their distance. There are two choices to go from i to j: we can not use the edge x-y (the distance will be j-i), or we can use the edge x-y (the distance will be abs(i-x)+1+abs(j-y)).

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e3;
int n, x, y, ans[mxN];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> x >> y, --x, --y;
    for(int i=0; i<n; ++i) {
        for(int j=i+1; j<n; ++j) {
            int d=min(j-i, abs(i-x)+1+abs(j-y));
            ++ans[d];
        }
    }
    for(int i=1; i<n; ++i)
        cout << ans[i] << "\n";
}
E:

We start by choosing the best x red apples and the best y green apples. While we can still choose a colorless apple, let's choose the biggest one and replace it with the smallest red or green apple (or stop if it doesn't increase the answer).

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int x, y, a, b, c, p[mxN+1], q[mxN+1], r[2*mxN];
ll ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> x >> y >> a >> b >> c;
    for(int i=0; i<a; ++i)
        cin >> p[i];
    sort(p, p+a);
    for(int i=0; i<b; ++i)
        cin >> q[i];
    sort(q, q+b);
    p[a]=q[b]=1e9;
    for(int i=0; i<c; ++i)
        cin >> r[i];
    c=max(x+y, c);
    sort(r, r+c);
    for(int i=0; i<x; ++i)
        ans+=p[a-1-i];
    for(int i=0; i<y; ++i)
        ans+=q[b-1-i];
    for(int i=0, j1=a-x, j2=b-y; i<x+y; ++i) {
        if(r[c-1-i]<=p[j1]&&r[c-1-i]<=q[j2])
            break;
        ans+=r[c-1-i];
        if(p[j1]<q[j2])
            ans-=p[j1++];
        else
            ans-=q[j2++];
    }
    cout << ans;
}
F:

Let's calculate the answer for the root. Let's simulate the process backwards, so we are basically taking a node u which has all nodes in its subtree except for itself numbered, and we will number u. Let's say u has two children v1 and v2, and let s[v] be the size of the subtree of v. We can interleave the ordering for the nodes inside v1 and v2, so dp[u] = dp[v1] * dp[v2] * (s[v1] + s[v2] choose s[v1]). The DP works similarly with more children.

To find the answer for all nodes, we can use the standard DP with rerooting technique.

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5, M=1e9+7;
int n, s[mxN];
vector<int> adj[mxN];
ll iv[mxN], f1[mxN], f2[mxN], dp[mxN], ans[mxN];

void dfs1(int u=0, int p=-1) {
    dp[u]=1;
    for(int v : adj[u]) {
        if(v==p)
            continue;
        dfs1(v, u);
        dp[u]=dp[u]*dp[v]%M*f1[s[u]+s[v]]%M*f2[s[u]]%M*f2[s[v]]%M;
        s[u]+=s[v];
    }
    ++s[u];
}

ll mI(ll a, ll m) {
    return (a%=m)<2?a:(1-mI(m%a, a)*m)/a+m;
}

void dfs2(int u=0, int p=-1, ll pd=1) {
    ans[u]=dp[u]*pd%M*f1[n-1]%M*f2[s[u]-1]%M*f2[n-s[u]]%M;
    for(int v : adj[u]) {
        if(v==p)
            continue;
        dfs2(v, u, ans[u]*mI(dp[v], M)%M*f2[n-1]%M*f1[n-1-s[v]]%M*f1[s[v]]%M);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    iv[1]=1;
    for(int i=2; i<n; ++i)
        iv[i]=M-M/i*iv[M%i]%M;
    f1[0]=f2[0]=1;
    for(int i=1; i<n; ++i) {
        f1[i]=f1[i-1]*i%M;
        f2[i]=f2[i-1]*iv[i]%M;
    }
    for(int i=1, u, v; i<n; ++i) {
        cin >> u >> v, --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1();
    dfs2();
    for(int i=0; i<n; ++i)
        cout << ans[i] << "\n";
}
﻿

Compiler output:
a.cc:9719:121: warning: multi-character literal with 97 characters exceeds 'int' size of 4 bytes
a.cc:9764:4: warning: multi-character literal with 40 characters exceeds 'int' size of 4 bytes
a.cc:9764:204: warning: missing terminating ' character
a.cc:9764:204: error: missing terminating ' character
a.cc:1:1: error: 'lccccccc' does not name a type
    1 | lccccccc
      | ^~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:62,
                 from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:9633:
/usr/include/c++/14/ext/type_traits.h:164:35: error: 'constexpr const bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/14/ext/type_traits.h:159:5: note: previous declaration 'template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)'
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:164:26: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/14/cstddef:50,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:41:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/type_traits:666:33: error: 'nullptr_t' is not a member of 'std'; did you mean 'nullptr_t'?
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:443:29: note: 'nullptr_t' declared here
  443 |   typedef decltype(nullptr) nullptr_t;
      |                             ^~~~~~~~~
/usr/include/c++/14/type_traits:666:42: error: template argument 1 is invalid
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/14/type_traits:670:48: error: template argument 1 is invalid
  670 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/14/type_traits:674:51: error: template argument 1 is invalid
  674 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/14/type_traits:678:57: error: template argument 1 is invalid
  678 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1429:57: error: template argument 1 is invalid
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:57: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1438:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1438:46: error: template argument 1 is invalid
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/14/type_traits:1438:46: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1440:26: error: 'std::size_t' has not been declared
 1440 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:1441:21: error: '_Size' was not declared in this scope
 1441 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/14/type_traits:1441:27: error: template argument 1 is invalid
 1441 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/14/type_traits:1442:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1442:65: error: template argument 1 is invalid
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1442:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1446:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1446:65: error: template argument 1 is invalid
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1446:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:2086:26: error: 'std::size_t' has not been declared
 2086 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2087:30: error: '_Size' was not declared in this scope
 2087 |     struct remove_extent<_Tp[_Size]>
      |                              ^~~~~
/usr/include/c++/14/type_traits:2087:36: error: template argument 1 is invalid
 2087 |     struct remove_extent<_Tp[_Size]>
      |                                    ^
/usr/include/c++/14/type_traits:2099:26: error: 'std::size_t' has not been declared
 2099 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2100:35: error: '_Size' was not declared in this scope
 2100 |     struct remove_all_extents<_Tp[_Size]>
      |                                   ^~~~~
/usr/include/c++/14/type_traits:2100:41: error: template argument 1 is invalid
 2100 |     struct remove_all_extents<_Tp[_Size]>
      |                                         ^
/usr/include/c++/14/type_traits:2171:12: error: 'std::size_t' has not been declared
 2171 |   template<std::size_t _Len>
      |            ^~~
/usr/include/c++/14/type_traits:2176:30: error: '_Len' was not declared in this scope
 2176 |         unsigned char __data[_Len];
      |                              ^~~~
/usr/include/c++/14/type_traits:2194:12: error: 'std::size_t' has not been declared
 2194 |   template<std::size_t _Len, std::size_t _Align =
      |            ^~~
/usr/include/c++/14/type_traits:2194:30: error: 'std::size_t' has not been declared
 2194 |   template<std::size_t _Len, std::size_t _Align =
      |                              ^~~
/usr/include/c++/14/type_traits:2195:55: error: '_Len' was not declared in this scope
 2195 |            __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                       ^~~~
/usr/include/c++/14/type_traits:2195:59: error: template argument 1 is invalid
 2195 |            __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                           ^
/usr/include/c++/14/type_traits:2202:30: error: '_Len' was not declared in this scope
 2202 |         unsigned char __data[_Len];
      |                              ^~~~
/usr/include/c++/14/type_traits:2203:44: error: '_Align' was not declared in this scope
 2203 |         struct __attribute__((__aligned__((_Align)))) { } __align;
      |                                            ^~~~~~
In file included from /usr/include/c++/14/bits/stl_tempbuf.h:59,
                 from /usr/include/c++/14/bits/stl_algo.h:69,
                 from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/new:131:26: error: declaration of 'operator new' as non-function
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:131:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  131 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/new:132:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  132 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/14/new:133:26: error: declaration of 'operator new []' as non-function
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/14/new:133:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  133 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: no