AtCoderでついに入緑しました！！！

AtCoder最高！！！

どうも皆さんこんにちは。
先日行われた 第二回日本最強プログラマー学生選手権 でついに緑コーダーになることが出来ました！！！

入緑しました！

本当に長い道のりでしたし、とても嬉しかったです！！

そこで今回はこれまでの過程や自分なりのアドバイスが出来ればなと思って記事を書いていこうと思います！

目次

1. 自己紹介

• 所属：公立はこだて未来大学（FUN）　B3
• 競プロ歴：１０ヶ月程度
• AtCoder：AtCoderのアカウント　自分のレートの遷移図が見れます！
• Twitter：Twitterのアカウント　フォローお待ちしております！
• GitHub：GitHubのアカウント　AtCoderのライブラリや典型90問のPythonコードなども上げてるのでチェックしてみて！
• OMC：OMCのアカウント　世間ではなぜか数強と呼ばれています...

2. 緑色の実力について

AtCoderの緑色（レートが800〜1199）の実力についてはAtCoder社 社長であるchokudaiさんが下記のように評価しています↓↓

詳しく見たい方はこちら！

緑色　(Cランク R800~1199　上位30%)

緑色になれれば、「競技プログラミングに熱心に取り組んでいる人」と考えて問題ないでしょう。要求レベルも決して低くなく、出場回数が足りないとマイナス補正がかかるため、運だけで到達することはまず出来ないラインです。他社アルゴリズム力判定サービスだと、上位１％の最高ランクが付く実力です。（あくまで「アルゴリズム力部分だけであることに注意してください）

印象としては、

• 学生ならかなり優秀。
• エンジニアとしてもある程度の安心感がある。論理的に複雑な処理の実装に対応できない、なんてことはなさそう、くらいには思える。データ量が多い現場など、計算量の多い処理が要求される現場でなければ、このレート帯以上を求める必要はほぼない。

くらいの印象です。もちろんアルゴリズム力しか計ってないので個人差があります。

技術的な部分では、

• if、forはもちろん、それを組み合わせて2次元配列に対して操作をしたり、深さ優先探索や幅優先探索などのキューや再帰を使った実装も出来る。
• 簡単な動的計画法の問題や、数学的に工夫する問題など、計算量の工夫も出来始める。

という感じです。

こんな感じで書かれていますが、実際の所、本当にこのような感じだと思います。

最近のAtCoder界隈では、「参加者のインフレが高くてレートが上がらない」や「昔ならもっとdiff（各問題の難易度を表す指標のようなもの）が低いだろ」などの意見も頻繁に聞きます。

確かに、昔よりかはレートを上げるのが難しくなっているような感じはしますが、緑に必要なアルゴリズムの典型はそんなに多くないと思います。

3. 緑色になるまでに取り組んできたこと

まずは、入茶した日（2020/09/19）から、今日(2021/04/17)に至るまでに精進してきたことを紹介したいと思います。
ここで話す内容がとても大事だと思うので、ぜひ読んでいただけると幸いです。

取り組んだ内容	期間	重要度
AtCoderの茶色全埋め	最初の１ヶ月	低
初中級者が解くべき過去問精選 100 問（後ほど解説）を全埋めしたがる	最初の２ヶ月	高
AtCoderの緑diff100問以上AC	茶色全埋め後から１ヶ月半	高
競プロ典型90問（後ほど解説）に挑戦	直近１週間	高
毎日精進（連続Streakの記録伸ばし）	入茶する前から１年ほど	超絶低

上記の表について軽く解説したいと思います。

AtCoderの茶色全埋め

これは正直あまりやる必要がないと思います。
自分がやろうと思った経緯については、茶色になったし、茶色の問題を全部溶けるレベルにしないとレートが上がらないよなーと思い全埋めをしました。
しかし、これよりも緑や水の問題をもっと解くべきだったと思います。
難易度の高い問題を優先して解いていけば、必然的に茶や灰の問題はスムーズに解けるようになると思います。

初中級者が解くべき過去問精選 100 問 を全埋めしたがる

このまとめられた問題集はとても良いと思いました！！
アルゴリズムを学ぶ際に、学びたいアルゴリズムを利用した問題がたくさん用意されているからです。

しかし、自分のような進め方でやっていくと確実に効率が悪いです。自分がどのようにやったかというと、何がなんでも順番に進めていくということです。

精選100問の中には平気で青や黄レベルの問題が含まれており、自分はその問題に出くわしたら解くまで、理解するまで次には進みませんでした。その結果、区間 DP, bit DP の分野で挫折して諦めてしまいました。（今はボチボチ再開してます。）

つまり、何が言いたいかと言うと、難しい問題に出会ったらとりあえず解説AC（答えを見てなるほどーって軽い気持ちで写経してAC）をして、とにかく100問最後まで解ききると言うのが大切だと思います！！

そうすると、とりあえずは基本的な全てのアルゴリズムを知ったことになるので、普段のコンテストの解説を見て「全くわからない...」ということは起きなくなるだろうし、典型問題だったら簡単にACできると思うので、ぜひ最後までやり切って見て下さい！！

AtCoderの緑diff100問以上AC

これは、精選100問を行いながら同時進行で進めていました。
最近は貼っていませんが、 精進ツリー もTwitterに作ってモチベーションを保っていました。

感想としては、とてもやる意義があったと思います。やはり、緑は自分が目指していた問題なので、それを解くことで緑のレベルを知ることが出来るし、とても効率の良い勉強法ではなかったのでは？と自分では思ってます。

ただ、先ほどと同様に全部を埋める必要はないです。中にはとても難しい緑の問題や、昔の問題でとても簡単なのに緑になっている問題も存在するので、最近の緑の問題を埋めるのがとても効率が良い気がします！

競プロ典型90問 に挑戦

これは５日前くらいから始めたのですが、とても良いと思います！！
こちらも精選100問と同様に典型の問題がたくさんオリジナルで作られているのでぜひやってみると良いと思います！

また、毎日の解説に記載されている類題も解いてみるととても力が付くような気がします。

下記のリンクにPythonのコードを少しずつ載せているので、興味のある方は是非ご覧ください！

github.com

毎日精進（連続Streakの記録伸ばし）

これが一番伝えたかったことです！！！！
特に灰や茶の人（自分もそうでした）でよく見かけますが、

レートを伸ばしたい方が、Streakの記録を伸ばしたいがために、毎日ACするのは絶対に良くないと思います！！！！！！！！！！！

まず、誤解があるといけないので伝えておくと、例えばとても時間があり、難しい問題（自分のレートよりも1, 2色以上の問題）を毎日解き続けている方なら問題ないし、むしろ良いと思います。
だって難しい問題を毎日解いてるんですもの。絶対に報われるじゃないですか...

自分が言いたいことは何かというと、自分のように力もつかないような（自分の色よりも下の色の問題）を解くのは絶対に効率が悪いと言うことです。
確かに競技プログラミングをするという習慣はつきます。しかし、そのせいで私生活に影響が出たりもしてきます。

なんか300日連続ACしてました。
AtCoder神ゲーかよ pic.twitter.com/K2gc36CIAM

— カイリュー (@ryusuke__h) 2021年2月25日

自分はなんか２月にこんなツイートをしてイキッていましたが、300日連続ACを達成するために、どんなに忙しい日でも簡単な問題を解く、簡単な問題が無くなったら AtCoder Problems の Other Contests からひたすら探す、と言う感じでとにかく毎日続けていました...

しかし冷静に考えて、自分にとって簡単な問題は解いた所で力が付く訳ないじゃないですか？
もし付いても糧となる経験値は少なそうですし...
簡単な問題をやるなら、どこかまとまった日にでも 50問くらい一気にやってしまえば良いんじゃないですか？と思いましたし、300日前の自分に聞かせてあげたいです。

だから、これ以降は自分（該当する読者の方で賛同して下さっている方がいるならその方も）は出来る日に、時間のある日に問題を解いて、特に難しい問題、まだ自分の知らないアルゴリズムを勉強する、こういった姿勢がレートが上がる最善策ではないのかと思います。

悪魔でも、上記の文章は自分の個人的な考えなので 「当てはまらない・そうでもないわ。」 などと思った方は無視していただいて全く問題ありません。
実際に、この話題についても賛否両論の意見があると思うので！

4. 学んだアルゴリズムについて

学んだアルゴリズムは下記の表の通りです。

理解度

理解度の種別について	説明
◎	理解してるので、何も見ずに書けるし、テンプレートもある
△	テンプレートがあるのみで、無いと書けない。典型問題なら解ける
×	聞いたことしかない
茶	茶色になる以前から身に付けていたアルゴリズム

重要度

※重要度は、緑色になるために必要なアルゴリズムかということです。決して競技プログラミングをやる上で知らなくても良いというわけではありません！！
また、完全に個人的な主観となっていますのでご了承ください。

アルゴリズム	理解度（◎・△・×・茶）	重要度（高・中・低）
最大公約数, 最小公倍数	茶	高
高速素数判定	茶	高
エラトステネスの篩	◎	中
素因数分解	茶	高
約数列挙	茶	高
半分全列挙	△	低
累積和	茶	高
いもす法	◎	高
高速な冪乗計算	◎	中
逆元の利用	×	低
bit全探索	茶	高
二分探索	△	中
幅優先探索(BFS)	◎	高
深さ優先探索(DFS)	◎	高
DP := 動的計画法（基本的な問題）	◎	中
区間 DP	×	低
bit DP	×	低
ダイクストラ法	◎	中
ワーシャルフロイド法	△	低
ダブリング	△	低
クラスカル法	×	低
RLE := RunLengthEncoding	◎	低
LCS := LongestCommonSubsequence（最長共通部分文字列）	◎	低
LIS := LongestIncreasingSubsequence（最長増加部分列）	◎	低
Union-Find木	◎	高
座圧	◎	中
行列累乗	×	低
Rolling Hash	×	低
平方分割	×	低
最大流／最小カット	×	低
Grundy 数	×	低
BIT := Binary Indexed Tree	×	低
RMQ := Range Minimum Query	×	低
遅延評価セグメント木	×	低

こう見てみると、とてもアルゴリズムって多いんですね...

灰時代では知らなかったアルゴリズムもたくさんありました。
灰・茶で「緑行けないよー」と言う方は一つの参考にしていただければ幸いです。

水に行くまでには下の全滅してるアルゴリズム 7, 8個を確実にマスターして入水したいです！

5. 各種実績について

AtCoder Problemsにて掲載されているデータを載せておきます。

Achievement

achievment

AtCoder Pie Charts

Pie Charts

Difficulty Pies

Difficulty Pies

Daily Effort

Daily Effort

Climbing

Climbing

Heatmap

Heatmap

Languages

Languages

基本的にはPythonですが、Pythonだとループの時間が遅く TLE になりやすい（自分が実装下手なだけです...）ので、最近では PyPy を併用して使っています。

6. モチベーションの維持について

競技プログラミングを行う上でよく話題になるのが、モチベーションの維持です。
自分はメンタルが強いのか、一度もモチベが下がったり、落ち込んでしまったりしたことはありませんが、話題になっているので少しだけお話しします。

周りの初心者が強すぎて、メンタルがやられてしまう場合

と言うのもAtCoderではとても能力・才能の高い初心者の方が山のようにおられ、そういった方が後から始めたにも関わらず、平気で自分のレートを越していきます。

こういう方を見て、自分のメンタルがやられてしまう方（自分は全くならないです。）は、

・その方をミュートにする
・今までAtCoderをやって来てないだけで、自分よりもアルゴリズムに詳しい
・最悪の場合、ブロ解（ブロックをして解除することで、フォローを外すことが出来ます。）を行う。

などと言った思考・処置をすればこういう被害は削減できると思います。

以降は完全な個人的な見解ですが、メンタルがやられてしまう方の場合、自分が１番だと思ってませんか？
なので後から入って来た人が、自分を超えると「なんで自分は置いていかれるんだ？」となってしまうのだと考えています。
上には上がいるといつも考えると楽になるのではないでしょうか？ならなかったらごめんなさい。

自分も数学は平均以上には出来る方だとは自負しており、良く水色の方などに、「いつになったら入緑しますか？」とか「なんで茶色から上がれないんですか？」などと言ったような、心配や煽り（自分には今後もしていただいて、全く問題ないです。むしろ煽って来て下さい。）の声を毎週のように聞いていました。

レートが伸びず、メンタルがやられてしまう場合

それから単純に伸び悩んでいる方でメンタルがやられる方も多いと思います。
確かに問題の愛称はとても大きく影響してくると思います。
ですが、昨日の自分よりは、今日の自分の方が経験値が豊富のはずなので、最後まで諦めずに頑張ってほしいです。

7. 最後に振り返って

だいぶ長くなってしまいましたが、いかがでしたか？？
色変記事は２回目で少しは書き慣れましたが、まだまだ至らない点が多いと思います。
次の目標はいよいよ最初に自分が立てた最終目標の水色です！

頑張って入水出来るように頑張りますので応援よろしくお願いします！！！！

最後までありがとうございました！

Atcoder Beginner Contests 195 に参加しました！！

皆さんこんにちは！
今回は昨日行われた パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） の感想を載せて行きたいと思います！

目次

A - Health M Death / Difficulty: 5 / 灰

atcoder.jp

A問題の難易度に関してはいつも通りといった感じでしたね。
迷った部分としては、A, Bは問題文あまり読んでいないので
M % H なのか H % M なのかでちょっと考えました。
でも、入力例に H は M の倍数であるのでといった感じのニュアンスが読み取れたのですぐくAC出来ました。

m,h = map(int,input().split())
if h % m == 0:
    print("Yes")
else:
    print("No")

B - Many Oranges / Difficulty: 483 / 茶

atcoder.jp

さて、今回のメインディッシュはこちらの問題でしょうか。
なんとB問題に茶色Diffが来ました！！
調べて見た所B問題が茶色以上なのは ABC107以来 / 2年半ぶり程 の出来事でした！！
どうせいつも通りBまではすんなり行くと思っててCでややこしいのが来るのかなと考えていたので、Bで考える問題が来て驚きました。

解法については、まずどのような場合において "UNSATISFIABLE" となってしまうのかを考えます。

ここで、入力例3を見て見ましょう。

みかんの個数を n とすると、

n = 1のとき、買うことのできる範囲は 300 以上 333 以下です。
n = 2のとき、買うことのできる範囲は 600 以上 666 以下です。
n = 3のとき、買うことのできる範囲は 900 以上 999 以下です。
...
...
n = k - 1のとき、買うことのできる範囲は 300 * (k - 1) 以上 333 * (k - 1) 以下です。
n = kのとき、買うことのできる範囲は 300 * k 以上 333 * k 以下です。

つまり、ここの範囲内に W(kg) が入っていなければ、答えは "UNSATISFIABLE" となります。
ここまでこれば、後一歩です。次に考えるべきポイントは買うことのできる最小値、最大値はいくらであるかということです。
すると先程の上記の図を見てください。
一般に k 個買ったときの最小値は 300 * k なのでそれよりも少ない数で買うことは出来ません。
なので、300 * k <= 100 * A となったタイミングが最小値の答えとなり、300 * k >= B となったタイミングが最大値の答えとなります。

a, b, w = map(int,input().split())
w *= 1000 # gに変換する
cnt = 0
# 以下、maが最小値、miが最大値を表しています。逆になっててすみません...
ma = mi = -1
for i in range(10 ** 7):
    x = a * (i + 1)
    y = b * (i + 1)
    if x <= w <= y and ma == -1:
        ma = i + 1
    if ma != -1 and x > w and mi == -1:
        mi = i

if ma == -1 or mi == -1:
    print("UNSATISFIABLE")
else:
    print(ma, mi)

C - Comma / Difficulty: 265 / 灰

atcoder.jp

次はC問題です。
この問題は結論から言えば、 ”筋肉しか勝たん” です。

コンマの必要な数について場合分けをして見ましょう。

1 <= n <= 999 のとき、必要なコンマの数は 0 個
1,000 <= n <= 999,999 のとき、必要なコンマの数は 1 個
1,000,000 <= n <= 999,999,999 のとき、必要なコンマの数は 2 個
1,000,000,000 <= n <= 999,999,999,999 のとき、必要なコンマの数は 3 個
1,000,000,000,000 <= n <= 999,999,999,999,999 のとき、必要なコンマの数は 4 個
n = 1,000,000,000,000,000 のとき、必要なコンマの数は 5 個

という考察結果が得られるのであとは 0 の数を間違えないように気をつけて判別すれば終わりです。

n = int(input())
if 1 <= n <= 999:
    print(0)
elif 1000 <= n <= 10 ** 6 - 1:
    print(n - 1000 + 1)
elif 10 ** 6 <= n <= 10 ** 9 - 1:
    print(999000 + (n - 10 ** 6 + 1) * 2)
elif 10 ** 9 <= n <= 10 ** 12 - 1:
    print(999999 - 1000 + 1 + (999999999 - 1000000 + 1) * 2 + (n - 1000000000 + 1) * 3)
elif 10 ** 12 <= n <= 10 ** 15 - 1:
    print(999999 - 1000 + 1 + (999999999 - 1000000 + 1) * 2 + (999999999999 - 1000000000 + 1) * 3 + (n - 10 ** 12 + 1) * 4)
else:
    print(999999 - 1000 + 1 + (999999999 - 1000000 + 1) * 2 + (999999999999 - 1000000000 + 1) * 3 + (999999999999999 - 10 ** 12 + 1) * 4 + 5)

D - Shipping Center / Difficulty: 945 / 緑

atcoder.jp

続いてD問題です。
Cまで解き終わった時点でまだ1時間ほどあったので解きたかったですが、解けませんでした。
終わった後に解くことができたのでコードだけ貼っておきます。

方針としては、貪欲法で解くことができます。荷物を入れられる箱のうち、重さ制限の小さいものからできる限り大きなものを入れていくといった方針でACすることができます。方針は簡単ですが、実装がやや複雑な気がします。

import sys
input = sys.stdin.readline
n, m, q = map(int,input().split()) # 荷物、はこ、クエリ
w, v = [0] * n, [0] * n # 大きさ、価値

for i in range(n):
    w[i], v[i] = map(int,input().split())

x = list(map(int,input().split()))

for i in range(q):
    box = [[True, 0] for _ in range(m)] # 荷物が入るかの有無・入る量
    l, r = map(int,input().split())
    # 箱に入れられるかの判定
    for j in range(l, r + 1):
        box[j - 1][0] = False
    # 荷物の入れられる最大値の判定
    for j in range(m):
        box[j][1] = x[j]
    box.sort(key = lambda x: x[1])

    nimotu = [[0, 0, True] for _ in range(n)] # 荷物の大きさ、価値、詰めたかどうかの有無
    for j in range(n):
        nimotu[j][0], nimotu[j][1] = w[j], v[j]
    # 価値の大きい順にソート
    nimotu.sort(key = lambda x: x[1], reverse = True)
    ans = 0
    for j in range(m):
        if box[j][0] == False: continue # 使えない箱だったらスルー
        for k in range(n): # 入れれる箱の場合どの荷物を詰めるかを見ていく
            if nimotu[k][2] == True and box[j][1] >= nimotu[k][0]:
                nimotu[k][2] = False
                ans += nimotu[k][1]
                break
    print(ans)

E - Lucky 7 Battle / Difficulty: 1609 / 青

atcoder.jp

全く問題すら見ていません。ここまでいけるようになりたいです。

F - Coprime Present / Difficulty: 2068 / 黄

atcoder.jp

こちらに関しても問題すら見ていません。
なにやら既出の問題だったそうですね。精進すると既出の問題が増えそうなので継続して今後も精進して行きたいです...

コンテスト結果

今回のコンテスト結果は以下のような結果となりました。

ABC195のコンテスト結果

Dも解けたかもしれなかったので残念です。次回こそは４完します！！！

それにしても緑パフォ取りまくってるのに茶コーダーというのはなかなか面白いですね（）

永年茶コーダー

最後に

ほんとに緑まで後ちょっとです。本日のARCには参加できませんが、とにかく早く緑に行きたいです。
よければ応援よろしくお願いします！

初中級者が解くべき過去問精選 100 問 茶コーダーが解いてみた #8 ( 動的計画法：ナップザック DP 編 )

今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います！

精選100問って何？

記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。

今回は第８回目の動的計画法：ナップザック DP！！

過去の記事についてはこちら！！

全探索シリーズ

第１回：全列挙

ryusuke920.hatenablog.jp

第２回：工夫して通り数を減らす全列挙

ryusuke920.hatenablog.jp

第３回：ビット全探索

ryusuke920.hatenablog.jp

第４回：順列全探索

ryusuke920.hatenablog.jp

二分探索

第５回：二分探索

ryusuke920.hatenablog.jp

深さ優先探索

第６回：深さ優先探索

ryusuke920.hatenablog.jp

幅優先探索

第７回：幅優先探索

ryusuke920.hatenablog.jp

動的計画法：ナップザック DP

動的計画法：ナップザック DPの分野は全部で５問あるので、紹介したいと思います！

34. Fibonacci Number

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_A&lang=ja

フィボナッチ数列の問題です。
再帰で解くこともできますが、制限時間以内には間に合わないのでこう言う場合にDPを使うようです。
まだまだDPは難しく感じますが、少しずつ慣れていきたいですね...

n = int(input())
dp = [0] * (n + 1)
(dp[0], dp[1]) = (1, 1)
def fibonacci(x):
    for i in range(2, x + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[x]

print(fibonacci(n))

35. 0-1 Knapsack Problem

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B&lang=ja

これがいわゆるナップザックDPと呼ばれる問題のようです。
最初にナップザックDPと聞いた際は、なんのことかわかりませんでした。
ナップザックの中にどれくらい詰めるかと言うことからこの名前がついているんですかね
（根拠はないです。）

先ほどのフィボナッチ数列の問題のように１次元のDPでは重さの制限をつけることが難しいので、２次元配列で解くことが出来ます。

ここら辺からもうわかんないです。

n, w = map(int, input().split())
v = [0] * n # 品物の価値
t = [0] * n # 重さ
for i in range(n):
    v[i], t[i] = map(int, input().split())
dp = [[0] * (w + 1) for _ in range(n + 1)] # （価値 * 重さ）
for i in range(n):
    for j in range(w + 1):
        if j < t[i]: # 追加できないとき
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - t[i]] + v[i])
print(dp[n][w])

36. Knapsack Problem

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_C&lang=ja

先ほどの問題とめっちゃ似ていますね。
何が違うのか気づくのに１０分くらいかかってしましました。今回の問題は同じ品物をいくつでも入れることができるらしいですね。

なので、解法としては先ほどの問題のdpの遷移の条件に加えて

dp[i + 1][j - w[i]]

と言ったような条件式を加えてあげるとAC出来ます!!
（詳細は日本語が下手でできないので省略...）

n, W = map(int,input().split())
v = [0] * n # 価値
w = [0] * n # 重さ
for i in range(n):
    v[i], w[i] = map(int,input().split())
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i], dp[i][j - w[i]] + v[i])
print(dp[n][W])

37. Coin Changing Problem

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=ja

今度はコインの問題ですね。
dp[j] と言うのを j 円 を作るのに必要な最小のコイン枚数と定義してあげることで１次元のDPとして扱えます。

なんかよくわかんないけど難しいのには変わりないよね...
DPはとりあえずどう定義してあげるかが重要だなと感じました。

n, m = map(int,input().split())
c = list(map(int,input().split()))
dp = [10 ** 18] * (n + 1)
dp[0] = 0
for i in range(m):
    for j in range(n + 1):
        if j >= c[i]:
            dp[j] = min(dp[j], dp[j - c[i]] + 1)
print(dp[n])

38. Longest Common Subsequence

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C&lang=ja

俗に言う LCS(Longest Common Subsequence) の問題です。
TLなどではよくワードを見かけていましたが、意味を知らなかったので理解できてとても嬉しいです！
感想としては、「結構考える上に実装が重い！！」
と言った感じでした。
なのでライブラリとして保存している方もよく見かけるので自分も近いうちにやっておきたいです。

解法としては、

dp[i][j] := sのi番目、tのj番目までで作れる最大共通部分列文字列

と定義してあげて、DPの遷移を考えていきます。
方針は立ちましたが、上位勢の方にアドバイスをいただきながら、ACしました。
典型問題のようなので、近いうちにもう一度解き直しておきたい所です。

import sys
input = sys.stdin.readline
q = int(input().rstrip())
for i in range(q):
    s = input().rstrip()
    t = input().rstrip()
    # dp[i][j] := sのi番目、tのj番目までで作れる最大共通部分列文字列
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i + 1][j], dp[i][j + 1])
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
    print(dp[len(s)][len(t)])

最後に

DPを避け続けてしまったせいで、投稿がとても遅くなってしまいました。（１ヶ月以上空いた？）
今度の 動的計画法：ナップザック DP の亜種編では投稿したいのは山々ですが、最後の2問がやばいらしい（緑や水の人が言ってるからそう言うことらしい）のでたぶん投稿自体は飛ばすことになると思います。

なので次回は 動的計画法：区間 DP になると思います。（これもめっちゃ難しいらしい）
遅くなると思いますが、よろしくお願いします！！

誤字脱字や間違い等ありましたら、DM等よろしくお願いいたします。
ありがとうございました！

Atcoder Beginner Contests 194 C - Squared Error (Python 3.8.2)

皆さんお久しぶりです！！
今日はなんとなく記事を書きたい気分になったので書きたいと思います。

問題はこちら！！

atcoder.jp

考察

見た瞬間に「これ類題あるやん〜〜〜」ってなりましたね。

その類題はこちら

atcoder.jp

これを解いた際には少し時間がかかってしまいましたが、結論から言うとこの問題を解くカギは累積和です！

解法

とりあえず眺めててもわからないので具体例を考えてみる。

• n = 4のとき

といったような式が出てきます。
前半の２乗の部分はO(N)で計算することができ、後ろの一つずつ項が小さくなっていくものは前処理で累積和を取っておくとO(N)で計算することが可能です。

一般にnのときでやってみると以下のようになります。

が得られるのであとはこれを累積和を用いて計算するだけです！！

提出コード

n = int(input())
a = list(map(int,input().split()))
b = [0] * n

# Bnを後ろから累積和を取る
for i in range(n):
    b[i] = a[i]
b = b[::-1]
wa = [0] * n
wa[0] = b[0]
for i in range(n - 1):
    wa[i + 1] += wa[i] + b[i + 1]

x = y = z = 0
for i in range(n - 1):
    x += (n - 1 - i) * (a[i] ** 2)

for i in range(n - 1):
    y -= 2 * a[i] * (wa[-2 - i])

for i in range(n  - 1):
    z += (i + 1) * (a[i + 1] ** 2)

print(x + y + z)

最後に

今回の問題は前回の復習が生きたおかげで速く解くことができたのでよかったです！！
今後も数問にはたくさん挑戦して慣れていきたいものです。

間違いなどがあれば指摘の方をよろしくお願いします。
ありがとうございました！

AtCoderで1000ACしたけど？？

こんばんは〜〜

2021 / 1 / 27 にAtCoderで1000ACしました！

1000AC記念撮影

いつになったら入緑できますか？？？
黙って精進しますーー

初中級者が解くべき過去問精選 100 問 茶コーダーが解いてみた #7 ( 幅優先探索（BFS）編 )

今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います！

精選100問って何？

記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。

今回は第７回目の幅優先探索！！

過去の記事についてはこちら！！

全探索シリーズ

第１回：全列挙

ryusuke920.hatenablog.jp

第２回：工夫して通り数を減らす全列挙

ryusuke920.hatenablog.jp

第３回：ビット全探索

ryusuke920.hatenablog.jp

第４回：順列全探索

ryusuke920.hatenablog.jp

二分探索

第５回：二分探索

ryusuke920.hatenablog.jp

深さ優先探索

第６回：深さ優先探索

ryusuke920.hatenablog.jp

幅優先探索

幅優先探索の分野は全部で６問あるので、紹介したいと思います！

28. Breadth First Search

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=ja

この問題は「The 最初の問題」という感じがしました。
方針としては頂点０からスタートして、行ける場合には今いる頂点 +1 にして解いていきます。
すると、その頂点までの最小値が記録されていきます！

from collections import deque
n = int(input())
graph = [[] for _ in range(n)] # 隣接リスト
for i in range(n):
    a = list(map(int,input().split()))
    for j in range(a[1]):
        graph[a[0] - 1].append(a[j + 2] - 1)

dist = [-1] * n
dist[0] = 0 # 頂点０→０の距離は当然０
q = deque()
q.append(0)
while q:
    v = q.popleft()
    for i in graph[v]:
        if dist[i] == -1: # まだ行ってない所であれば今いる頂点 + 1をした距離が最小値となる
            dist[i] = dist[v] + 1
            q.append(i) # qに距離を記録した頂点を追加する

for i in range(n):
    print(i + 1, dist[i])

29. C - 幅優先探索

https://atcoder.jp/contests/abc007/tasks/abc007_3

この問題はAtCoderの中でもとても有名な問題ですね。
これがスラスラ書けるようになると、アルゴリズムの視野がとても広くなる気がします。

方針は至って単純で今いる場所から４方向に向かって行けるかどうかを判定する。
行ける場合には今いるマス +1 をしてあげることで判別することができます。

最近のAtCoderはこのようなアルゴリズムの問題があまり出題されてないので近い時期に出そうですね！！

from collections import deque
r, c = map(int,input().split())
sy, sx = map(int,input().split())
gy, gx = map(int,input().split())
(sy, sx, gy, gx) = (sy - 1, sx - 1, gy - 1, gx - 1) # 0indexで設定する
grid = [[] for _ in range(r)] # r * cのgridマスを用意する
for i in range(r):
    C = list(input())
    for j in range(c):
        grid[i] = C

dist = [[10000] * c for _ in range(r)] # 各マスの最小距離を記録する２次元配列
for i in range(r):
    for j in range(c):
        if grid[i][j] == "#": # gridマスが # になっている場合は通れないので便宜上 -1 とする
            dist[i][j] = -1
dist[sy][sx] = 0 # スタート地点は０距離で行ける

q = deque()
q.append([sy, sx]) # (スタートのy座標, スタートのx座標)
d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # ４方向への変化量

while q:
    v = q.popleft() # (今いるy座標, 今いるx座標)
    for i, j in d: # 変化量を足していく（配列の長さである4回分）
        if not (0 <= v[0] + i <= r - 1 and 0 <= v[1] + j <= c - 1): continue # 変化量を足した際に配列外になる場合は調べない
        if grid[v[0] + i][v[1] + j] == "#": continue # マスが通れない場合は当然調べない
        if dist[v[0] + i][v[1] + j] != 10000: continue # 10000でなければ既に調べたか行けない場所なので調べない
        dist[v[0] + i][v[1] + j] = dist[v[0]][v[1]] + 1
        q.append([v[0] + i, v[1] + j]) # 次に行く場所をdequeに追加する

print(dist[gy][gx]) # ゴールのマスを出力してAC！！

30. E - チーズ (Cheese)

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_e

これは難しかった！！
しかししばらく考えてみると意外と単純で、上記で解いた問題はスタートとゴールが決まった１カ所でしたが、この問題はそれがn回出てくるだけです。
なのでfor文をn回してBFSをすればAC出来ます！！

from collections import deque
h, w, n = map(int,input().split()) # gridマスの縦、横、チーズの数
grid = [[] for _ in range(h)]
for i in range(h):
    S = list(input())
    grid[i] = S

num = [str(i + 1) for i in range(n)] # チーズを探す際に作っておくと楽になる
q = deque() # (y, x)
cheese = [[0, 0] for _ in range(n)] # それぞれのチーズのある場所を記録する配列（y座標・x座標）
for i in range(h):
    for j in range(w):
        for k in range(n):
            if grid[i][j] == num[k]:
                (cheese[k][0], cheese[k][1]) = (i, j) # それぞれの番号（チーズ）がある場所を記録する
        if grid[i][j] == "S": # スタート地点をdequeに追加する
            q.append([i, j])

d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # ４方向への変化量
ans = 0 # 距離を足していくもの（いわゆる答え）
for k in range(n): # n回分チーズを食べる
    if k != 0: # i == 0 のときは既に16, 17行目でdequeに追加している
        q = deque() # (y, x)
        q.append([cheese[k - 1][0], cheese[k - 1][1]]) # n回ごとのスタート地点を決める
    dist = [[10000] * w for _ in range(h)] # boolの役割もしている
    dist[q[0][0]][q[0][1]] = 0 # スタート地点は0距離
    while q:
        v = q.popleft()
        for i, j in d:
            if not (0 <= v[0] + i <= h - 1 and 0 <= v[1] + j <= w - 1): continue # 行く先が範囲外なら調べない
            if grid[v[0] + i][v[1] + j] == "X": continue # 障害物の場合は調べない
            if dist[v[0] + i][v[1] + j] != 10000: continue # 既に調べている場所は調べない
            q.append([v[0] + i, v[1] + j]) # 次の場所をdequeに追加する
            dist[v[0] + i][v[1] + j] = dist[v[0]][v[1]] + 1 # １歩先の場所は今いる場所から +1 して更新する
            if grid[v[0] + i][v[1] + j] == str(k + 1): # ゴール地点が見つかったらwhile文を脱出
                ans += dist[v[0] + i][v[1] + j] # スタートからゴールまでかかった分を足す
                break
print(ans)

31. E - イルミネーション (Illumination)

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_e

これは今回の６問の中では圧倒的に最難関の問題でした。
何が難しいかって、みたらわかるように４方向ではなく６方向なんですよね。
なので普通にBFSをしてもACは出来ません。

そこで各マスが装飾しなきゃいけないマスといくつ隣接してるかを数えます。
例えば、あるマスの周囲６カ所のうち２カ所に装飾すべき建物があるとします。そうすると、そこは塗らなくても良いので +4 色ぬりをします。

具体的にはTwitterでコメントいただいた下記のような画像が参考になると思います。

例2の図を用意するくらいしかできない... pic.twitter.com/rozHEyuSp8

— tnodino (@tnodino) 2021年1月13日

このような図が浮かべば、あとは偶数行・奇数行かのいずれかで場合分けをしてそれぞれの場合でBFSを行うとACすることが出来ます！

from collections import deque
w, h = map(int,input().split())
grid = [['0'] * (w + 2) for _ in range(h + 2)]

for i in range(h):
    S = list(input())
    for j in range(w):
        grid[i + 1][j + 1] = S[2 * j] # 文字列で取ってるので ' ' も含まれるから 2 * j とする

check = [[-1] * (w + 2) for _ in range(h + 2)]
d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 行けるかどうかチェックする際に使用する４方向の変化量
q = deque()
q.append([0, 0])
check[0][0] = 0

odd_d = [[-1, 0], [0, -1], [1, 0], [1, 1], [0, 1], [-1, 1]] # 奇数行６近傍の変化量 (y, x)
even_d = [[-1, -1], [0, -1], [1, -1], [1, 0], [0, 1], [-1, 0]] # 偶数行６近傍の変化量 (y, x)

# BFSで行ける場所を調べ上げる（-1 = 行けない, 0 = 行ける）
while q:
    v = q.popleft()
    if v[0] % 2 == 0:
        for i, j in even_d: # (dy, dx)
            if not (0 <= v[0] + i <= h + 1 and 0 <= v[1] + j <= w + 1): continue # 範囲外は調べない
            if grid[v[0] + i][v[1] + j] == '1': continue # 行く先が建物である場合には調べない
            if check[v[0] + i][v[1] + j] != -1: continue # 既にチェック済みの場所は調べない
            q.append([v[0] + i, v[1] + j])
            check[v[0] + i][v[1] + j] = 0
    else: # v[0] % 2 == 1:
        for i, j in odd_d: # (dy, dx)
            if not (0 <= v[0] + i <= h + 1 and 0 <= v[1] + j <= w + 1): continue # 範囲外は調べない
            if grid[v[0] + i][v[1] + j] == '1': continue # 行く先が建物である場合には調べない
            if check[v[0] + i][v[1] + j] != -1: continue # 既にチェック済みの場所は調べない
            q.append([v[0] + i, v[1] + j])
            check[v[0] + i][v[1] + j] = 0

# 周囲全てが黒で覆われているものは１に書き換える（入力例１だと (3, 2) など）
for i in range(1, h + 1):
    for j in range(1, w + 1):
        if check[i][j] == -1: # checkが -1 であれば全ての周囲が建物であるので'1'に置き換える
            grid[i][j] = '1'

ans = 0

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] == '1': # 今いるマスが建物であれば計算を開始する
            cnt = 0
            if i % 2 == 0: # 偶数行のとき（even_dを使うとき）
                for k in range(6):
                    if grid[i + even_d[k][0]][j + even_d[k][1]] == '1':
                        cnt += 1
            else: # 奇数行のとき（odd_dを使うとき）
                for k in range(6):
                    if grid[i + odd_d[k][0]][j + odd_d[k][1]] == '1':
                        cnt += 1
            ans += 6 - cnt # ６箇所のうち建物である場所を引けば装飾するべき場所が求まる

print(ans)

32. Amazing Mazes

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1166&lang=jp

こちらも少し癖のある問題です。
先ほどまでの問題はグリッドのマス自体に障害物がありましたが、この問題は線が障害物となっているのでそう簡単には解けません。

方針としては、調べようとしている先が縦方向なのか横方向なのかを場合分けしてそれに応じて作った障害物の有無を記載してる配列と照らし合わせて、行けるなら進み、行けない場合は止まります。
そうすると、上手くBFSを実装することができます。

コメントアウトは丁寧にしてあるので詳しくはACしたコードをみていただければわかると思います。

from collections import deque
while True:
    w, h = map(int,input().split())
    if (w, h) == (0, 0):
        exit()
    x = [[0] * w for _ in range(h - 1)] # 横線の障害物（0 = 何もない, 1 = 壁あり）
    y = [[0] * (w - 1) for _ in range(h)] # 縦線の障害物（0 = 何もない, 1 = 壁あり）

    for i in range(2 * h - 1): # 入力を受け取る
        S = list(map(int,input().split()))
        if i % 2 == 0: # 縦線の有無
            for j in range(w - 1):
                y[i // 2][j] = S[j]
        else: # 横線の有無
            for j in range(w):
                x[i // 2][j] = S[j]

    dist = [[10000] * w for _ in range(h)] # 初期値は10000で設定（boolの役割も果たせる）
    dist[0][0] = 1 # スター地点は距離１でいける
    q = deque()
    q.append([0, 0]) # スタート地点は左上の[0, 0]（y・x）
    d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # ４方向に対する変化量
    while q:
        v = q.popleft()
        for dy, dx in d:
            if not (0 <= v[0] + dy <= h - 1 and 0 <= v[1] + dx <= w - 1): continue # 範囲外であれば調べない
            if dist[v[0] + dy][v[1] + dx] != 10000: continue # 既にチェック済みの場所は調べない
            if dx == 0: #今調べてるのが縦（y）方向に行けるかどうかの場合
                if dy >= 0:
                    if x[v[0]][v[1]] == 1: continue # 壁のときは行けないので調べない
                else:
                    if x[v[0] + dy][v[1]] == 1: continue # 壁のときは行けないので調べない
                dist[v[0] + dy][v[1] + dx] = dist[v[0]][v[1]] + 1 # 今いる場所 +1 する
                q.append([v[0] + dy, v[1] + dx]) # 新たに行けた場所をdequeに追加する               
            else: #今調べてるのが横（x）方向に行けるかどうかの場合
                if dx >= 0:
                    if y[v[0]][v[1]] == 1: continue # 壁のときは行けないので調べない
                else:
                    if y[v[0]][v[1] + dx] == 1: continue # 壁のときは行けないので調べない
                dist[v[0] + dy][v[1] + dx] = dist[v[0]][v[1]] + 1 # 今いる場所 +1 する
                q.append([v[0] + dy, v[1] + dx]) # 新たに行けた場所をdequeに追加する

    if dist[-1][-1] == 10000: # 更新されてない場合は行けないことを意味している
        print(0)
    else:
        print(dist[-1][-1])

33. D - Grid Repainting

https://atcoder.jp/contests/abc088/tasks/abc088_d

本日最後の問題はこちら！！
最後だからといって難しいわけではなく、むしろ前の２問に比べたら簡単です。
必ずゴールまでの最短経路は白色でなければいけません。
なので、言い換えると最短経路以外の部分は白から黒に塗り替えても良いということになります。
それがわかれば基本問題の難易度と全く変わりません。

from collections import deque
h, w = map(int,input().split())
s = [[] for _ in range(h)]
for i in range(h):
    S = list(input())
    for j in range(w):
        s[i].append(S[j])

# マス全体の白いマスの個数を計算する
white = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white += 1

dist = [[10000] * w for _ in range(h)] # 各マスの距離を記録する配列
q = deque()
q.append([0, 0]) # スタート地点は(0(x座標), 0(y座標))
dist[0][0] = 1 # スタート地点は白いので +1 しておく
d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # ４方向に対する変化量
while q:
    v = q.popleft()
    for i, j in d:
        if not (0 <= v[0] + i <= h - 1 and 0 <= v[1] + j <= w - 1): continue # 行く先が範囲外なら調べない
        if s[v[0] + i][v[1] + j] == "#": continue # 黒の場合は調べない
        if dist[v[0] + i][v[1] + j] != 10000: continue # 既に調べている場所は調べない
        q.append([v[0] + i, v[1] + j]) # 新しく行く場所をdequeに追加する
        dist[v[0] + i][v[1] + j] = dist[v[0]][v[1]] + 1

last = dist[-1][-1]
if dist[-1][-1] == 10000: # 距離が更新されていないのでたどり着けない
    print(-1)
else:
    print(white - last) # 解 = （全体の白色の個数） - （通らなければならない白い場所）

最後に

意外と早く終わらせることができました！！
DFSとBFSを両方終わらせてみての感想ですが、どちらも書き方自体はとても似ている気がします。なのでDFSをある程度理解できていれば書きやすいと思います。
次回からはDPで全く分野が変わります。案の定DPについてはまだ何も知らないので時間がかかると思いますが、応援よろしくお願いします！！
それではまたいつか会いましょう！！

コードの指摘事項・アドバイス等ありましたら、コメントにてお知らせください。

初中級者が解くべき過去問精選 100 問 茶コーダーが解いてみた #6 ( 深さ優先探索（DFS）編 )

新年あけましておめでとうございます！！（おそっ）

今日も "初中級者が解くべき過去問精選 100 問"
を解いていきたいと思います！

精選100問って何？

記事はこちら！
qiita.com
こんなに丁寧にまとめてくださっている e869120 さんには本当に感謝しかないです。

記事を上げるタイミングは、この問題は100問ありますが、細かく分野ごとに分かれていますので、分野ごとに全て解き終わったら書いていきたいと思います。

今回は第６回目の深さ優先探索！！

過去の記事についてはこちら！！

全探索シリーズ

第１回：全列挙

ryusuke920.hatenablog.jp

第２回：工夫して通り数を減らす全列挙

ryusuke920.hatenablog.jp

第３回：ビット全探索

ryusuke920.hatenablog.jp

第４回：順列全探索

ryusuke920.hatenablog.jp

第５回：二分探索

ryusuke920.hatenablog.jp

深さ優先探索

深さ優先探索の分野は全部で４問あるので、紹介したいと思います！

24. Depth First Search

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja

個人的にはいきなり難しすぎて１ヶ月ほど放置してました...

これはまず３種類のグループ分けをして調べていきます。

• 1. まだ訪問してない頂点（下記コードのvisitでbool判定）
• 2. 訪問した頂点 かつ 行きしか調べてない（下記コードのgoが行きの判定）
• 3. 訪問した頂点 かつ 行きも帰りも調べてある（下記コードのbackが帰りの判定）

この上記のものを上の方から優先度が高くなるように調べていくと見つけることができます。
慣れるまではもう少し時間がかかりそうです。

n = int(input())

graph = [[0] * n for _ in range(n)] # 各ノードがどこのノードに行けるかの判定
for i in range(n):
    a = list(map(int,input().split()))
    for j in range(a[1]):
        graph[a[0] - 1][a[j + 2] - 1] = 1

visit = [False] * n # 訪問済みかどうかの判定
go = [0] * n # 発見時刻
back = [0] * n # 完了時刻
time = 0 # その時の時刻

def dfs(i):
    global time
    time += 1
    go[i] = time
    visit[i] = True
    for j in range(n):
        if visit[j] == False and graph[i][j] == 1: # 未訪問かつ行ける所
            dfs(j)
    time += 1
    back[i] = time

for i in range(n):
    if not visit[i]:
        dfs(i)

for i in range(n):
    print(i + 1, go[i], back[i])

25. How Many Islands?

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jp

これはdequeを使う問題です。
最初は全くわからず10人くらいのACしている方のコードを写経していると少しずつ理解してきて書けるようになりました。

コードの流れとしてはまず一つ一つのマスを見ていき、そこが陸であった場合dfsで行ける場所全てを訪問済みにして ans += 1 として全部のマスを調べていくイメージで解きました。

from collections import deque
def dfs(y, x):
    d = [[1, 0], [-1, 0], [0, 1], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]] # 8方向に対する変化量
    q = deque()
    q.append([y, x])
    while q:
        dy, dx = q.popleft()
        c[dy][dx] = 0
        for i, j in d:
            if 0 <= dy + i <= h - 1 and 0 <= dx + j <= w - 1: # これよく忘れがちでREになる
                if c[dy + i][dx + j] == 1:
                    c[dy + i][dx + j] = 0
                    q.append([dy + i, dx + j])

while True:
    w, h = map(int,input().split())
    if (w, h) == (0, 0):
        exit()
    c = [list(map(int,input().split())) for _ in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if c[i][j] == 1:
                ans += 1
                dfs(i, j)
    print(ans)

26. D - Ki

https://atcoder.jp/contests/abc138/tasks/abc138_d

こちらもqueueを使う問題です。
やっぱりこの分野はまだまだ難しく感じます。
方針としてはチェック済みでないノードに隣接してるものの合計を足していく方針でACできます。隣接行列はDFSでは本当によく使うので必ず取得が必要となってきます。

from collections import deque
n, q = map(int,input().split())
graph = [[] for _ in range(n)] # 隣接行列の作成
for i in range(n - 1):
    a, b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

ans = [0] * n # 答えとなるカウンターの値
for i in range(q):
    p, x = map(int,input().split())
    ans[p - 1] += x

q = deque()
q.append(0)
check = [0] * n
while q:
    v = q.popleft()
    check[v] = 1 # queueに入ってるノードをチェック済みにする
    for i in graph[v]:
        if check[i] != 0: continue # 未チェックの状態なら調べ上げる
        ans[i] += ans[v]
        q.append(i)
print(*ans)

27. D - 薄氷渡り

https://atcoder.jp/contests/joi2009yo/tasks/joi2009yo_d

この問題も非常に苦戦しました。
2時間くらいかけた上にTLの方人も聞いた。

方針としては全てのマスについて調べていって、そのマスが薄氷だった場合DFSを開始して最後に最大値を適宜最大値を更新するイメージです。

個人的に難しく感じた点は19行目の

    check[y][x] = False

にする所です。これはDFSの探索が奥まで終わったらもう一度元のマスを
初期化するというものでなかなか理解するのに苦労しました。

n = int(input())
m = int(input())

grid = [[0] * (n) for _ in range(m)] # 入力した値を打ち込む場所
d = [[1, 0], [-1, 0], [0, 1], [0, -1]] # 変化量[y, x]
for i in range(m):
    l = list(map(int,input().split()))
    for j in range(n):
        grid[i][j] = l[j]

def dfs(y, x, num):
    cnt = num
    check[y][x] = True
    for i, j in d:
        if not (0 <= y + i <= m - 1 and 0 <= x + j <= n - 1): continue # 範囲外なら調べない
        if check[y + i][x + j] == True: continue # 既にチェック済みの場所なら調べない
        if grid[y + i][x + j] == 0: continue # 薄氷でなければ調べない
        cnt = max(cnt, dfs(y + i, x + j, num + 1))
    check[y][x] = False
    return cnt

ans = 0 # 答え
for i in range(m):
    for j in range(n):
        if grid[i][j] == 1:
            check = [[False] * n for _ in range(m)]
            ans = max(ans, dfs(i, j, 1))
print(ans)

最後に

最後に記事を投稿してからかなりの日付が開いてしまいました。
DFSは１度も書いたことがなく全て０から調べていたので時間がかかりました。
次回はBFSですが、こちらも早く投稿はしたいですが、おそらく時間はかかります。
でも頑張って解くので応援よろしくお願いします！
最後まで見てくださった方、本当にありがとうございました！

コードの指摘事項・アドバイス等ありましたら、コメントにてお知らせください。