tooh’s diary

半角全角、常体敬体が入り乱れるカオス

3/3 AtCoder(グリッドの扱い)/ウニ(G線上のアリア)

こんにちは。金恋GTのグランドエンディングまで見て涙したオタクです。いやーよかった.........................................................................................................................................................................................................................................................................................................................................................。 

 

AtCoder

解くに至った問題(7問)

ABC:042B/075B,C/120A,B,C

AGC:007A

 

ABC075B

グリッドを操作する苦手なタイプの問題。放置しまくってました。

結局、難しいところは「周囲八方向が'.'か'#'かを確認する際の例外処理」に集約されると思われる 

例えばグリッドの外周であれば多くても五か所(角に至っては三か所)だけを調べればよいが、周りにほかのマスがある場合は八か所全部調べないといけない、といったことを、いちいち場合分けして処理するのが面倒くさいというところを解消したい

で、そういう時に「あらかじめ移動する方向の差分のリストを持っておく」というのが便利である

例えば、

dx = [0,0,1,1,1,-1,-1,-1]
dy = [1,-1,1,-1,0,1,-1,0]

としておけば、(dx[k],dy[k])をそれぞれx方向、y方向の移動と捉えることで、8通りすべて賄うことができる

さらに、例外処理は面倒なので、全八通りを出したうえで、

①(調べるマスの行番号)+dy[k]が0未満、もしくはH以上であれば調べない

②(調べるマスの列番号)+dx[k]が0未満、もしくはW以上であれば調べない

とすれば、実質的に例外処理をしたことと同じになる

全方位を探索するのに、こういう工夫ができると楽

 

また、昨日もちらっと書いたが、例えば

L = [['A','B','C'],['D','E','F'],['G','H','I']]

というリストを

ABC

DEF

GHI

と出力したい場合は、

for i in range(3):

    for j in range(3):

        print(L[i][j],end = '')   #行ごとに改行なしで出力

    print()           #一行出力しきったら改行

とすればよい

 

atcoder.jp

 

AGC007A

与えられた模様が右、下の移動のみで進んでいけるかどうかを判定する問題

右に行けば列番号が1、下に行けば行番号が1増えることから、結局(1,1)から(H,W)に移動するまでの間にH+W-2回の移動する必要がある

(1,1)にも模様'#'がついていることを考えれば、全体で'#'の数を合計するとH+W-1になるので、これが与えられた情報と合致するかを判定すればよい

 

atcoder.jp

 

 

ABC042B

 

文字列を辞書式に並べてつなげて出力する問題

文字列の比較は不等号でできて、小さいほうが辞書で先に出てくる方になる(それはそう)

 

atcoder.jp

 

 

解けなかった問題

ABC:120D

ABC120D

 

見た瞬間「UF木やんけ!」と思ったものの与えられる橋の情報が多く、それだけで逐一確認していくのは不可能だと判断

次に「あれ、逆順から島をつなげていって、行き来できる島を数えていけばよくね?」と考えたものの実装できず

サイズ付きのUF木なるものがあるらしい これはrank(木の根っこ)の情報に加えて、各要素が所属するグループの全要素数の情報を付与したもの

これがあれば、

①島同士が最初から同じグループに所属していた→島をつなぐ作業により新たに行き来できる島はないため+0

②島同士が別グループに所属していた→島をつなぐ作業によって新たに行き来できる島は(今連結した島を含め)その島同士が所属するグループの全要素数に等しいので、答えにグループの要素数の積を足す、そして、そのグループ同士をuniteでくっつける

結局これをM回繰り返せばよくなり、時間的には間に合う

明日実装してみます サイズ付きUF木を学習する

 

 

 

 

ウニ

 

アリア鳥取れました  うれしい

f:id:saguh:20190304015223j:plain

 

Warcry地帯は擦ったら全ピカしました  最近擦りに自信がつき始めています

この曲、とにかく巻き込みやすいから大変だし、それだけじゃなくてラストのフリックも地味に抜けやすくてなかなか手こずる奴でしたが鳥取れて感無量でした

そろそろ15.5も見えてきそうなので、上位の曲を練習していきたいです