AtCoder ABC 175 Python

Résumé

ABC a été résolu. D et E ont été mis en place en tant que politique, mais ils ne peuvent pas être résolus à temps. Cette fois, j'ai pu réfléchir au problème F pour la première fois (s'il peut ou non être résolu est une autre histoire ...) E a été résolu à une date ultérieure, mais D n'a pas pu écraser WA et n'a pas encore AC.

problème

https://atcoder.jp/contests/abc175

A. Rainy Season

Répondre

S = tuple(input())

if S == ('R', 'R', 'R'):
    print(3)
elif S == ('R', 'R', 'S') or S == ('S', 'R', 'R'):
    print(2)
elif S == ('S', 'S', 'S'):
    print(0)
else:
    print(1)

Je me suis demandé s'il y avait un bon moyen de le résoudre, mais je n'y pensais pas. Je les ai tous énumérés et les ai résolus avec une déclaration if.

Au moment du concours, je l'ai mis dans le tuple, mais vous pouvez juger la chaîne de caractères telle qu'elle est.

B. Making Triangle

Répondre

from itertools import combinations

N = int(input())
L = list(map(int, input().split()))

count = 0
for C in combinations(L, 3):
    l_list = list(C)
    l_list.sort()

    if l_list[2] > l_list[1] and l_list[1] > l_list[0]:
        if l_list[2] < l_list[1] + l_list[0]:
            count += 1

print(count)

Puisqu'il s'agit d'une condition triangulaire, elle peut être résolue par côté maximum <somme des deux autres côtés '' ''. Puisque les restrictions sont petites, je les ai toutes énumérées.

C. Walking Takahashi

Répondre

X, K, D = map(int, input().split())

new_X = abs(X) % D
new_K = K - abs(X) // D

if new_K <= 0:
    answer = abs(X) - K*D
else:
    if new_K % 2 == 0:
        answer = new_X
    else:
        answer = abs(new_X - D)
        
print(answer)

Tout d'abord, je ne veux certainement pas utiliser l'instruction for car les restrictions sont trop strictes. Puisque nous traitons un si grand nombre, nous pouvons nous attendre à ce que le processus de «division d'un grand nombre par un certain nombre» arrive quelque part.

Dans cet esprit, je souhaite diviser les coordonnées X '' par la distance parcourue D '' pour le moment. x // dSi vous pensez à la signification de, vous pouvez voir que c'est "le nombre de déplacements de distance d nécessaire pour parcourir x distance". Quand il s'agit de "nombre de coups", vous voulez soustraire de `` K```.

Ensuite, en expérimentant avec certains échantillons d'entrée, nous constatons que si D est bien au-dessus de X, il vibre près de l'origine. Il s'avère qu'il y a deux réponses à la vibration.

À ce stade, la politique est devenue assez solide.

1. Faites `` K --X // D``` et calculez le nombre de fois restant
2. Puisqu'il vibre près de l'origine, divisez les deux cas et calculez la réponse.
3. Après cela, faites attention au traitement des valeurs positives et négatives, et gérez les exceptions lorsque X est suffisamment plus grand que D.

Déposez ceci dans votre code.

D. Moving Piece

Réponse (c'est la moitié WA)

N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

answer = -float('inf')
for start_p in range(1, N+1):

    cycle_total_score = 0
    cycle_in_score = -float('inf')
    cycle_count = 0
    next_p = P[start_p]
    while True:
        cycle_total_score += C[next_p]
        cycle_in_score = max(cycle_in_score, cycle_total_score)
        cycle_count += 1

        if next_p == start_p:
            # print('start_p:', start_p, ' cycle_total_score:', cycle_total_score, 'cycle_in_score:', cycle_in_score, 'cycle_count:', cycle_count)
            break
        next_p = P[next_p]
    
    max_score = 0
    if K == cycle_count:
        max_score = cycle_in_score
    else:
        #Débordant K% cycle_Trouver max pour ajouter des scores pour compter les temps
        add_max_count = K % cycle_count
        add_total_score = 0
        add_score = -float('inf')
        add_count = 0
        add_next_p = P[start_p]
        while True:
            add_total_score += C[add_next_p]
            add_score = max(add_score, add_total_score)
            add_count += 1

            if add_count == add_max_count:
                break
            add_next_p = P[add_next_p]

        if K < cycle_count:
            #Le nombre maximum d'essais est cycle_K si inférieur à compter% cycle_bec au meilleur endroit pour compter
            max_score = add_total_score
        else:
            if cycle_total_score >= 0:
                #Si un cycle est positif, tournez le cycle autant que possible et K% cycle_bec au meilleur endroit pour compter
                max_score = (K // cycle_count) * cycle_total_score + add_total_score
            else:
                #Si un cycle est négatif, ne pas tourner le cycle, K% cycle_pause au meilleur endroit pour compter
                max_score = add_total_score
    # print('max_score', max_score)
    answer = max(answer, max_score)

print(answer)

Je n'ai pas encore pu obtenir de climatisation. Dans le code ci-dessus, toutes les entrées de test réussissent, mais en production, la moitié est WA. Je pense que l'idée est correcte, mais je n'ai pas été en mesure d'identifier la cause de WA ...

Je ne sais pas ce que je dis si ce ne sont que des lettres, alors je dessine un diagramme. Voici une illustration de l'exemple d'entrée 1.

Compte tenu des caractéristiques de cette figure, nous pouvons voir qu'un ou plusieurs graphiques avec des cycles peuvent être créés. La politique à résoudre est d'essayer honnêtement toute la rue.

1. Décidez d'abord par où commencer => Essayez ceci de N façons
2. Faites un tour depuis le début et enregistrez les scores suivants 2.1. Note totale pour un cycle 2.2. Score au moment maximal d'un cycle 2.3. Nombre de mouvements requis pour un cycle
3. C'est facile si K est un multiple entier du nombre de mouvements dans un cycle, mais il peut y avoir des temps à mi-chemin, donc dans ce cas j'irai chercher le score ci-dessous 3.1. Numéro à mi-chemin 3.2. Score au maximum des numéros à mi-chemin

Cela devrait peut-être le résoudre, mais cela n'a pas été résolu avant la fin (n'est-il pas possible de le résoudre avec ça?)

E. Picking Goods

Réponse (version normale TLE)

R, C, K = map(int, input().split())
scores = [[0] * (C + 1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    scores[r][c] = v
dp = [[[0] *4 for _ in range(C+1)] for _ in range(R+1)]

for i in range(1, R+1):
    for j in range(1, C+1):
        for k in range(4):
            dp[i][j][k] = max(dp[i][j-1][k],
                              dp[i-1][j][3])
        for k in range(3, 0, -1):
            dp[i][j][k] = max(dp[i][j][k],
                              dp[i][j][k-1] + scores[i][j])

answer = dp[R][C][3]
print(answer)

Réponse (accélérer ver AC)

from numba import jit
import numpy as np

@jit
def main():
    R, C, K = map(int, input().split())
    scores = np.zeros((R,C), np.int64)
    for _ in range(K):
        r, c, v = map(int, input().split())
        scores[r-1][c-1] = v
    dp = np.zeros((R+1,C+1,4), np.int64)

    for i in range(1, R+1):
        for j in range(1, C+1):
            for k in range(4):
                dp[i][j][k] = max(dp[i][j-1][k],
                                  dp[i-1][j][3])
            for k in range(3, 0, -1):
                dp[i][j][k] = max(dp[i][j][k],
                                  dp[i][j][k-1] + scores[i-1][j-1])

    return dp[R][C][3]

print(main())

Je voulais résoudre cela à temps. Si vous le construisez normalement avec Python, l'heure ne sera pas dans le temps, mais si vous améliorez le code d'origine avec numpy et `` @ jit, cela passera.

Tout d'abord, j'ai lu le problème et j'ai découvert que c'était DP. Cependant, je peux toujours résoudre jusqu'à 2D DP ... Pour le moment, j'écrirai le DP en ignorant la restriction de "jusqu'à 3 sur la même ligne". Ensuite, ce sera comme suit. (Lors de la visualisation d'une table DP bidimensionnelle, l'utilisation de pandas permet de voir plus facilement les directions verticale et horizontale, de sorte que les pandas et numpy sont inclus pour le débogage)

R, C, K = map(int, input().split())
scores = [[0] * (C + 1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    scores[r][c] = v
dp = [[0] *(C+1) for _ in range(R+1)]

for i in range(1, R+1):
    for j in range(1, C+1):
            dp[i][j] = max(dp[i-1][j] + scores[i][j],
                           dp[i][j-1] + scores[i][j])

print(dp[R][C])

# import numpy as np
# import pandas as pd
# show_dp = np.array(dp)
# show_dp = pd.DataFrame(show_dp)
# print(show_dp)

Jusqu'à présent, c'est facile. (Tout en disant cela, il m'était impossible il y a une semaine d'arriver aussi loin, mais ici la semaine dernière >> [Directives pour améliorer les pros de la compétition et AtCoder enseignées par Red Coder [Intermédiaire: Visez Light Blue Coder! ]](Https://qiita.com/e869120/items/eb50fdaece12be418faa# 2-3% E5% 88% 86% E9% 87% 8E% E5% 88% A5% E5% 88% 9D% E4% B8% AD% E7% B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% Je peux dire cela parce que je résolvais le problème DP de E5% 8E% BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F). )

Au moment du concours, il n'était pas possible d'incorporer la contrainte «jusqu'à 3 sur la même ligne» à partir d'ici. Je savais que je devais augmenter la dimension de la table dp d'une unité et faire "quelque chose", mais je ne pouvais pas penser à ce "quelque chose".

J'écrirai "En allant de côté, additionnez le score jusqu'à la troisième fois, et n'ajoutez rien d'autre" tel quel. Quand je résous dp, je dois en fait écrire la table dp sur papier et la visualiser, donc je ne peux pas obtenir une bonne image, donc la table dp 3D ne convient pas tout à fait. Est-ce un endroit pour s'habituer plutôt que pour apprendre?

Au fait, en python, si vous codez normalement avec dp, ce sera TLE. En tant que politique, je pense utiliser numpy pour calculer la partie écrite dans l'instruction for à la fois, utiliser pypy ou utiliser jit. Il semble que les gens forts calculent naturellement bien avec numpy, mais je ne peux pas encore écrire autant. Dans ce code, même pypy n'a pas réussi, alors j'en ai fait une fonction et utilisé @jit.

Ensuite, comme indiqué ci-dessous, "une petite quantité de calcul est beaucoup plus lente, et une grande quantité de calcul est beaucoup plus rapide", et j'ai réussi à passer AC. Je ne sais pas pourquoi cela se produit, mais si vous ne pouvez pas vous en sortir avec dp pour le moment, essayez jit de la même manière.

[Pour le code ordinaire]

[Pour le code utilisant @jit]