精進 ABC077D-Small Multiple

すごくいい経験になったと思う

これからも使いそうな考え方を書いておく

この問題の特徴

まず、目に付くのは

「Kの正の倍数」という制限

僕は、このような「上に無制限」な問題に慣れていなかったのがダメだった思う

じゃあどうするの

なんとかして、この「Kの正の倍数」という無制限さを

有限に置き換えたい

どうするか

Kの倍数ということは

すべてKで割った時の剰余が0になる

まずこれに目をつけなければならなかった

また、数同士の関係性についても考えてみる

1 -> 2
1を足すと桁の和が1増える

1 -> 10

10を掛けると桁の数は変わらない

これを mod K の有限の世界で考えると

K の倍数、つまり 0 (mod K)を目指せばいいということだ

これは 0~K-1について

上の関係性のグラフを貼れば求めることができる(これは01BFS)

世界を狭める方法を考えることが大事だった

このような経験がなかったので成長できたと思う

Submission #2117580 - AtCoder Beginner Contest 077

精進 ARC068E Snuke Line

何をしても時間がかかりそう...

と悩んでいたが解説見てー

あーなるほどってなった

わかってたこと

r - l + 1 > d を満たす区間は必ず１回以上通る

それ以外は通らない、または１回だけ通る(つまり分からない)

わからなかったこと

倍数の計算量の抑え方

方針

・dはループで1~mまで計算する

・r - l + 1 <= d を満たす区間[l,r]に1加算する

このようにすることで、

dの倍数全てについて総和を取ることで

通るか通らないか分からない区間について調べることができる

つまりdについて

N - (r - l + 1 <= d を満たす区間  つまり通るかわからない区間)
  + (駅[i]における分からない区間の名産品の種類の数 | i は d の倍数)

とできるね

あとはBITを使うだけ

とは言いつつBITとimos法を合体させてるの面白くないですか

僕は面白いなーと思った

精進 ARC074D - 3N Numbers

おおー500点とかびびってたけど

最近の精進が効いてきてるみたいで自力で解けた嬉しい

さて方針

吸収していく、というイメージを持ちました

入力例1 2 3 1 4 1 5 9

これを右側と左側で分けてみると

[ 3 1 ] 4 1 [ 5 9 ]

左側は大きく、右側は小さくしていくのが目標ですね

左から3番目の4を考えてみよう

左側を大きくすることだけを考えれば

左側のグループで最小の1を捨てて、4を吸収するのがいいですね

また、

右から３番めの1を考える

右側を大きくすることを考えれば

右側のグループで最大の9を捨てて、1を吸収するのがいいです

これを方針とします

ここからがちょっと問題

ただし、どこまでを左側のグループで考えるか、

どこまでを右側のグループで考えるかを

決めることは不可能です

これは、全部試さなきゃダメ(この方針が今の僕に大切だと思う)

よく考えると

それぞれのグループの和はDPで求めることができます

これを利用して計算すればすべて試すことができる

O(NlogN)で通りました

もっと頑張る

Submission #2093049 - AtCoder Regular Contest 074

精進 ARC-070D No Need

途中まで気付けていたのですが

二分探索が分からなかった...

二分探索できない、勉強しなきゃ

どこまで気づいていたか

・ナップサック的にギリギリまで詰め込む

・ソートしておく

・不必要以下の大きさのカードは不必要

・必要以上の大きさのカードは必要

以下と以上の条件が出たら二分探索じゃないですか

確かにそうだ

ちゃんと把握しなきゃ、練習しなきゃ

Submission #2090524 - AtCoder Regular Contest 070

精進　ARC-069D Menagerie

あーこんなに簡単だったのか....

気づくの苦手すぎるので意識することを書いておく

どの問題でも「何が決まればいいのか」を把握しておく

広義昨日のForestも

「辺の数」と「森の形」と「頂点の小さい順」が決まれば

答えが導ける

ということだった

そういうことだね...

今回の場合は

「最初の２つの動物の種類」が決まれば

すべて決定できる

ということだった

あーやっぱり

「ここがわかってれば解けるのになぁ」という気持ちにならないと

頑張るぞ

Submission #2090026 - AtCoder Regular Contest 069

精進 APC-001-D Forest

こういう考え方が足りなさ過ぎてつらい

頑張らないとね

精進1

理想な考察の仕方を連ねてみるが(あっている保証がない)

要するに何するんですか (What is this?)

森を木にするための最小コストを調べます

答えはどんな形ですか (Answer?)

森にある木をすべて頂点で結んだ形

頂点はどうやって選びますか (How?)

すべての木をつなぐ->木のうち最低一つの頂点は使う

あとは小さい順

何個頂点を選びますか (Time?)

木を構成するにはn - 1の辺が必要

もうm本引いてあるので n - m - 1

引く辺の頂点はかぶってはいけないので

2 * (n - m - 1)個頂点を選べばいい

簡単ですね

はい

木を作って

木の中でもっとも小さいのを取り出して

あとは個数分だけ取り出す

もうすでに木ができているケースがあるので注意

apc001.contest.atcoder.jp

JOI'2018 本選体験記

お疲れさまでしたーーーーーー

だがしかし大爆死....

来年頑張るね

次出ようかなとか考えてる人も参考までに

プラクティスの日

はい誕生日()

僕は会場に受付終了30分前ぐらいにつきました

えープロばっかり赤いなみんな

綾鷹を入り口付近で抱きしめているとツイートすると

えかすどプロと、るましプロが寄ってきてくれましたー

初めましてーーっていう感じ

僕はここで携帯の電源がなくなります(ア)

新幹線の中では充電しましょう

プラクティス受ける全完

漁師がプラクティスTLEが判明

とがさんに会う

たのちい

夜は独房に入れられます()

ですがTwitterのおかげで

えかすど、るまし、漁師でアニメが見れた

ほんとたのちい

本選

150点！死！！！

DEGwerさんの解説面白すぎか

早く黄色になりたいな