あるぱかのブログ

AtCoder茶(レート566)

モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

A - Leftrightarrow

リンク：A - Leftrightarrow (atcoder.jp)

概要：<、=、>からなる文字列 Sが、<==…==>のようになっているか判定してね

文字列 Sの1文字目が"<"、末尾が">"、その他が全て"="であればYes、そうでなければNoを出力します。

そのまま S[0]="<"、 S[-1]=">"、 S[1:-2]= "="かどうか確認します。

#ABC345 A - Leftrightarrow
S = input()
#正誤判定のフラグ 条件を満たさないと分かったときにFalseに変える
flag = True
if S[0] != '<':
    flag = False
if S[-1] != '>':
    flag = False
for i in range(1, len(S)-1):
    if S[i] != '=':
        flag = False
#すべての判定を潜り抜けたらYesを出力、どこかで引っかかったらNoを出力
if flag == True:
    print('Yes')
else:
    print('No')

提出リンク：提出 #51278901 - モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

B - Integer Division Returns

リンク：B - Integer Division Returns (atcoder.jp)

概要：整数 Xに対して  \dfrac {X}{10}以上で最小の整数を出力してね

Xが10の倍数ならそのまま \dfrac{X}{10}を、そうでなければ \dfrac{X}{10}+1を出力すれば題意を満足します。

AtCoderでは上界 \lceil X \rceilと下界 \lfloor X \rfloorは頻繁に出てくるので覚えておきましょう。

それぞれ天井関数、床関数とも言います。

今回のA問題よりこっちのほうが簡単じゃない・・・？

#ABC345 B - Integer Division Returns
X = int(input())
#余りが0なら10の倍数なのでそのまま、違う場合は+1して出力
if X % 10 == 0:
    print(X//10)
else:
    print(X//10 +1)

提出リンク：提出 #51282581 - モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

C - One Time Swap

リンク：C - One Time Swap (atcoder.jp)

概要：英小文字からなる文字列 Sの2か所を選んで入れ替えを行うときに最大何通りの文字列ができるか出力してね

文字列の長さN = 10^{6}なので組み合わせ数は最大 _{10^{6}} C _2=5 \times 10^{10}なので愚直に全パターン試すと当然TLEします。

全パターンから重複するものを引けば答えが出そうなのでその方針で行きます。

いつもの度数分布で各文字が何個あるかチェックを行い、度数分布 numの要素数 n = 文字列 Sの長さ Nであれば答えは _N C _2となります。

重複がある場合、仮にabcccのようにcが3文字あれば重複する数は _3 C _2なので上記の組み合わせ数から引けばよさそうです。

一般化すれば特定の文字が D回あるとすると重複する数は _D C _2です。

ただ今回は文字列入れ替え前をカウントしていないので、入出力例2のような場合に _5 C _2 - _5 C _2 = 0となり引きすぎてしまうので、重複がある場合のみ+1して初期の文字列分を考慮します。

中学か高校数学でこんな感じの問題あったような気がする・・・

#ABC345 C - One Time Swap
from collections import defaultdict
S = input()
N = len(S)
#度数分布作成
num = defaultdict(int)
for key in S:
    num[key] += 1
#print(num)
#すべて違う文字としたときの総組み合わせ数
ans = N*(N-1) // 2
#度数分布の要素数=文字列の種類
n = len(num)
#すべてバラバラの文字ならansをそのまま出力
if N == n:
    print(ans)
#違う場合はansから重複分を引いて+1した数を出力
else:
    for key in num:
        if num[key] > 1:
            ans -= num[key] * (num[key] - 1) // 2
    ans += 1
    print(ans)

提出リンク：提出 #51309245 - モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

ここまで28分、最終順位2735 / 10047位で大変満足です。

D - Tiling

リンク：D - Tiling (atcoder.jp)

概要：手持ちのタイルを使ったり使わなかったりしてマス目をぴったり埋められるか判断してね

解けなかったのでお気持ちだけ。

タイルのサイズを受け取ると同時に各タイルの面積をメモしておき、まずはDPで面積ぴったりになるタイルの組み合わせを探す。面積が合わないならNoを出力して終了。

上記で選んだタイルが占有する座標をそれぞれ列挙する。

全探索で座標の重複なく置けるかどうか確かめる。

置けなければ90°回転（座標(x, y) →(y, -x)）でまた全探索。

マス目ぴったりになればYesを出力。

1番目のDPするところまでは書けましたが残りがね・・・diffどのくらいだろう、緑上位か水色？

結果

いつも通りA~Cの3完28minでした。

今はまだ実装できないけども解法がぼんやり浮かぶくらいにはなったような気がします。

初めての緑パフォ！