[PYTHON] AtCoder Pour devenir bleu clair

0. Introduction

Bonjour, c'est HIROSHI0635. J'ai écrit un article simple quand il est devenu vert, mais j'ai réussi à le rendre bleu clair environ 9 mois après qu'il soit devenu vert. Pour être honnête, je pense que ça fait longtemps. C'est pourquoi j'écris avec l'espoir d'écrire quelque chose qui donnera des indices à ceux qui luttent avec le vert ou le marron. Dans cette optique, j'ai osé lui donner le titre "Comment devenir AtCoder bleu clair" au lieu de "Jusqu'à ce qu'il devienne bleu clair" (j'admire le fait qu'il soit passé au vert en écrivant l'article ...).

1. Auto-introduction

・ Troisième année de travail dans les affaires financières. ・ AtCoder a démarré une fois en C ++, mais je ne pouvais rien faire et j'étais frustré au bout d'un mois environ. ・ J'ai changé la langue en Python et essayé à nouveau et j'ai atteint le bleu clair en un an et demi. ・ Quand j'étais à l'université, j'étais étudiant en arts libéraux. Je n'ai aucune expérience en programmation. ・ Il n'y a pas de faiblesse en mathématiques au stade des examens universitaires.

C'est à peu près comme ça. Pour ceux qui veulent savoir comment démarrer AtCoder, consultez l'article précédent (AtCoder jusqu'à ce qu'il devienne vert) Veuillez vous référer au

2. Réfléchir au problème

2-1. Penser à partir d'une croissance lente

Alors que la première performance verte était le 11e concours, la première performance bleu clair a pris la 38e (en fait la 41e parce que le 38e concours Hitachi était simplement accro à 100-200 réponses rapides). Certes, à la 11ème fois, je ne connaissais pas les soi-disant "algorithmes standards" tels que DFS, BFS, méthode Dikstra, dichotomie etc, mais à la 25ème fois, tous peuvent être implémentés et copiés plusieurs fois. C'était une situation où AC pouvait être fait pour de tels problèmes. Même ainsi, je pense que la raison pour laquelle je n'ai pas pu résoudre le problème de la difficulté verte [^ 1] était que j'étais faible dans la conscience de la quantité de calcul [^ 2] et la conscience de réduire le problème.

2-2. Sensibiliser au montant du calcul

Soudainement, remplaçons la résolution du problème d'AtCoder par la préparation du curry (le curry ne veut rien dire, j'y ai juste pensé). Supposons que l'on vous demande de faire un curry pour moins de 2000 yens comme limite. Je ne pense pas que les gens ordinaires achètent plus de 2000 yens pour les ingrédients dans les supermarchés, mais c'est ce qui se produit lorsque vous devenez de manière inattendue TLE dans une programmation concurrentielle. C'est un peu mieux si vous savez que vous ne savez pas combien coûte cet ingrédient, mais si vous vous rendez à la caisse sans tenir compte du prix, ou si vous pensez que c'est 100 yens, c'est en fait 5000 billions de yens. est. ** Si vous ne savez pas combien votre réponse est calculée, il vaut mieux prendre l'habitude de saisir d'abord votre propre réponse, au lieu d'essayer divers algorithmes **. Comme je l'ai dit, ce n'est que juste avant qu'il ne devienne vert que j'ai pris conscience de la quantité de calcul et de la réponse.) En premier lieu, le motif de l'utilisation de l'algorithme n'est pas suffisant pour la recherche complète, il est donc utilisé pour réduire la quantité de calcul, et si vous ne connaissez pas la quantité de calcul, ce sera un trésor.

Ensuite, lorsqu'on vous demande comment améliorer la capacité à saisir la quantité de calcul, s'il y a une situation où vous ne savez pas combien cette quantité de calcul représente au stade de la pratique, vous devriez vérifier la quantité de calcul ou prendre l'habitude de passer à un style d'écriture qui détermine la quantité de calcul Je pense qu'il n'y a pas le choix. Si vous êtes un utilisateur de Python, cet article (Histoire de calcul embarrassant si vous ne connaissez pas Pythonista) vous sera très utile.

2-3. Sensibiliser pour réduire les problèmes

Soudain (encore), AtCoder est souvent appelé un jeu de mathématiques. Certes, il y a des cas où des personnes ayant une solide expérience en mathématiques atteignent le bleu en quelques secondes après avoir participé environ 10 fois. Ma théorie est que c'est à moitié correct et à moitié incorrect (je suis désolé si je ne comprends pas parce que je ne fais que des examens mathématiques). En effet, il n'y a pas beaucoup de problèmes dans lesquels AtCoder peut utiliser les connaissances mathématiques telles quelles, mais la méthode de réflexion consistant à trouver une formule qui peut être appliquée en faisant abstraction du problème, qui est nécessaire pour résoudre un problème de mathématiques, peut être utilisée telle quelle. Par exemple, supposons que vous ayez appris à résoudre une équation linéaire de «5x = 10» → «x = 2» lorsque vous étiez au collège. Si vous vous souvenez de ceci tel quel, même si on vous demande de résoudre "3a = 6", ce sera "Je ne sais pas parce que je ne l'ai pas appris". Selon que le premier problème est considéré comme une variante de seulement x ou x est considéré comme un conteneur de nombres en premier lieu, le degré d'abstraction est différent, et plus il est abstrait, plus il peut être appliqué à de nombreux problèmes. Je vais. J'ai osé donner un exemple simple et donner un exemple d'abstraction, mais même dans un problème réel, la difficulté peut changer considérablement même si le montant d'implémentation n'est pas très différent en utilisant le même algorithme. Par exemple (soyez prudent si vous voulez le résoudre en premier car il inclut les spoilers ci-dessous), AtCoder Beginner Contest 177 D - Friends [AtCoder Regular Contest 107 C - Shuffle Permutation] (https://atcoder.jp/contests/arc107/tasks/arc107_c?lang=ja)

Les deux problèmes utilisent le même algorithme, mais la difficulté diffère de plus de 500. Le problème avec 177-D est que le mot «groupe» sort, et il y a une atmosphère qui est comme Union-Find, donc j'ai l'impression qu'il y a beaucoup de gens qui ont réussi à AC. Je pense que la différence dans les conséquences du problème est la différence entre ceux qui peuvent régler le problème supérieur et non le problème inférieur. Le problème ci-dessous semble trivial à première vue, mais comme il n'y a pas de duplication d'éléments, vous pouvez voir qu'il peut être considéré séparément verticalement et horizontalement (lorsque vertical et horizontal sortent, il peut être considéré séparément. C'est un schéma de pensée assez typique pour y penser). De plus, si vous considérez que les lignes / colonnes qui peuvent être permutées sont bordées, vous pouvez voir que les lignes / colonnes qui sont connectées peuvent être permutées librement. Si vous pouvez le faire jusqu'à présent, vous pouvez résoudre le problème en réduisant la structure de données qui gère si elle est concaténée ou non → Union-Find. Le point le plus important est de savoir si «swap» peut être paraphrasé comme «étirement», mais c'est ainsi que le problème peut être considéré comme abstrait. À partir de maintenant, je vais vous expliquer comment améliorer la capacité à réduire abstraitement le problème.

2-4. Formation pour améliorer la capacité de retour

① Résolvez ensemble des problèmes du même genre

En faisant cette dévotion, vous constaterez que chaque algorithme peut être appliqué à une variété de problèmes, augmentant ainsi l'impact du problème. Aussi, afin d'augmenter la puissance de conséquence, chaque algorithme doit être compris dans une dimension plus abstraite (comme le montre l'exemple de l'équation linéaire). Cependant, il est difficile de penser de manière abstraite d'un coup (si vous essayez soudainement de comprendre une définition / théorème mathématiquement strict, vous serez surpris, non?), Alors faites-vous remarquer en pensant à des exemples concrets (problèmes concrets). Je pense que cette méthode est facile à faire. Ceux qui couvent en brun et en vert sont particulièrement recommandés Directives pour améliorer les pros de la compétition et AtCoder enseignées par Red Coder [Édition intermédiaire: Visez Light Blue Coder! ] est de résoudre les 100 questions répertoriées. J'ai résolu environ 80 questions, mais j'ai le sentiment d'avoir acquis une force considérable. Il y a des problèmes difficiles, donc si c'est vraiment difficile, vous pouvez les ignorer.

② Résolvez le même problème avec une méthode différente

Si la méthode (1) est une brochette verticale, la méthode (2) est une brochette horizontale. Par exemple, les problèmes qui peuvent être résolus avec BFS peuvent être résolus avec DFS. En outre, les problèmes qui peuvent être résolus par la méthode à l'échelle peuvent être résolus par une dichotomisation approximative. Résoudre le même problème d'une manière différente conduit à une perspective différente sur le problème, augmentant le pouvoir de paraphrase du problème, c'est-à-dire la capacité de le réduire. De plus, il existe une solution qui dit que l'un ou l'autre peut être résolu, mais lequel est le plus facile à résoudre (bien que cela puisse changer en fonction de la personne), et il existe une ligne directrice pour adopter cet algorithme pour de tels problèmes, accélération et certitude. Cela conduit à une amélioration. Je pense moi-même que BFS est plus facile à comprendre que DFS, et que la dichotomie est plus rapide que la méthode de mise à l'échelle sans causer de bogue, donc si vous avez un problème qui semble s'appliquer à l'un ou l'autre, utilisez respectivement BFS et la dichotomie. Je le fais. En tant que découverte récente, j'ai appris une façon de réduire le problème avec les problèmes suivants (qui incluent également les spoilers).

[AtCoder Grand Contest B - Graph Partition] (https://atcoder.jp/contests/agc039/tasks/agc039_b)

De la conclusion, ce problème est une question de savoir s'il est possible de paraphraser "peut-il être séparé en un ensemble de sommets" → "jugement de graphe en deux parties". Quand j'ai pensé à ce problème moi-même, j'ai pensé qu'il serait possible de le séparer s'il n'y avait pas de chemins fermés de longueurs impaires, mais je ne pouvais pas écrire le code et j'ai regardé l'explication et je l'ai corrigé avec une solution utilisant un graphique en deux parties. J'ai confirmé que AC peut être obtenu en écrivant un code basé sur l'idée que "il peut être séparé s'il n'y a pas de chemin fermé de longueur impaire" car il ne s'arrête pas ici. [Méthode utilisant un jugement de graphe en deux parties] (https://atcoder.jp/contests/agc039/submissions/17673050) [Méthode axée sur la présence ou l’absence de routes fermées de longueur irrégulière] (https://atcoder.jp/contests/agc039/submissions/17673603)

Comme vous pouvez le voir en les comparant, il est plus facile d'utiliser le jugement de graphe en deux parties. Cependant, si vous osez faire ce travail, lorsque vous proposez une solution qui se concentre sur les routes fermées de longueur impaire de la même manière, vous pourrez la réduire à un jugement graphique en deux parties. Je ne pense pas que ce soit nécessaire pour tous les problèmes, mais si vous avez du mal et que vous pouvez faire AC vous-même, regardez l'explication, et si vous adoptez une approche différente, essayez-la également. Je pense que c'est bien.

2-5. Résumé

En plus de résumer l'histoire jusqu'à présent, je vais expliquer un peu le flux de réflexion sur le problème.

Je pense au problème avec un flux qui ressemble à une diapositive ci-dessus. Comme vous pouvez le voir, la clé est de pouvoir saisir correctement la quantité de calcul en ④ et ⑥, et de pouvoir se réduire à un algorithme typique capable de résoudre le problème en ② et ⑤. Lorsque vous entrez dans la branche de ①, pensez à un moyen de "lutter" et de comprendre le problème comme décrit dans ②. Ici, nous allons considérer un algorithme qui peut être résolu pour le moment, sans tenir compte de la quantité de calcul. Ce serait bien si la réponse que vous pensiez était à temps pour le calcul, mais si elle n'est pas à temps, essayez de la réduire par la méthode décrite en ⑤. Parmi eux, la lutte typique est bien organisée dans cet article (Façon de penser typique pour trouver une solution en programmation compétitive). .. Je pense que plus il y a de gens qui ne sont pas conscients de réduire le problème au niveau normal, plus ils peuvent obtenir en le regardant une fois.

3. Autres contenus de dévotion

J'ai écrit un peu de dévotion au chapitre 2, mais voici d'autres choses que j'ai faites.

3-1. Dévotion JOI

Directives pour améliorer AtCoder, un pro de la compétition enseigné par Red Coder [Édition intermédiaire: Visez Light Blue Coder! ] Il y a pas mal de problèmes JOI, mais il y a beaucoup de bonnes questions sur les problèmes JOI, en particulier le problème DP / itinéraire le plus court. Je ne suis pas très bon en DP moi-même, et j'ai aussi participé au Concours pédagogique DP / Concours de résumé DP, mais ce n'était pas très bien établi, donc c'était assez utile. .. AOJ / AtCoder-JOI est pratique car vous pouvez gérer les problèmes que vous avez résolus tout en organisant les problèmes par niveau. Pour le codeur marron, il est préférable de résoudre à partir du niveau 4 ou du niveau 5, et pour le codeur vert, il est préférable de résoudre à partir du niveau 5 ou du niveau 6.

3-2. Dévotion Kodofo

Je pense que beaucoup de gens font cela. Cependant, les concours de Kodofo ont souvent lieu tard dans la nuit et il est difficile pour les travailleurs d'y participer. Si vous utilisez Codeforces Anytime, vous pouvez obtenir une évaluation virtuelle même dans un concours virtuel, vous pouvez donc travailler avec un sentiment de tension.

3-3. Participation à une bataille d'équipe

Récemment, j'ai participé à un concours organisé par des bénévoles d'universités telles que WUPC et KUPC. C'était une bonne occasion d'apprendre les schémas de pensée des autres en participant à des groupes de trois. Mes deux coéquipiers étaient des codeurs bleus, donc je ne pouvais pas beaucoup contribuer à l'équipe, mais en pensant "je veux résoudre ne serait-ce qu'une question d'ici la prochaine fois" et "je veux rattraper ces gens", je peux le faire. Je pense que j'ai pu l'étendre.

4. Circuler dans le concours

4-1. Utilisons le classement

Vous voyez les classements pendant le concours? Je verrai. Dans le cas d'ABC, j'essaie de résoudre rapidement jusqu'à D sans regarder le classement, de regarder le classement lorsque je peux le résoudre, de regarder E et F et de résoudre F quand ils sont résolus autant. En effet, il est probable que F soit plus facile à résoudre car F est résolu autant qu'il y a des gens qui résolvent un certain nombre de face sans regarder le classement. Aussi, si vous pensez pouvoir le résoudre avec la méthode gourmande mais que vous n'êtes pas sûr de la preuve, vous devriez franchir le pas et le soumettre si vous voyez qu'il est résolu considérablement en regardant le classement ou le taux de WA est faible. Cependant, je ne pense pas que cette méthode puisse être honnête, donc je pense qu'il vaut mieux lire le commentaire et comprendre la preuve une fois le concours terminé.

4-2. L'énoncé du problème peut contenir des indices

Ce n'est pas si polyvalent, mais il peut être utilisé occasionnellement. Récemment, le problème du HHKB Programming Contest 2020 E --Lamps est AtCoder Beginner Contest 129 D --Lamp Si vous connaissez le problème de / contests / abc129 / tasks / abc129_d), vous pouvez copier et coller le prétraitement. Ces dernières années, ABC semble avoir terminé le champ des questions honnêtes, et il est important d'être conscient des questions du passé dans une certaine mesure. En outre, ce problème, AtCoder Beginner Contest 166 D - Je déteste la factorisation, nécessite-t-il apparemment une transformation de formule mathématique? J'ai pensé, mais quand je regarde l'énoncé du problème, il dit "Je déteste la factorisation" et il n'y a aucune garantie, mais je pense qu'il peut être résolu par une simple recherche plutôt que par une transformation de formule avancée. C'était l'occasion de se déplacer.

4-3. Lorsque le montant du calcul est suspect

Même si vous connaissez le montant du calcul, vous vous demandez peut-être s'il faut le soumettre à temps ou s'il s'agit d'une quantité délicate de calcul. Dans un tel cas, vous pouvez créer votre propre scénario de test avec le montant maximal de calcul et soumettre le code au test de code sur la page AtCoder pour obtenir la garantie que vous serez à temps sans sacrifier la pénalité.

5. Collecte de liens pratique

Jusqu'à présent, j'ai répertorié un certain nombre de sites Web, mais voici d'autres choses que j'ai trouvées utiles. Je pense que vous ne devriez regarder que les choses qui vous intéressent.

Passer par référence et passer par valeur dans les arguments Python ... J'ai eu du mal à comprendre la structure d'un tel langage car je n'avais pas l'opportunité d'apprendre systématiquement les langages de programmation. Si vous utilisez Python, c'est le premier contenu que vous devez maîtriser.

[Un nerd des nombres à virgule flottante tente d'expliquer le problème C du concours AtCoder pour débutants 169] (https://qiita.com/mod_poppo/items/910b5fb9303baf864bf7) ... Otaku est un dieu car il connaît un domaine spécifique. La blague concerne la virgule flottante, qui semble être devenue plus fréquente ces jours-ci, mais c'était aussi un domaine faible pour moi, qui n'avais aucune chance d'apprendre systématiquement les langages de programmation. Je ne suis pas encore bon dans ce domaine, mais je commence à remarquer des soupçons.

[Comment utiliser Python defaultdict] (https://qiita.com/xza/items/72a1b07fcf64d1f4bdb7) ・ ・ ・ Il est souvent utilisé pour juger s'il est sorti une fois en utilisant une boucle. Si la valeur maximale qui sort est d'environ 10 $ ^ 6 $, il n'y a pas de problème avec une liste initialisée à zéro, mais lorsque la valeur est jusqu'à 10 $ ^ 9 $, la quantité de calcul spatial est dépassée et la liste est initialisée à zéro. Ne peut pas être utilisé, donc defaultdict est pratique. Une fois que vous vous y êtes habitué, c'est très facile et pratique, donc je veux vraiment que vous le maîtrisiez.

[Une fonction spéciale sur la façon de trouver "trop divisé par 1000000007"! ~ De l'élément inverse au logarithme discret ~] (https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a) ・ ・ ・ Le traitement des Mods est fréquent, mais j'ai toujours été un champ faible. Après avoir lu cet article, j'ai pu comprendre le théorème de Fermat autant que je le pouvais, donc je me sentais moins faible.

[^ 1]: affichage du niveau de difficulté dans AtCoder Problem.

[^ 2]: Il existe deux types de montant de calcul, le montant du calcul du temps et le montant du calcul spatial, mais comme la fréquence du goulot d'étranglement est essentiellement le montant du calcul du temps, je pense qu'il s'agit du montant du calcul du temps, sauf indication contraire. S'il vous plaît.