強くなりたい

毎日無意識に生きてて良くない

典型90問 まとめ 021～030

典型90問 競プロ

022 - Cubic Cake（★2）

できる立方体のうち最も大きいモノを考えるとその一辺は g = \gcd (a,b,c)　である。

実際そうなるように分割したときの操作の回数が今回求めたい最小回数である。

各面に対して何回操作を行うかと考えることでその回数は

\displaystyle \left(\frac{a}{g} -1\right)+\left(\frac{b}{g} -1 \right)+\left(\frac{c}{g} -1\right)

と求まる。

AC

024 - Select +／- One（★2）

AをBに合わせるのに必要な操作の最小回数はS = \sum_{i=1}^n |A_i-B_i|である。

このSがS \leq Kを満たしかつ(S-K)\% 2 = 0であることがちょうど K回でAをBに合わせられるための必要十分条件。

AC

026 - Independent Set on a Tree（★4）

木は二部グラフである！！！！

私はこれが思いつかなくて結局解説を見た。

隣り合う木に順に黒と白の色を塗っていってグループ分けする。すると同じ色に属する木は隣り合わないので黒と白のグループのうち大きい方を出力すれば良い。

AC

027 - Sign Up Requests （★2）

set型を使うとin演算子が高速で動作する。これを使うと簡単。 AC

参考↓ Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由 - Qiita

028 - Cluttered Paper（★4）

いもす法を使う。私はいもす法をあんまり使ったことがなかったのでちょっと実装に手間取った。

AC

参考↓

いもす法 - いもす研 (imos laboratory)

解説を読んでもよく分からなかった人のための「いもす法」の解説｜きりみんちゃんノート｜note

競プロの基本事項確認~累積和といもす法~ - Qiita

ニキビ

日記

鼻の下にできるニキビが今日また増えた。しかも痛い。肌の調子は確実に良くなってきているのにどうしてまた増えだしているのだろうか。

今日食べた食堂のまぐとろ丼は微妙だった。中央食堂はチキン南蛮を常時販売してくれ、そして北食はカツ丼を再開してくれ……。在学中にもういっかい食べたいよ……。

今日の発見

蝉やGが死ぬとき仰向けになっているのは死ぬときに足が内側に曲がってバランスを崩してしまうかららしい

典型90問 まとめ 011～020

典型90問 競プロ

012 - Red Painting（★4）

マスを赤く塗るクエリと赤で塗ったマスが繋がっているかを判定するクエリを処理する問題。

連結判定なのでUnionFindを使う。

その際マス (r,c) を数字に対応づける必要があるが、それは

\displaystyle (r,c) \longmapsto rW + c

とすればよい。（これは左上から順にマスをひとつずつ数えていったとき何番目に対応するかを表しており、この対応は単射である。まあW進法と考えれば当たり前だが……）

AC

013 - Passing（★5）

(ある地点Kを経由して1からNまで辿る最短経路) = (1からKまでの最短経路) + (KからNまでの最短経路)
最短経路を求めるにはダイクストラを使えば良い

AC

014 - We Used to Sing a Song Together（★3）

ソートして同じ順位にあるものたちの差を足し上げれば良いことがすぐにわかります。

AC

016 - Minimum Coins（★3）

制約が全探索してくれって言ってるので素直に全探索しましょう。

以下のコードではなるべくループの回数を少なくするために A>B>Cとなるようにしています。

Aのi枚、Bをj枚使うとしたときにN-Ai-Bjが非負でCの倍数ならk = \frac{N-Ai-Bj}{C}とおくと i+j+kが最小値の候補です。これを繰り返します。 AC

018 - Statue of Chokudai（★3）

三角比でゴリゴリ計算すればOK

私はarctanを求める方法で解きました。いろいろな求め方があると思います。

AC

020 - Log Inequality（★3）

誤差に注意しようという問題。

b\log_2 c> \log_2 a はc^{b} > aと同値なので後者で判定していく。

AC

本棚が欲しい

日記

私は段ボール箱を本棚の代わりに使っているのだが、今日その段ボール箱から本を取り出したら大切な本がかなり埃をかぶっていた。

中には本の重みで変に折れ目がついた本まで見つかり、、、

社会人になって一人暮らしをするときはちゃんと本棚は買おうと思った。。

今日は線型代数の復習をした。明日もこの続きをする。おやすみ。

典型90問 まとめ 001～010

典型90問 競プロ

簡単な解法を自分用にメモしておこうと思います。

001 - Yokan Party（★4）

答えに単調性があるので二分探索を考えます。

答えを決め打ちしての二分探索です。具体的には答えはM以上か？ということを考えます。

仮にK回以上分割してスコアSが得られたとします。このときK回より多く分割していることからより少ない回数で分割すればS以上のスコアが達成できます。

M以上のスコアが取れるかを考える→長さがM以上になったら切断することを考える→得られるスコアはS(>=M)→切断回数がK回以上ならよりS以上(つまりM以上)のスコアが達成できる

この判定を二分探索で繰り返します。

AC

002 - Encyclopedia of Parentheses（★3）

正しいカッコ列を全列挙する問題です。

制約が小さいことに着目してbit全探索を考えます。

bit全探索を用いて条件を満たさないカッコ列を含めてリストアップし、その中から条件を満たすものだけを出力します。

正しいカッコ列であることは次の2条件と同値です。

1. '('と')'の数が等しいこと
2. 文字列の途中で')'の数が'('の数を上回らないこと

AC

003 - Longest Circular Road（★4）

要約すると与えられるグラフは木であり、木の直径を求めよという問題である。

いったん都市1から各都市までの最短距離を求め、そこからわかった都市1から最も遠い都市を始点として再び各都市までの最短距離を求める。

すると木の直径がO(N)で求まる。

AC

004 - Cross Sum（★2）

やることはすぐわかるけど実装がちょっと大変。

\displaystyle B_{ij} = (Aのi行目の総和) + (Aのj列目の総和) - A_{ij}

なので各行、各列の総和を前もって計算しておく。

AC

007 - CP Classes（★3）

二分探索を使って以下を満たすiを求めれば良い。

\displaystyle A_{i-1}< B <= A_i

AC

008 - AtCounter（★4）

dpでできそうな感じがするので遷移を考える。

dp[i][j] = (S[0:i]で\rm{atcoder}[0:j]を作る方法が何通りあるか)

とすると遷移はS[j] = T[i]のとき

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

そうでないときは

dp[i][j] = dp[i-1][j]

となる。

AC

010 - Score Sum Queries（★2）

区間の総和を求めるので累積和の出番ですね。 特に難しいところはないです。

AC

こんにちは

このたび新たにブログを開設しました。

三日坊主なので続くかどうかはわかりません。この記事が最後になる可能性だってあります。（え？）

ブログを開設した理由は最近結構無意識的に生きてる気がしているからです。ブログに書くネタを探したり一日の最後にその日やったことを思い出したりすることで人生が濃くなれば良いなあと思ってます。

あとこのnoteをみたのも理由の一つです。

3日坊主が日記を365日、約60万文字書いて気づいたこと｜品田遊（ダ・ヴィンチ・恐山）｜note

恐山、いいよね。

よろしくお願いします。