草体にぼ日記

だらだらと

2020年6月16,17日　日記

毎日

2020年 6月 16,17日

まえがき

あ〜。コンテスト出たときの記事書かねえと…

健康管理

最近PCの前に座りっぱなしで部屋の掃除が出来ていませんね。
風呂に入る前に3分ぐらい筋トレをしているのですが、腕立て伏せをしているときに床に落ちている髪の毛を見ると気が沈みますね。（ソレは筋トレですか？）
ちなみに筋肉にお願いしても解決してくれません

何した

ありがとうございました。

具体的に

今日(?)解いた問題

東京海上日動プログラミングコンテスト

C. Lamps

  • [操作回数の最大]

最大でも50回ぐらい操作をすれば値は収束する。（僕は1000回ぐらい回せばええやろっていってTLEでした。うざい) はあああああああああああああああ

Codeforces Round #514 (Div. 2) A.Cashier

  • [切り捨て]
    客が返ってから次の客がくるまでの時間(最後に客が来る時間をL(一日の長さ)としておくと都合がいい) で、何回休憩が取れるかを取っていく。

Codeforces Round #514 (Div. 2) B.

###
#.#
###

とする為の真ん中の'.'をポチっていいます。

ポチになる可能性があるのは、外周をぐるっとする1マスの枠より内側にあるので、ソレを全部ポチとして採用するか見てやる。
具体的には、作りたい

#####
#.###
#####

のようなものをfieldという配列に収めたとき、 field[i][j]の隣接8マスが全部#であればマスi,jはポチであるとする。
この時、ansという配列の[i][j]の隣接8マスを#にする。
このようにしていった時、最終的にansとfieldが一致するかを見てやれば良い。

ポチにしたマスを黒くするためには、ポチの隣接8マスがポチになる可能性のあるマスじゃなきゃいけない
だからかは知らないけどうまく行く。感覚で通したから証明は分からない。
恐らくだけど、あるマス(i,j)の隣接8マスが#のとき、(i,j)以外をポチとして(i,j)の周りを#にすることを考えると、場合がめっちゃ増えて頭コンガラがるし、(i,j)の隣接8以外も#になってしまう。

つまり(i,j)をポチにするのが最適(ポチのマスだけが求めるものとチガウ可能性がある）だから(i,j)をポチにしよう！みたいなノリで行けるんとちゃうんかな〜（わっかんね〜）

Codeforces Round #514 (Div. 2) C.

  • [約数,最大公約数,場合分け]

最初取る最大公約数は絶対1って言うのは分かる。
じゃあ、出来るだけ早い段階でGCDが2以上となるようにしたい。
サンプルを見てみると、N = 3 のときは、3がGCDとして取れるようになってる。

で、ちょっと考えると、N=4以上の時、1~Nの列の中に2の倍数はN/2個、3の倍数はN/3個である。
GCDを2にしたい時、操作はN-(N/2)回行うことで、2の倍数で無いものを取り除く. 数列は全て2の倍数になる。

GCDを3にしたいとき、操作はN-(N/3)回行うことで、3の倍数でないものを取り除く。 数列は全て3の倍数になる。

操作回数が少ない回数でGCDを1でないものにしたいので、基本的には2の倍数出ないものを取り除く。 (N/2 >= N/3 であるから)
ただし、N=3のときのみN/2 == N/3となる。(つまり、2の倍数出ないものを削除する操作回数と、3の倍数で無いものを取り除く操作回数が同じ) GCDを2にするより3にしたほうが辞書順で大きいので、このときは操作で3の倍数でないものを取り除いていく。

操作するごとにNを引いていき、Nが0になるまで操作する。
するとなんかうまく行く。

GCD は1,2,4,8,...,って感じで代わっていく。
N == 3 担った時だけ注意が必要で、 この時の数列の状態は {4,8,12}みたいになってる。
この状態になったら GCD　4 -> 4 -> 12 (要素の削除は4,8)
ってやって終わり。

まぁなんか、早くGCD大きくしたいよ〜ってとき、最低でも要素数/2 ぐらいすればGCD大きく出来るよ。的な。（ぐらい。ね。)

ABC170 D- Not Divisible

  • [素数っぽいやつ,エラトステネスの篩っぽいやつ]

まず入力を昇順に並び替えとく。 2が与えられたら,4,6,8,...は以後出てきても答えに加算はされない。みたいなエラトステネスの篩っぽいことをして素数っぽいやつの数を数えればいい。解けた時自分が天才かと思った。

ABC157 E-Simple String Queries

  • [set,集合を管理する,query,アルファベット]

'a' ~ 'z'の26文字についてを管理する。
'a'なら'a'が何文字目にあるかを保持。このように'a'のある位置を管理する配列~'z'のある位置を管理する配列を用意する。

文字の置き換えqueryに対しては、置き換わる前の文字列が何かを見て、其の文字の集合から、其の文字の位置を削除。（S自体も置き換える)
新しい文字cに対して、cが何番目にあるかを管理している配列に対して、追加する。

範囲queryに対しては、'a'~'z'があるかを1文字ずつ判定
これは、setの中身に対してLi文字目以降ではじめてc( 'a' ~ 'z'がc)が出てくる場所を見つける。見つけた位置がRより手前なら（Li以降で見つけているので)文字cがある。

今度似たような問題が出たら自分で解きてえ

ABC141 E- Who Says a Pun?

  • [文字列,DP,後ろからDP,Z-Algorithm]

文字列の問題強くなりてえなあ…。

DPを使うことによって、i文字目から見たsubstringとj文字目から見たsubstringについて、何文字共通するかを全てのi,jの組についてO(N2)で求めることが出来る。
おわり

EDPC F-LCS

最長の長さを取ることは出来たんだけど、DPの復元が分からなかった。
けんちょんさんの記事読んだんだけど、そのDPの値がどこから来たのかっていうのを考えるとわかりやすかった。

EDPC G- Longest Path

  • [DP,有向グラフ,再帰関数,トポロジカルソート]

DPの表って、出来ているものから出来ていないものを作っていくイメージだったんだけど、今回のような、（僕の中のイメージで）葉から根に向かって値を作っていく（根が呼び出しのもと)ようなときには、再帰関数を使えば逆から埋めていけるようだ！！（久しぶりに再帰書いた（書いてない）） f:id:niboshi_bisyoujo:20200618044720j:plain

あとがき

もっとかんがえれるのにしこうをほうきしています。

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)