masuTomo’s blog

競技プログラミングの勉強メモです.主にPythonを使用します.数学の記事も書くかもしれません.

非プログラマーがやる競技プログラミング

はじめに

この記事は次のアドベントカレンダーの12/11の記事として投稿します。 qiita.com

対象読者

競技プログラミングをやっていて次のいずれにも当てはまらない方

  • 上級者(AtCoder水色以上くらい)
  • 競プロ忘年会に参加している人 (今日やってるらしい)
  • IT系企業に勤めている
  • 理系大学(院)生である
  • 競技プログラミングを一緒にやる友達等がいる
  • Twitterに競プロをやっているフォロワー(リプライできるひと)がいる
  • めちゃめちゃ頭がいい(一人で精進してどんどん強くなれる)

要は周りに競プロやってる人いないけどやってみたい(やってるぞ),でも不安だな,という人に向けた記事のつもりです。

私の周囲の環境

  • 非ITの職場(エクセルマクロ使える人はほとんどいない)
  • 競技プログラミングという言葉を知っている人が知人にいない
  • 現実世界で競プロをやっている人と会ったことがない

一人で競プロをやっていて困ること

  • 情報が入ってこない
  • 勉強が続かない
  • 疑問が解決できない

この3つがとても大きいです。これらのことに焦点をあてて記事を書きたいと思います。

情報収集について

そもそも,このブログにたどり着いている方は,この部分を読む必要はない気がしますが,一応書きます。

Twitterをはじめる

これがほぼ唯一解な気がします。私自身,Twitterを始めた時期と競プロを始めた時期が(たまたま)ほぼ一致していますが,競プロの情報の9割以上はTwitterから得ています。

ここで,私がフォローしている競プロerのアカウントをいくつか紹介します。(勝手に紹介してすみません)

@chokudai いわずもがなAtCoderの偉い人。ぷよぷよとかその他の話題も多い。

@drken1215 @drken_procon けんちょん本の著者。アルゴリズムググるとこの方のQittaの記事によく出会う。

@kenkoooo AtCoder Problemsの方。チョコケーキがお好きらしい。

@kyopro_friends よくAtCoderのコンテストのWriterをされているイメージ。コンテスト後に問題に対して解説ツイートしてくれるのだ。

@kaede20203 この方の周りには色々な競プロerが集まってこられてます。こつこつ続けられていて本当にすごいです。

@e869120 この度,競プロの本を出版されるとのこと(予約しました)

@sak_algo アルゴ式の方(大変お世話になりました)

※ほかにもたくさんの競プロerの方をフォローしていますが,ツイートの頻度や内容,私のアカウントから見つけやすかった,という3つの観点で選びました。 基本的には,ここで紹介した人のうち,数名をフォローしておけば,あとは芋づる式にたくさんの競プロerを発見することができる思います。

注意点

自分と同じくらいの実力の人もフォローしましょう。そして自分も発信しましょう。意外と自分と同じことで悩んでいる人もいるものです。

理由

基本的にフォロワーがたくさんいて発信力がある(Twitter上で有名)な方は強い方(AtCoderでいう青以上)が多い気がします。

コンテスト後のTLが,自分にはちんぷんかんぷんの話題ばかりになってしまい辛いです。

勉強が続かないことについて

正直難しいです。

競プロを一緒にやっている友人知人がいる場合は,コンテストのあとにわいわいすることもできるでしょう。そのために普段から勉強するというのも楽しいでしょうし,なんなら競プロゼミのようなことをやっている人もいるかもしれません。

ですが,ひとりぼっちだとそのどれもありません。せいぜいレート上がったことをツイートして,1つか2ついいねがつくくらいです。

それではなかなか難しいので,ある程度の強制力が必要だと思います。ここで私が色々試したことを列挙します。(合う合わないは個人差が大きいと思うので,私が挫折したものでも,みなさんに合うものもあるかもしれません)

とにかくコンテストに出る

これを私は川内優輝方式と読んでいます。つまり,本番で練習してしまおうということです。 最初の方の自分のレートがどんどんあがっている時期はいいのですが,レートが下がり始めると辛くなります。

自分でノルマを決める

毎日◯◯をやるぞ!と決めて取り組んだこともありました。個人的にはこれが一番合っているのですが,問題点として,わからない問題にぶつかったときに進捗がでない(後述)。仕事が忙しくなるとできなくなり,その後ペースを元に戻しにくい。

なお,このときはAtCoder Problemsのrecommendationの問題をこつこつやっていました。

Paizaに課金する

1ヶ月くらいで挫折しました。3ヶ月やったうちの2ヶ月分くらいの利用料は無駄になりました。

アルゴ式をやる

アルゴ式でテスターをやらせてもらう機会をいただきました。コーチング,ペースメイキングということでサポートいただきましたが,結局この他者からのプレッシャーが一番効果的だった気がします(結局一人ぼっちじゃ無理ということになってしまう)。

ちなみに,テスター期間は終了してしまいましたが,アルゴ式に取り組むこと自体は継続しています(アルゴ式は初学者向けのコンテンツとして,とてもおすすめだと思います)。

疑問の解決について(精進)

書籍について

書籍とWebサービス以外に頼れるものはありません。ここでは私が所有している書籍をご紹介します。

www.amazon.co.jp

www.amazon.co.jp

www.amazon.co.jp

*プログラミングコンテスト攻略のためのアルゴリズムとデータ構造(マイナビ

www.amazon.co.jp

このうち,役にたったと感じているのは最初の2冊かと思っています。それ以外の本はちょっと初心者には難しいです。ただ,蟻本などは辞書的に使うことがあります。 一緒に読み進めたり,質問できる相手がいれば良いのでしょうが,一人なのでそうもいきません。

そのことを打破するために次の提案します。

アウトプットの機会をつくる

Twitterかブログで発信しましょう。一人で勉強していると知識を得るという意識に偏りがちなので発信することを意識するのが良いと思います。

友人知人がいることの良さは議論できることだと思っています。もう少し限定すると,自分の口で説明する機会が得られることとしても良いかもしれません。ベアプログラミングと似たような考えでしょうか。

発信することで自分の考えを整理するきっかけになりますし,自分がわかっていない部分が明確になります。

初学者は,なかなかそのような行動は取りにくいかもしれませんが,同じような初学者で困っている人も多くいます(AtCoderでも灰・茶の人がほとんどなのですから)。 ぜひやってみてください。

もし,みなさんがそのようなブログやツイートを見かけたら積極的にいいねするようにしてあげてください。

おわりに

とりとめのないことをつらつらと書いてしまい非常に読みづらかったのではないかと思います。

ずっと一人で競プロをやっていて,続ける工夫を試行錯誤する中の一つの取り組みとしてこのアドベントカレンダーを利用させてもらいました。ごめんなさい。

私は地方に住んでおり,競プロのイベントにも気軽に参加できません。最初に書いたように一緒にやる知人もいません。ときには次のようなツイートをしたこともあります。

冗談ですが,心情としてはこんな感じです。 もし,ここまで読んでくださった稀有な方がいらっしゃれば,ぜひ私と一緒に競プロをやりましょう。よろしくお願いします。

最後までお読みくださいありがとうございました。

アルゴ式のテスターに選ばれました(20日目?)グラフ入門で苦労しています

更新が滞っており申し訳ありません.

停滞していた理由としては,全然解けなかったからです.

進捗

以前の記事で次は

algo-method.com

これに挑戦すると言っていました.最初はこのコンテンツの貪欲法に取り組みました.

貪欲法自体はそこそこかけて,Q1-1〜Q1-7まで自力でACできました.その次にグラフ入門のコンテンツに取り組むことにしました. アルゴ式には教科書があるので,それを読みながら進めることでQ3-4まではサクサク解くことができました(3日くらいでここまで到達).

そこからQ3-5でかなり詰まりました.

algo-method.com

Q3-5について

問題

次の操作を k = 0,・・・N-1について順番に行う.

  1. もし k=0なら頂点0に色を塗る

  2. もし k 0 ならi-1回目の操作で色が塗られた頂点と繋がっており、まだ色が塗られていない頂点に色を塗る。

操作 k によって色が塗られた頂点を番号が小さい順に全て求めよ。(ただしk=iのときの操作を操作iという)

考察

最初の提出

操作自体はシンプル.とにかく頂点0からはじめて隣にある頂点に順番に色を塗っていけばよいので,BFSかな?とすぐ察しがつきました.

で,最初の(ちゃんと)提出したコードがこちら

from collections import deque
#入力を受け取って,頂点と辺の情報をリストGに格納
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

#最初は頂点0から始める
print(0)
DONE[0] = True

#NEXTには,次の操作で色を塗る頂点を格納する.
#最初は頂点0と繋がっている頂点を格納しておく
NEXT = deque(G[0])
l = len(NEXT)

while l > 0:
    for _ in range(l):
 
   #NEXTから取り出して,表示,DONE[v]=True(頂点vに色を塗った)とする
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True

        #頂点vに色を塗ったので,vと繋がっている頂点をNEXTに格納する
        for x in G[v]:
            #すでに色が塗られている頂点と,すでにNEXTに格納されている頂点は除く
            if not DONE[x] and x not in set(NEXT):
                NEXT.append(x)
 
    l = len(NEXT)
    print()

5AC,3WA,2TLEでした.

まぁいろいろよくなかったです.すぐにわかることとして,出力条件の

k によって色が塗られた頂点を番号が小さい順に全て求めよ。

番号が小さい順という点を全く考慮していませんでした(読み飛ばしてしまっていました).実際,WAしたテストケースを見てみると

  • 入力
7 13
4 3
1 4
1 6
0 3
5 0
6 0
5 6
2 6
6 4
5 1
2 4
4 5
5 3
  • 上記コードの出力
0
3 5 6 
4 1 2 
  • 正しい出力
0
3 5 6
1 2 4 

となっており,出力の3行目の数字の順番が異なっています.

なので,NEXTに頂点を格納するときにソートしてやれば良いということになります.

次の提出

ということで実装したものがこちら

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])
l = len(NEXT)
while NEXT:
    tmp = []
    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True
        #vの隣接頂点のうちでまだ彩色されていない点をtmpに格納
        #NEXTはキューなのでソートできない
        for x in G[v]:
            if not DONE[x] and x not in NEXT and x not in tmp:
                tmp.append(x)
    tmp.sort()
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

としました.これで1ケースのみTLEであとはACしました.

注意 NEXTにキューを使う必要はありません.なぜかキューを使わないといけないと思い込んでいました.

最後の提出

このTLEがなかなかとれず,アルゴ式さんに

「できません〜」と泣きついたところ

f:id:masuTomo:20211031095842p:plain

さらに

f:id:masuTomo:20211031100025p:plain

ということで修正しました

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])
l = len(NEXT)
while NEXT:

    #tmpをセットに変更
    tmp = set()

    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True
        #vの隣接頂点のうちでまだ彩色されていない点をNEXTに格納
        for x in G[v]:
            if not DONE[x] and x not in set(NEXT) and x not in tmp:
                tmp.add(x)
    tmp = sorted(tmp)
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

まだTLEでしたが,たしかに実行時間で比べるとかなり早くなっていました.

また,このあと

f:id:masuTomo:20211031100444p:plain

f:id:masuTomo:20211031100525p:plain

とアドバイスをいただきました.

後半の

tmp に x を挿入する瞬間に DONE[x] = True にしてしまうことが考えられます!

の部分はおそらく自力では思いつけなかったのではないかと思います.だって,色を塗ったかどうかの判定をリストDONEに格納しています.色を塗ったあとでは遅いのです.NEXTに格納した瞬間に,色を塗ることは確定するのだからそのタイミングでTrueにせよ,と.難しいです.

DONEじゃなくてTODOの気持ちだそうです.

何はともあれ,実装しました.

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])

#ここも追記
for g in G[0]:
    DONE[g] = True

l = len(NEXT)

while NEXT:
    tmp = set()
    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ')

        #DONE[v] = True

        #vの隣接頂点のうちでまだ彩色されていない点をNEXTに格納
        for x in G[v]:
            if not DONE[x]:
                tmp.add(x)
                DONE[x] = True

    tmp = sorted(tmp)
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

無事ACです.

おわりに

アルゴ式さんのアドバイスによりなんとかACできました.ちなみに解説のコードはもっとすっきりしていました.(当然キューもつかっていない).

アルゴ式のテスターに選ばれました(10日目)

今後の方針

昨日,何とか動的計画法のコンテンツを終えたので,次にやるところをどこにしようか悩んでいましたが,アルゴ式さんから

「毎日アルゴ式」の過去問を埋めながら、日々の問題を並走していくのがよいと思います。

とアドバイスをいただいたので,素直に従って,

algo-method.com

をやることにしました.

進捗

貪欲法のQ1-1〜Q1-5をやりました.少し悩むところもありましたが,なんとか自力ACです.

それに加えて毎日アルゴ式の本日分(10/20)もやろうと思いましたが,ちょっと難しそうだったのでまたにすることにしました.

ちなみに,自力ACした問題の解説もきちんと読んでます(コードも含めて)

感想

貪欲法は実装自体はそんなに難しくないと言う印象ですが,貪欲法でやれば解を求めることができるということの証明の部分が難しいなと感じています.だから嘘解法しちゃうんだろうなあ.

今日はこれでおしまい

おまけ1

Macの変換って慣れないと難しいですね(すぐスペースで変換を押してしまう癖を抜けば便利そう)

おまけ2

統計検定2級の受験も予定しているのでそちらの勉強もせねばなりませんがサボっております.

アルゴ式のテスターに選ばれました(9日目)

進捗

数日詰まっていたQ3-6に何とかACし,勢いそのままにQ3-7もACしました!やった!!

Q3-6について

最初の実装

dp[i][j]はi番目までを使用しjを作れた場合は,j%Aの値.jを作れなかったときは-1.

N, A, B = map(int,input().split())
X = list(map(lambda x: int(x)%A  ,input().split()))
sumX = sum(X)
dp = [ [-1]*(sumX+1) for _ in range(N) ]
dp[0][0] = 0
dp[0][X[0]] = X[0]%A
for i in range(N-1):
    for j in range(sumX+1):
        if dp[i][j] != -1:
            dp[i+1][j] = dp[i][j]
            if j + X[i+1] <= sumX:
                dp[i+1][j+X[i+1]] = (j + X[i+1])%A
if B in set(dp[N-1]):
    print('Yes')
else:
    print('No')

結果

1TLEで,そのほかのケースはAC.

解決

自力解決とはいきませんでしたが,アルゴ式の公式アカウントさんに,進捗報告(TLEしたこと)をTwitterのDMでお伝えしたところ,提出コードを見てくださり,

「sumXがとても大きくなる場合にTLEしている様子ですね。」

と言う絶妙なヒントを頂いた.しかも,その後に続けて

「もしヒントなど必要であれば、その旨伝えていただけるとお教えいたします。」

とのことでした(ありがたい).

この絶妙なヒントを受けて落ち着いて考えてみました.

そもそも先の実装では,dp[i][j]においてiをNまで,jをsumXまでループさせていたので,もっとループ回数を減らすことを考えました.そこで自分のメモを見て次のことに気がつきました

f:id:masuTomo:20211019205033p:plain

なんだこれは,と言う感じかもしれませんが,これは入力サンプルのdpテーブルを書いたものです.これを書いているときに,横(jに相当)方向の値とjの値が一致していること,Aによる剰余をとっているので,表の中の値も0~A-1までしか取らないことに気づきました(最初に気づきましょうと言うのは置いておきましょう.あと,挿入した図はちょっとずれてますね)

と言うことは,jのループはsumXまでではなくて,Aまででもいいのでは?となり次の実装にしてみました.

N, A, B = map(int,input().split())
X = list(map(lambda x: int(x)%A  ,input().split()))
dp = [ [-1]*(A+1) for _ in range(N) ]
dp[0][0] = 0
dp[0][X[0]] = X[0]%A
for i in range(N-1):
    for j in range(A+1):
        if dp[i][j] != -1:
            dp[i+1][j] = dp[i][j]
            dp[i+1][(j+X[i+1])%A] = (j + X[i+1])%A

if B in set(dp[N-1]):
    print('Yes')
else:
    print('No')

このコードで無事ACです.

ちなみに,解説ではもっとスマートなdpテーブルの持ち方をしており,解説を読めばそりゃそうした方がいいよな,と納得感しかありませんでした.

Q3-7について

最初に手で計算しました. f:id:masuTomo:20211019205931p:plain

注:一番下の四角で囲んである一番大事な部分「W-dp[i][j]のMax」の部分は「W-2*dp[i][j]のMax」の間違いです.

幸いにもこの考察が正しかったようで割とスムーズにACできました.

N = int(input())
W = list(map(int, input().split()))
sumW = sum(W)
dp = [ [False]*(sumW//2 + 1) for _ in range(N)]
dp[0][0] = True
if W[0] <= sumW//2:
    dp[0][W[0]] = True

mx = 0
for i in range(N):
    for j in range(sumW//2 + 1):
        if i+1 < N:
            if not dp[i][j]:
                continue

            dp[i+1][j] = dp[i][j]

            if j+W[i+1] <= sumW//2:
                dp[i+1][j+W[i+1]] = True
                mx = max(j+W[i+1],mx)
print(sumW-2*mx)

ただこれも解説の方法とは違っていました.解説の方法も勉強しておかなくちゃと言う感じですが,とりあえず解けたので嬉しいです.

感想

とりあえずアルゴ式の動的計画法の最初のコンテンツがなんとか終了しました.せっかくなのでこのまま続けて【特集】典型的な動的計画法のパターンを整理 ~ ナップサック DP 編 ~をやろうかなぁと思っていますが,違うところも興味あるので悩ましです.整数論のところとかやりたいなぁ.

あと,記事の途中にアルゴ式さんとのDMのくだりを書きましたが,ヒントを与えるということに対するスタンスがとても教育的でありがたかったです.

まだまだ頑張るぞ

アルゴ式のテスターに選ばれました(8日目)

昨日からやっている問題に改めて挑戦した.

挑戦した問題はこちら

結論から言うとできていません.とりあえず愚直に実装したらTLEでした.

N, A, B = map(int,input().split())
X = list(map(lambda x: int(x)%A  ,input().split()))
sumX = sum(X)
dp = [ [-1]*(sumX+1) for _ in range(N) ]
dp[0][0] = 0
dp[0][X[0]] = X[0]%A
for i in range(N-1):
    for j in range(sumX+1):
        if dp[i][j] != -1:
            dp[i+1][j] = dp[i][j]
            if j + X[i+1] <= sumX:
                dp[i+1][j+X[i+1]] = (j + X[i+1])%A
if B in set(dp[N-1]):
    print('Yes')
else:
    print('No')

アルゴ式のテスターに選ばれました(5〜7日目)

進捗

土日はあまり進捗がありませんでした. Q3-4,Q3-5の二問を解きました.

Q3-6もやりましたが,解けませんでした....むむむ algo-method.com

考えていること

Q3-4,3-5は置いておいて,Q3-6で考えていることを書き留めておこうと思います.

  • 問題設定は分かっている(つもり)

  •  modとかも知っている

  • 和がMになるかどうか,という問題設定はQ3-2でやった

  • dpテーブルがうまく作れない

個人的に,dpテーブルがうまく作れれば解決するんだろうと思っている.たとえば dp(i,j) =  i番目までのカードを使って,重さjが作れるかどうか,としたのがQ3-2であったから, dp(i,j) =  i番目までのカードを使って, i=B (mod A) となるかどうかとすれば良いのか?

True,Falseの真偽値を保持しておいて, dp(i,j)=Trueのときに, X _{i+1} = B (mod A)かどうかを調べて dp(i+1, j+X_{i+1}) の値を決定する?

いや,Falseのときダメじゃない?Falseだったら前回の値を保持しておかないと次の値を計算できないよね. うーむ...

終わりに

MacbookAirが届きました.キーボードに慣れないと入力しにくいですね.

アルゴ式のテスターに選ばれました(4日目)

今日はやるだけにして書かないつもりでしたがやっぱり書きます.

進捗

動的計画法Q3-1,Q3-2をやりました. Q3-1はスムーズに解けましたが,Q3-2は2時間くらい悩んだと思います.

感想

Q3-2の問題はタイトルの通り,本当によく見るDPの問題でした.もちろん以前どこかで(多分EDPC)解こうとしたり解説を読んだりしたことがあります.ただ,今回は調べずに(アルゴ式を信じて)この3日でやってきたことを利用できないかという観点で考えました(邪道と言えば邪道かもしれない).

最初はdp[i][j]のようなリストを考えて,ボールiを箱に入れた時の重さを表して...などと考えていましたがうまくいきそうにありません(漸化式がたてれない).いろいろ考えるうちにdp[i]は重さiが(ボールの組み合わせで)作れるかどうか,というようにすればよいのではないかと考えました.そこからもう少し考えを進めて(DPの問題なのだからそこを利用すると...と考えました)dp[i][j]で最初のj個のボールを使って重さ[i]が作れるかを表せばうまくいきそうだと気づきました.

ここまで考えて,最初にやったQ3-1と同じ形の遷移になっていることにも気づくことができました.そうしたらあとは実装するだけなので(といってもここも少し手間取りました)無事ACを取ることができました.

N, M = map(int,input().split())
W = list(map(int,input().split()))
dp = [ [False]*(M+1) for _ in range(N)]
dp[0][0] = True

for i in range(N):
    for m in range(M):
        if dp[i][m]:
            if m+W[i] < M:
                dp[i][m+W[i]] = True
            elif m+W[i] == M:
                print('Yes')
                exit()
                
            if i+1 < N:
                dp[i+1][m] = True
                if m+W[i+1] < M:
                    dp[i+1][m+W[i+1]] = True

print('No')

ポイント

自分の中で2点ポイントになったことがあると感じています.1点目は事前にQ3-1が用意されていたことです.Q3-1の構造が頭にあったので,Q3-2のdp[i][j]を思いついたときに,この方法で答えを求めることができる,という確信につながりました.

2点目は重さを連続量だと考えないことです.自分の中でQ3-2で難しいと感じている点は「重さ」と「リストの添え字部分」を対応させるというところです.おそらくその理由の一つが,重さを連続量だと思っていて(一般的にはその通りだが,この問題では離散量と考えて良い),リストの添え字として使えるという発想に至るのに時間がかかったような気がしました.

あんまりわかっていないこと

TLEするような解法ってどんなのがあるんでしたっけ?

おわりに

明日,MacbookAirが届く予定です.