ABC263-Fに苦戦しました。Pythonで解きました。

abc263F問題に超絶苦戦したので、コメントアウトを多めに書きこみながら丁寧にACしました。言語はPythonです。

誰かのお役に少しでも立てれば幸いです。

コード

"""

n = int(input())
C = [[0] + list(map(int, input().split())) for _ in range(1 << n)]

# dp[i][j] :  ノード iにおいて、人jが勝ち上がっているときの、これまでノード iの子ノードで負けた人が貰うお金の合計の最大値
dp = [[0] * (1 << n) for _ in range(n + 1)]

# 誰かしらがwin_num回勝った場合を考える
for win_num in range(1, n + 1):
    # 例えば誰かが2回勝った場合(win_num = 2)を考える
    # その場合{0, 1, 2, 3}の小トーナメント, {4, 5, 6, 7}の小トーナメント, {8, 9, 10, 11} ...を考えれば良い
    # よってiにはそれぞれの小トーナメントの最も左の人(0, 4, 8, ...)を格納していく
    for i in range(0, 1 << n, 1 << win_num):
        # 小トーナメントの左半分の人をjに格納する. 
        # {0, 1, 2, 3}のトーナメントなら, 0, 1を格納する
        # 0, 1が2回勝たなかった場合(すなわち, 0が1回だけ勝つ場合と, 1が1回だけ勝つ場合)にもらえるお金の最大値を求める
        left_max = 0
        for j in range(i, i + (1 << (win_num - 1))):
            left_max = max(left_max, dp[win_num - 1][j] + C[j][win_num - 1])
        # 小トーナメントの右半分の人をjに格納する
        # {0, 1, 2, 3}のトーナメントなら, 2, 3を格納する
        # 人jが2回勝つ場合の、負けた人がもらえるお金の最大値を求める
        # 人jがもらえるお金は格納しないことに注意
        for j in range(i + (1 << (win_num - 1)), i + (1 << win_num)):
            dp[win_num][j] = left_max + dp[win_num - 1][j]

        # 上の2つのfor文と左右を反転させて同じことをする
        right_max = 0
        for j in range(i + (1 << (win_num - 1)), i + (1 << win_num)):
            right_max = max(right_max, dp[win_num - 1][j] + C[j][win_num - 1])
        for j in range(i, i + (1 << (win_num - 1))):
            dp[win_num][j] = right_max + dp[win_num - 1][j]

# dp[n][j]に格納しているのはjがn回勝った時に負けた人が貰うお金の合計の最大値
# よって, 最後にjがn回勝った時にもらえるお金を考慮して最大を取る必要がある
ans = 0
for j in range(1 << n):
    ans = max(ans, dp[n][j] + C[j][n])
print(ans)

参考: https://atcoder.jp/contests/abc263/editorial/4550

ABC257-G KMP解法 Python

abc257G問題をKMP解法でACしているPythonコードがあまり見受けられなかったので、KMP解法で解いてみました。

誰かのお役に少しでも立てれば幸いです。

コード

"""
construct_mp(s) -> mp
mp[i] = s[0:x] = S[i-x:i]なる最大のx

例)
construct_mp(aba?ababaab) ->
[0, 0, 1, 0, 1, 2, 3, 2, 3, 1, 2]
"""
def construct_mp(S):
    l = len(S)
    ret = [0] * (l+1)
    ret[0] = j = -1
    for i in range(l):
        while j >= 0 and S[i] != S[j]:
            j = ret[j]
        j += 1
        ret[i+1] = j
    return ret[1:]

s = input()
t = input()
mp = construct_mp(s + "?" + t)

ind = len(s) + len(t) #最右index
ans = 0

while ind > len(s): #Tが左端まで構成できていない限り
    if mp[ind] == 0: #Tは作れない
        ans = -1
        break
    ans += 1
    ind -= mp[ind]

print(ans)

参考: https://snuke.hatenablog.com/entry/2014/12/01/235807 https://atcoder.jp/contests/abc257/editorial/4197

機械学習初心者向け 浜田と松本どっちがゴリラか

動機

私は、バラエティが大好きです。特に「水曜日のダウンタウン」と「M1グランプリ」が大好きです。ダウンタウン浜田雅功氏がテレビで”ゴリラ”といじられているのをたびたび見かけますが、いじっている張本人である松本人志氏の方がゴリラに似ているのでは???と私は長年疑問に思い続けてきました。その辺を大学の講義で習った画像分類というものを用いて白黒つけてみようと思った所存です。

1. 2人の顔を機械に教える

画像の取得・加工

機械は、日本人の9割以上が知っているであろうダウンタウンのことを知りません。2人の顔写真を渡して、覚えてもらう必要があります。

顔写真を取得します。大量の画像を自動取得してくる方法もあることを知り見よう見まねで試してみましたが、使えない画像の方が多く逆に面倒なことになったので、今回はgoogle chromeで「松本人志」「浜田雅功」と検索し、顔がはっきりと写っているものを20枚ずつ取得することにしました。

取得した20枚の画像には、顔だけの画像もあれば、全身の画像もあります。スーツを着ている画像もあれば、松本氏が裸で肉体美を見せつけている画像もあります。「服を着ていないからゴリラは松本氏に似ている」などと分類されてしまっては、困ります。今回はあくまで顔がどちらに似ているかを知りたいと考えているからです。

よって、画像を加工する必要があります。これまた、自動で加工する方法もあるそうなのですが、元画像のサイズや切り取る箇所は画像によりまちまちで、私には難しすぎる気がしたため、諦めました。今回は、「PhotoScape X」というアプリを使って手作業で加工することにしました。

それぞれの画像の顔の部分だけを256×256ピクセルのサイズで切り取りました。256という値は適当です。サイズを揃えないと後々面倒くさいので揃えることに意味があります。

これだけでもいいと思うのですが、松本氏は金髪の画像が多く、髪色によってゴリラが浜田氏であると分類されてしまっては嫌だったので、白黒画像にすることにしました。色のオプションで「無彩色」というものを選べたので、とても簡単に白黒画像にする事ができました(厳密には無彩色画像=白黒画像ではないらしい)。

f:id:iiko_11:20211022124220p:plainf:id:iiko_11:20211022124338p:plainf:id:iiko_11:20211022124423p:plainf:id:iiko_11:20211022124429p:plain

機械に画像を渡す

いよいよPython3でコードを書いていきます。好きな場所に新規フォルダを作成し、そこにgorilla_classify.pyというファイルとdatasetフォルダを作ります。datasetフォルダにhamadaフォルダとmatsumotoフォルダを作成し、先ほど加工した画像をそれぞれ保存します。以下、gorilla_classify.pyにコードを書き込んでいきます。

import numpy as np
import glob
from PIL import Image

num_of_hamada=20 #浜田氏の画像数
num_of_matsumoto=20 #松本氏の画像数
num_of_total=num_of_hamada+num_of_matsumoto #総画像数
N_col = 256*256*4 # 行列の列数
x = np.zeros((num_of_total, N_col)) # 松本氏浜田氏の画像情報格納のためのゼロ行列生成
y = np.zeros((num_of_total)) # 松本氏浜田氏の画像に対応するラベルを格納するためのゼロ行列生成

path_list = glob.glob("./dataset/hamada/*") #hamadaフォルダに入っている画像までのパスを全て格納
i = 0

for item in path_list:
    im = Image.open(item) #画像を取得
    im_array = np.ravel(np.asarray(im)) # 画像を配列に変換
    x[i,:] = im_array #配列xのi番目にi番目の画像を表す配列を格納
    y[i] = 0 #i番目の画像が浜田氏の画像だよってことをy[i]=0と定義
    i += 1

path_list = glob.glob("./dataset/matsumoto/*") #matsumotoフォルダに入っている画像までのパスを全て格納

for item in path_list:
    im = Image.open(item) #画像を取得
    im_array = np.ravel(np.asarray(im)) # 画像を配列に変換
    x[i,:] = im_array #配列xのi番目にi番目の画像を表す配列を格納
    y[i] = 1 #i番目の画像が松本氏の画像だよってことをy[i]=1と定義
    i +=1
これにより、配列xには各画像を表す配列、配列yにはその画像が松本氏、浜田氏のどちらであるかの情報が格納されました。

2. 機械に見分け方を学習してもらう

頭のいい人たちによって、画像の見分け方の学習方法は複数種類生み出されています。今回はSVM(サポートベクタマシン)というものを使います。人に説明できるほど理解できてないので、詳しく知りたい方は「SVM」でググってください。理解しなくても読み進められます。

見分け方の学習自体は、先ほど用意した配列xとyを使って

from sklearn import svm
clf = svm.SVC()
clf.fit(x,y) #見分け方を学習する

のたった3行のみで学習できてしまいます。先人たちに感謝です。

しかし、xとyをこのまま使うと、困ったことになるのでこのコードは使いません。次の章で説明します。

3. 学習した見分け方が正しいか検証する。

最初に用意した配列x、yを使用したいのでgorilla_classify.pyに引き続き記述していきます。

機械がゴリラをどちらに分類するかを実験することが最終目標ですが、これは機械が松本氏と浜田氏の区別がしっかりできるようになっていることが大前提です。この機械は本当に松本氏と浜田氏を見極められるようになっているのでしょうか。検証する必要があります。

この検証で注意すべき点は、ズルをしないことです。最初に、それぞれ20枚の画像を機械に渡しました。すでに機械に答えを教えた画像に関して、「この画像は松本氏と浜田氏のどちらですか?」と聞いても、当然間違えません。そこで学習のために機械に渡した画像と検証するための画像を別のものに必要があります。しかし、画像は20枚ずつしか用意しておらず、これ以上増やすのは面倒です。よって、「40枚の画像を、学習用の画像と検証用の画像に分割し、正答率を計測する」という操作を複数回行います。

from sklearn import svm

def svc_classifier(x_train, y_train, x_test, y_test):
    clf = svm.SVC()
    clf.fit(x_train, y_train) #見分け方を学習する
    pred = clf.predict(x_test) #学習した見分け方に基づいてテスト画像を分類
    mispred = (pred != y_test).sum() #テスト画像のうち正しく分類できなかった画像の枚数
    return 1 - mispred / x_test.shape[0] #正しく分類できなかった画像の割合を返す

from sklearn.model_selection import train_test_split

def test_model(x,y,itertimes):
    now_svc=0
    for i in range(itertimes): #学習と検証をitertimes行う
        x_train, x_test, y_train, y_test = train_test_split(x, y) #x、yを学習用と検証用にランダムに分割

        now_svc+=svc_classifier(x_train,y_train,x_test,y_test)

    print(now_svc/itertimes) #正答率(正しく見分けられた割合)の平均を出力

test_model(x,y,100)

先ほど説明した、見分け方を学習するclt.fitの引数のx、yに対応する部分がx_train、y_trainに変化している事がわかると思います。

これにより、SVMアルゴリズムによって松本氏と浜田氏の見極めを正しくできるようになるのかを検証する事ができます。

python3 gorilla_classify.pyを実行したところ、0.9990000000000001と出力されました。すなわち99.9%の精度で松本氏と浜田氏の見極めができているといえます。

4. 機械にゴリラの顔を渡す

先ほどと同じ要領で、gorillaフォルダを作成し、google chromeから20枚のゴリラ画像を取得します。そして、画像加工アプリで256×256ピクセルのサイズに切り取り、無彩色画像に変更しました。

f:id:iiko_11:20211022160015p:plainf:id:iiko_11:20211022160020p:plain


引き続き、gorilla_classify.pyにコードを書いていきます。基本的には、松本氏浜田氏の顔を機械に覚えさせた時と同じです。違いは配列y_gorillaを用意する必要がない事です。ゴリラの画像を与えて、これがゴリラだよって機械に教えたい訳ではないからです。ゴリラの画像情報を機械に渡すだけでオッケーです。

num_of_gorilla=20 #ゴリラの画像数
x_gorilla=np.zeros((num_of_gorilla,N_col)) #ゴリラの画像情報格納のためのゼロ行列生成

path_list = glob.glob("./dataset/gorilla/*") #gorillaフォルダに入っている画像までのパスを全て格納
i=0

for item in path_list:
    im = Image.open(item) #画像を取得
    im_array = np.ravel(np.asarray(im)) #画像を配列に変換
    x_gorilla[i,:] = im_array #配列x_gorillaのi番目にi番目のゴリラ画像を表す配列を格納
    i += 1

5. 機械はゴリラをどちらと判断するのか

いよいよ本題に入ります。松本氏と浜田氏を正しく見極める事が可能になった機械はゴリラをどちらだと認識するのでしょうか。ここでは、モデルの検証を行う必要がないので、松本氏浜田氏の画像40枚全てを使って、学習を行います。

clf = svm.SVC()
clf.fit(x, y) #検証は終わったので、松本氏浜田氏の画像40枚全てを使って学習する
gorilla_pred = clf.predict(x_gorilla) #ゴリラの画像はどちらであるか見分ける 浜田氏と判断すれば0 松本氏と判断すれば1
hamada=0
matsumoto=0
for i in gorilla_pred: #len(gorilla_pred)=20
    if(i==0): #ゴリラの画像を浜田氏と判断した時
        hamada+=1
    else: #ゴリラの画像を松本氏と判断した時
        matsumoto+=1
print(f"hamada:{hamada}/{hamada+matsumoto}") #ゴリラの画像20枚のうち、浜田氏と判断したされた数
print(f"matsumoto:{matsumoto}/{(hamada+matsumoto)}") #ゴリラの画像20枚のうち、松本氏と判断された数

出力は、以下のようになりました。

f:id:iiko_11:20211022155546p:plain

つまり、機械にゴリラの画像を20枚渡して、「松本氏と浜田氏どっちに見える?って聞くと、機械が「全部松本氏に見える」って答えたことになります。

総括

この結果を見ると、浜田氏に対するゴリラいじりが不当極まりないものであったと結論づけることができます。また、ゴリラいじりをされた際、笑みを浮かべ受け入れているように見えてしまう浜田氏の反応は、完全に間違っており、正解は「お前の方がゴリラやろがい!」であったことがわかります。

この事実は、世間に流布している「浜田氏といえばゴリラ、ゴリラといえば浜田氏」という誤った認識を根底から覆すものであり、日本中を震撼させるものと言っても過言ではありません。周囲の人に、一刻も早く夢から醒めるように説得してほしいと切に願います。

調子に乗りました。今回の手法にも、ほんの少しの正当性はあると信じたいです。しかし、データ数が圧倒的に少ない点、加工した画像にも髪色の違いが根強く残っており、これが大きな影響を及ぼした可能性がある点などを考えると、とても正当であると言い切ることはできません。

間違いやアドバイス等ありましたら、教えていただきたく思います。拙文を読んでいただきありがとうございました。

ARC133感想

結果

ARC初の3完。ARC128では0完で泣きそうになっていた私ですが、ついに3完できる日が訪れました。感慨深いです。

f:id:iiko_11:20220123000106p:plain

f:id:iiko_11:20220123000031p:plain

A問題

E8さんの競プロ典型90問の「辞書順は前から」の考えに則って解きました。前から見ていき、a[i-1]>a[i]となるような部分が出てきたらa[i-1]の数字を取り除くことが決定します。a[i-1]>a[i]となる部分がない場合、"employee"より"employ"の方が辞書順が前理論に基づいて末尾の数字を取り除きます。break を書き忘れて1WAを喰らってしまいました。自分らしさ全開です。

B問題

最初は解ける気がしませんでしたが、諦めずに紙とペンを使って考察し続けました。思考を進めていくと少し前に解いたARC126のB問題と類似していることに気づきました。ARC126_Bでは接続可能な辺が与えられていましたが、今回はa[i]がb[j]の約数であればa[i]とb[j]は接続可能であるというように自分で接続可能な辺を求めることで、同じ問題のように扱うことが可能になりました。あとは、ARC126_Bの自分の回答を見ながらSegTreeを使って、辺が交差しないという条件下で、最大となるような接続する辺の数を求めて行きました。

C問題

B問題まで解けて満足していたので撤退しかけていたのですが、問題に目を通して本当に良かったです。

まず、sum(a)%kとsum(b)%kが一致しない場合、総和をkで割ったあまりが2種類あることになり意味不明なので-1を出力すべきです。次に、総和はなるべく大きい方がいいので、全てのマスにk-1を入れるのが理想です。よって、ans=(k-1)*h*wと設定し、ここから条件に当てはまるように引き算していくことにしました。

i行目に着目します。現在i行目の総和をkで割った余りは(k-1)*w%k(以下、xとする)であり、これがa[i]と一致しなければなりません。x>=a[i]の場合、x-a[i]をi行目の適当なマスから減じることで矛盾しない書き込みとなります。x-a[i]+zk(0<=z)を減じれば矛盾しませんが、マスに書き込まれている数字は大きいほどよく、減じる数は小さい方が良いのでx-a[i]を減じるとして進めます。x<a[i]の時、x+k-a[i]をi行目の適当なマスから減じることで矛盾しない書き込みとなります。

以上の操作を全行に対して行って最終的に残ったansがaに矛盾しない最大の総和です。同様にans2=(k-1)*h*wと初期設定し、行とは独立に全列に対しても上記の操作を行うと、min(ans,ans2)が答えです。

総括

C問題は正当性を確かめることなく、通ったらいいなーくらいの気持ちで解答を投げたので全くもって実力とは言えませんが、それでも青パフォを出せたことはとてつもない自信になりました。大きな大きな目標だった入水を達成できて感無量です。次の目標は水色定着です。

ABC235感想

結果

人生2度目の5完を目指すも叶わず。4完が少しずつ安定してきたことに成長を感じます。

f:id:iiko_11:20220115233410p:plain

f:id:iiko_11:20220115233439p:plain

A問題

全桁の数字に111をかけて足し合わせてAC。A問題を少し工夫して解くことができたのは初めてです。

B問題

前の台から愚直に大小比較していきました。今の台の高さ>=次の台の高さの時、高橋くんは動かなくなりbreakです。

C問題

各数字が何番目に登場するかを辞書を使って記録していきました。例えば"5"がa0、a3、a7に登場するときはdictionary[5]:[0,3,7]です。数字xiの登場回数がki回を超えている時は、dictionary[xi][ki-1]を出力します。1を引いているのはlistが0-indexedだからです。

D問題

dequeを使って、愚直にシミュレーションしました。まだ生成されていない数字が新たに作られた時のみdequeに追加することで、計算量は必ずO(10**6)におさまります。各数字を生成するのに必要な回数をlistに格納していき、目的の数字が生成される、もしくはdequeが空になったらbreakです。

E問題

解けませんでした。まず、コンテスト中にクラスカル法のアルゴリズムを復習しました。必要知識をコンテスト中にググった問題が解けたことはほとんどありません。解けぬべくして解けなかったと言えます。クラスカル法は重みの小さい辺から順に選んで、閉路にならないのであれば採用していくというアルゴリズムだと分かったので、新たに追加される重みwの無向辺がuとvを結ぶとき、wよりも重みの小さい辺でuとvが結ばれうるのであれば、追加辺は最小全域木を構成する辺になり得ない、それ以外は追加辺になる。と考察したのですがWA。最後まで何が違うのかがわからずタイムアップしてしまいました。

コンテスト後、実装が考察を反映できていなかったことに気づきました。勝手に連結判定しているつもりでしたが、できていませんでした。

総括

E問題が解けない問題から解けそうな問題に変わってきた実感があります。5完が当たり前になる日を夢見て、少しずつ精進していきたいと思います。

余談

kaggleに興味があるのですが、何から始めたらいいのか分かりません。春休みに入ったら少しやってみようかなと思ったり思わなかったりです。

ABC234感想

結果

人生初の5完。5完は1つの大きな目標だったので、本当に嬉しいです。

f:id:iiko_11:20220108233130p:plain

f:id:iiko_11:20220108233152p:plain

A問題

defを使って関数f(x)を定義しました。新鮮味のあるA問題でした。

B問題

入力の数が小さいB問題は大抵全探索で解ける気がします。

C問題

まず、何桁かを考え、その後、前から0か2を割り振っていきました。実装が少し大変でした。2進数の1を最後に2に変更したら良いだけだったという解説を見て、感動しました。確かにその方法だと実装も簡単そうです。思いつけなくて悔しいです。

D問題

優先度付きキューを使う発想がなく、最初bisect.insort関数を使ってTLE。listの長さを変えるのには時間がかかるという事実を肝に銘じ、この類のTLEをなくしていきたいと思います。setを使いながらごちゃごちゃやってなんとかACできました。最初の方のABCで優先度付きキューの問題を解けなくて悔しい思いをしたにもかかわらず、優先度付きキューの発想が出なかったというのは本当に反省しなくてはなりません。

E問題

考えるべき範囲において、等差数なるものがそれほど多く存在しないことに気づけたのが勝因でした。後は、等差数を列挙、ソートし、bisect.bisect_left関数を使って適切な等差数を出力しました。

F問題

dpというのはわかりました。さらにO(n**2)のコードを書いたつもりで提出してTLE。どこがダメだったのか要復習ですが、的外れではなかった気がします。

総括

個人的にはEよりDの方が難しく感じたので、いつもより難易度の優しいE問題だったのかもしれませんが、それでも5完という目標を達成できて嬉しいです。5完の頻度を増やすことを目標に頑張っていきたいと思います。

余談

日本では、コンビニの数より歯科医院の数の方が多いらしいです。個人的には、直感に反しすぎです。

ABC233感想

結果

そこそこのタイムで4完。耐えたという印象です。 E問題は恒例の誤読をしていました。力がないから誤読が起こります。単純に実力不足です。本当に反省しなければなりません。

f:id:iiko_11:20211225235813p:plain

f:id:iiko_11:20211225235743p:plain

A問題

全部場合わけしました。恐ろしくスマートな以下のコードを開始25秒で提出している怪物さんがいらっしゃいました。脳取り替えてください。

print(max(0,(y-x+9)//10))

B問題

0-indexと1-indexを脳内ですぐに整理する能力をそろそろ身につけたいのですが、無能にはまだまだ時間がかかりそうです。

C問題

ボールの個数の総積<=10**5の制約から全探索すればいいことは分かったのですが、実装方法が思いつかず、かなり苦戦しました。

ひねり出した実装方法は、辞書を使って、各袋まで見終わった時点での積の候補とその個数を保持し続けるというものでした。引き出しの少なさを痛感しました。

天才たちのコードを見て、itertoolsのproduct関数がこの問題を解くのにピッタリだったということを知りました。引き出しが増えたとポジティブに捉えたいと思います。

D問題

最初、尺取り法かなと思い、総和がピッタリKという制約のため、あー無理だな。と気づくまでに5分を要しました。累積和をとればなんとかなりそうだなと思って手を動かすと、本当に上手くいきそうだったので、C問題と同様に辞書を使い、頑張って実装しました。ある場所までの累積和-Kがそれより左側の累積和に存在していたら、存在した数だけansに加算します。もっと早解きできるようになりたいです。

E問題

ググると、繰り上がり計算を自分で上手に実装することで大きな桁数の足し算を高速化できるという記事が出てきて、これに間違い無いと思って実装しましたがWAとTLEがとれませんでした。

分母の10**kのkは0から10**100までをとる制約でしたが、弱々アホアホ脳が10**(10**100)なんてあるわけないと思ってしまい、kが0から100までをとるという制約に勝手に読み替えてしまっていました。

誤読してしまった結果、入力Xの桁数が100以上の時は上の方の桁の数字がが1桁目まで加算されることはないので当然WAをくらいました。

コンテスト後、誤読に気づいた後は自力ACできたので、悔いは残りますが、それと同じくらい手応えを感じることができました。来年こそは5完します。

総括

クリスマスのコンテストで、問題文にサンタさんをねじ込んでくれるようなユーモアが楽しくて仕方ありません。作問者さんに感謝です。

5完できていたら年末年始サボりまくっていたと思うので、良い戒めになったと思うことにします。

余談

AtCoderの提出コードのページに「ためになった」ボタン的なのがあったら、綺麗なコードを書くモチベにもなるし、コード作成者に感動と感謝を伝えられるのになーと思ったりしている今日この頃です。感動と感謝を伝えたい方が山ほどいます。あげたらキリがないですが、一番参考にしているのはrin204さんです。届け、この思い。

ABC232感想

結果

6ペナルティ4完。年内水色を目指しているにも関わらず茶パフォをかましてしまったと思ったら、ギリギリ緑パフォでした。ac-predictorという拡張機能の精度が分かりません。

f:id:iiko_11:20211219231557p:plain

f:id:iiko_11:20211219231532p:plain

A問題

文字列として受け取って、index0とindex2の文字をintに直して掛け算しました。

B問題

かなり時間を要しました。原因は2つ。まず、O(len(s)**2)のプログラムをO(len(s))だと見積もってしまった点。次に、chrやらordやらを考えているうちに頭がこんがらがってしまった点。計算量を見積もりながらたくさんの問題を解くことで成長していきたいです。

コンテスト後、文字列を数値に置き換えて考えたら、もっと簡単に解けたということを知りました。頭やわやわになりたいです。

C問題

n=8なので全探索できそうだと考えました。辞書を使って、青木くんのおもちゃの数字がそれぞれどの数字に対応するかを管理しました。その対応関係に基づいて、構築し直したグラフが高橋くんのグラフと同じならばYesです。

D問題

とにかく苦しみました。まず最初に、右と下だけでなく左と上にも移動できると誤読しており、昨日復習したばかりの深さ優先探索を実装してTLE。深さ優先探索の計算量が分からないので、PypyじゃなくてPythonにしたら通るのではないかと思って提出してTLE。ここで誤読に気づきました。あとはdequeを使って連結判定を行っていきました。ACを確信して書いたコードがTLEを喰らってしまい、なぜTLEなのかを突き止めるのに20分くらいかかってしまいました。原因は同じ点を何度もdequeにappendしてしまっていたことでした。解説ACばかりしているのでバグとりの実力が全くついていないようです。

深さ優先探索は基本的に、全ての頂点と辺を走査するのでO(V+E)ですが、私の実装では同じ点を何度も走査していたので当然TLEが出たようです。

E問題

残り10分。解法が思いつきませんでした。仮にDまで早解きできていても5完は無理だったように思います。

総括

今週はそこそこ精進したつもりだったのでショックでした。精進の方向性が間違っているのでしょうか。わかりません。

余談

Rated Point Sumが200000を超えたらほぼほぼ水色になれる的なことを書いている記事を見てしまい、無能と自覚していながらも深めに傷つきました。

ABC231感想

結果

4完。先週は3完だったので、素直に嬉しいです。

f:id:iiko_11:20211211232122p:plain

f:id:iiko_11:20211211232146p:plain

A問題

自分がコンテストに出始めて以来、最も簡単な問題だったように思います。

B問題

辞書を履修していたのでとても簡単に解くことができました。pythonの場合、辞書はdefaultdictというライブラリを使うと便利です。当初は難しそうだという理由で敬遠していましたが、一度使うと虜になってしまいました。

C問題

身長順にソートして二分探索しました。「~以上/以下のものはいくつあるか。」と問われたら二分探索が使えることが多い気がします。問題を見てすぐに二分探索だと気づけたことに成長を感じました。

D問題

1列に並ぶ時、1人が3人以上と隣り合うことはできません。この条件のみを考えて提出してWAを喰らってしまいました。考察してみると、(1,2)、(2,3)、(3,1)が全て隣り合う時、円を作るしかなくなるため条件を満たしません。これをUnion-Findを用いて判定し、ACできました。隣り合う2人を次々に連結させていき、新たに連結させようとする2人がすでに連結しているならば、円(閉路)ができてしまうので、条件を満たさないといった具合です。

E問題

D問題でWAしたものの順調に歩みを進め、残り80分。問題をみると、かなり練習してきた桁DPで解けそうな雰囲気。今回こそは5完できるかもしれないと希望を抱いて問題に取り組みましたが、何をどうしたらいいのか分からないままタイムアップ。圧倒的実力不足です。来週までにACします。

総括

E問題の壁が厚すぎます。E問題が解ける日は来るのでしょうか。もし解けたら、嬉しすぎて眠れない気がします。

余談

ABC231は全体的に問題文の文章量が少なく、文字嫌い無能な私的にはとてもありがたかったです。意図して文章量を減らしてくださったように感じました。

明日はAHCなるものが開催されるということで、初参加してみようと思います。

ABC230感想

結果

3完。4完を安定させたいお年頃なので辛すぎます。

f:id:iiko_11:20211203235025p:plain

f:id:iiko_11:20211203234955p:plain

A問題

入力が1桁の時、42以上の時、それ以外に場合分けしてACしました。pythonの基礎知識が圧倒的に足りていません。競プロやっていれば少しずつついていくかなと楽観視してしまっています。

"AGC"+str(n+(n>41)).zfill(3)というコードが多分最もスマートです。zfill(x)はx桁になるようにゼロ埋めしてくれるみたいです。

B問題

最初のoの場所で場合わけしました。sの長さが2以下の時を考慮できておらず痛恨の1WA。解説を読んでs in tだけでよかったんだと分かり悲しくなりました。

C問題

40分格闘し、最終的に諦めました。敗因はmax(1−A,1−B)≤k≤min(N−A,N−B)及びmax(1−A,B−N)≤k≤min(N−A,B−1)という条件式を理解できなかったことです。今思えばなぜこの条件式の理解を諦め、放置して問題に入ろうと思ったのか後悔と謎しかありません。(a,b)を通る傾き1の線分と傾き−1の線分を黒く塗ればいいことは分かったのですが、線分の両端と(a,b)の位置関係で場合わけをせねばと考えており、可読性のかけらもない長々コードを書いて挙げ句の果てにはACできませんでした。普通の人なら1分で理解できる条件式に対して、たとえ10分かかろうがしっかりと理解してから問題に取り組まないと解けるはずがないということがわかりました。

らしさ全開のバカなコード書いてました

C問題 解説AC

D問題

結論から言えばなぜかACできましたが、本質を全く理解できていませんでした。右端に関してソートして前から見ていくのが想定解法であり、解説を読んで納得しました。私は左端に関してソートして前から見ていきWA。もう時間もなかったのでなんとなく反対側からも見て回数の少ない方を出力してみようと思ったらACできました。偶然、想定解法の真逆である左端に関してソートして後ろから見ていくというプログラムを書けていただけで、何も理解できていませんでした。全コンテスタントに申し訳ない気持ちが込み上げてきました。申し訳ございませんでした。

E問題

n=12について考えてみました。約数は[1,2,3,4,6,12]。12//12が12-6個、12//6が6-4個、12//4が4-3個...という考察のもと、かなりの自信を持ってコードを書いたら、4AC、18WA。どういうケースがカバーできていないのか分からないままタイムアップ。素晴らしき方々のありがたき解説を読みながらまったり考えたいと思います。

E問題 コンテスト中の提出

総括

12月は毎回4完しようと心に決めていましたが、早くも失敗してしまいました。また明日から少しずつ頑張ります。

余談

今まで知らなかったatcoderの機能について。すべての提出を見るとき、「コード」とか「実行時間」とかの文字をクリックするとコード長順、実行時間順に並び替えてくれるのです。クリックできるところは青くデザインされているということに気づけていなかった私は本当に驚き、感動しました。