ABC-374

A

$URL\:\to$ https://atcoder.jp/contests/abc374/tasks/abc374_a

#愚直

s = String().content
YesNo(s[-3:]=="san")

int main(void) {
    string s;
    cin >> s;
    ll l = s.size();
    cout << ((s[l-3]=='s' && s[l-2]=='a' && s[l-1]=='n') ? "Yes" : "No") << endl;

    return 0;
}

解法

$S$ の後ろ $3$ 文字が"san"であるか否かで"Yes" / "No"の判断をする。ここで s[-3:] を s[-3:-1] としていまい、1ペナ

B

$URL\:\to$ https://atcoder.jp/contests/abc374/tasks/abc374_b

#愚直

int main(void) {
    char s[100], t[100];
    scanf("%s\n%s", s, t);
    if (strcmp(s,t)==0) {
        printf("%d\n", 0);
        return 0;
    }
    ll ls = len(s), lt = len(t);
    ll m = min(ls, lt);
    rep(i, 0, m) {
        if (s[i]!=t[i]) {
            printf("%lld\n", i+1);
            return 0;
        }
    }
    return 0;
}

    s = Word().content
    t = Word().content
    if s==t:
        print(0)
        exit(0)
    for i in range(min(len(s), len(t))):
        if s[i]!=t[i]:
            print(i+1)
            exit(0)
  print(min(len(s), len(t))+1)

解法

$S=T \to 0,\;S\ne T\to i\;(\;(S[i]\ne T[i])\;が初めて成立する \;\; \&\& \;\; 1\le i \le 100)$ を出力すればいい。

C

$URL\:\to$ https://atcoder.jp/contests/abc374/tasks/abc374_c

#bit全探索

n = Integer().content
k = IntegerList().content
M = INF
for i in range(2**n):
  asum, bsum = 0, 0
  for j in range(n):
    if ((i>>j) & 1): asum += k[j]
    else: bsum += k[j]
  M = min(M, max(asum, bsum))
print(M)

int main(void) {
    ll n;
    scanf("%lld", &n);

    ll k[n];
    rep(i, 0, n) scanf("%lld", &k[i]);

    ll mt = PINF;
    rep(i, 1, (1<<n)-1) {
        ll as = 0, bs = 0;
        rep(j, 0, n) {
            if (i>>j & 1) as += k[j];
            else bs += k[j];
        }
        mt = min(mt, max(as, bs));
    }
    cout << mt << endl;

    return 0;
}

解法

$k[i]$ を $A,B$ どちらに振り分けるのかは $2^{n}$ 通りあり、また $2^{20} \lt 10^9$ なので、bit全探索が使用可能かもと考え、実装する。 $0\to A,\;1\to B$ とし、それぞれの振り分け方での $max(\sum\limits{A},\;\sum\limits{B})$ の $min$ を求めればよい。今回の問題では $len(A)\ne0 \;\;\&\;\; len(B)\ne0$ なので厳密な分け方は $2^{n}-2$ であるが、 $2^{n}$ で解答を求めても問題はない。

D

$URL\:\to$ https://atcoder.jp/contests/abc374/tasks/abc374_d

#bit全探索 #順列全探索

def d(a,b):
    return ((b[0]-a[0])**2+(b[1]-a[1])**2)**0.5

def calc(a, b, cN):
    return (a,d1,b) if (d1:=(cN[0]-a[0])**2+(cN[1]-a[1])**2) < (d2:=(cN[0]-b[0])**2+(cN[1]-b[1])**2) else (b,d2,a)

def solve():
    n,s,t = Integer().content
    lines = [IntegerList().content for _ in range(n)]
    anstime = INF

    # bit全探索
    for bit in range(2**n):

        # 順列全探索
        for pmt in list(permutations(range(n))):
            tmptime = 0
            cn = (0,0)
            for i in range(n):
                nn = lines[pmt[i]]
                S,D,F = calc(nn[0:1+1], nn[2:3+1], cn)
                if (bit>>i & 1)==1:
                    tmptime += d(S,cn)/s
                    tmptime += d(F,S)/t
                    cn = F
                else:
                    tmptime += d(F,cn)/s
                    tmptime += d(S,F)/t
                    cn = S
            anstime = min(anstime, tmptime)

    print(anstime)

解法

どの線分から印字していくのかを順列全探索、どちらの点から引き始めるのかをbit全探索で、探索していくと解を求められる。ちなみにPythonで順列や組み合わせを使いたいときはitertoolsのpermutations, combinationなどを使用すると楽。再帰はうんち💩。

E

$URL\:\to$