Wie üblich fühlt es sich an wie "Beende das ABC-Problem 3 und bleibe für den Rest deines Lebens beim D-Problem." Mit Blick auf die Rangliste möchte ich die Genauigkeitsrate von Frage D erhöhen, um näher an den grünen bis blauen Zielgürtel heranzukommen ...
Klicken Sie hier für die Wettbewerbsseite:
https://atcoder.jp/contests/abc156
A - Beginner
https://atcoder.jp/contests/abc156/tasks/abc156_a
Sei $ R_ {in} $ die interne Bewertung und $ R_ {out} $ die externe Bewertung
Ist.
[N,R]=[int(item)for item in input().split()]
print(max(R, R+100*(10-N)))
https://atcoder.jp/contests/abc156/submissions/11763127
Es gibt auch einen Fall, in dem die Größe von K normalerweise geteilt wird. [^ 1]
[N,R]=[int(item)for item in input().split()]
print(R if N>=10 else R+100*(10-N))
https://atcoder.jp/contests/abc156/submissions/11755645
B - Digits
https://atcoder.jp/contests/abc156/tasks/abc156_b
Zum Beispiel sind 100 bis 999 Dezimalzahlen mit ** 3 Ziffern **.
Das heißt, der Wert von $ 10 ^ 2 $ bis $ 10 ^ 3-1 $ ist ** 3 Stellen ** in Dezimalzahl.
Werte von 1000 bis 9999, dh Werte von $ 10 ^ 3 $ bis $ 10 ^ 4-1 $, sind ** 4 Stellen ** in Dezimalzahl.
Denken Sie binär (Fügen Sie von nun an 2 rechts unten neben dem Binärwert hinzu, um deutlich anzuzeigen, dass es sich um eine Binärzahl handelt. Beispielsweise ist die Dezimalzahl "5" die Binärzahl "101", dies ist jedoch der Fall Ausgedrückt als $ 101_ {2} $.)
Wenn beispielsweise 6 binär ausgedrückt wird, ist dies $ 110_2 $, was 3 Ziffern entspricht.
Mit anderen Worten, die Zahl zwischen 4 und 7 ($ 100_2 $ bis $ 111_2 $) ist binär ** 3 Stellen **.
4 ~ 7 kann übrigens auch als $ 2 ^ 2 $ ~ $ 2 ^ 3-1 $ ausgedrückt werden.
Außerdem ist die Zahl zwischen 8 und 15 ($ 1000_2 $ bis $ 1111_2 $) binär ** 4 Stellen **.
8 ~ 15 kann übrigens auch als $ 2 ^ 3 $ ~ $ 2 ^ 4-1 $ ausgedrückt werden.
Wie Sie vielleicht bemerkt haben [^ 2], ist dies die Obergrenze von (Untergrenze bis Obergrenze), $ 10 ^ 3-1 $, $ 10 ^ 4-1 $ oder $ 2 ^ 3-1 $, $ 2 Es gibt eine Beziehung zwischen dem Exponenten von ^ 4-1 $ und der Anzahl der Dezimalstellen.
Wenn die Dezimalzahl N in die K-ary-Zahl zwischen [Ziffern, K, N] umgewandelt wird,
Wenn Sie den Logarithmus von K für jeden Term nehmen
(Im Fall einer Stichprobe gilt beispielsweise (N, K) = (11,2) und $ (Anzahl der Stellen) -1 \ leq \ log_2 (11) = 3,45 ... \ lt (Anzahl der Stellen) $ gilt. $ ( Anzahl der Ziffern) 11 ist eine Binärzahl mit 4 Ziffern, da nur 4 Ganzzahlen in $ passen.)
Hier,
Kann berechnet werden als.
Danach, wenn Sie dies in das Programm setzen ...
import math
[N,K]=[int(item)for item in input().split()]
#print(math.log(N,K))
print(math.floor(math.log(N,K))+1)
https://atcoder.jp/contests/abc156/tasks/abc156_b
Es war $ log_2 (11) = 3,45 ... $. Dies bedeutet, dass, wenn das Konzept der "kleinen Ziffern" existiert, die Anzahl der Ziffern, die erforderlich sind, um die Zahl 11 in Binärform darzustellen, 3,45 betragen würde ... Natürlich gibt es kein Konzept für Brüche in der Anzahl der Ziffern (keine Trübung), daher sind mindestens 4 Ziffern erforderlich, um 11 vollständig darzustellen.
In der Informationstheorie gibt es einen "Geruch" von Informationsentropie ... aber ich bin mir nicht sicher, weil ich Analphabet bin. Sehr enttäuschend.
C - Rally
https://atcoder.jp/contests/abc156/tasks/abc156_c
Die in diesem Problem erhaltenen Koordinaten von P seien die gleichen $ P
Wenn $ \ sum ^ N_ {i = 1} (X_i-P ') ^ 2 $ transformiert wird
\sum^N_{i=1}(X_i-P')^2\\
\begin{align}
&=P^2-2X_1P' + X_1^2\\
&+P^2-2X_2P' + X_2^2\\
&\vdots\\
&+P^2-2X_nP' + X_n^2\\
&=nP^2-2(X_1+X_2+...+X_n)P' + (Konstante Laufzeit)\\
&=(P-\frac{X_1+X_2+...+X_n}{n})^2+(Konstante Laufzeit)\\
\end{align}\\
Wenn $ (P- \ frac {X_1 + X_2 + ... + X_n} {n}) ^ 2 \ geq0 $ und $ P = \ frac {X_1 + X_2 + ... + X_n} {n} $ Da $ (P- \ frac {X_1 + X_2 + ... + X_n} {n}) ^ 2 = 0 $ ist, wird der gesamte Ausdruck minimiert.
(Natürlich kann das gleiche Ergebnis durch Differenzieren mit P erhalten werden.)
D - Bouquet
Ich werde es beschreiben, sobald es gelöst ist.
[^ 1]: Ich bin mir für Anfänger nicht sicher, welche Implementierung besser ist.
Recommended Posts