shuのブログ

好きな時に好きなこと書くブログです。

ABC197に参加しました

ABC197に参加しましたので、復習のために解説を書いていこうと思います。今回は、初めて水パフォを達成しました。 自分の得意な問題セットだったのが大きいですね。Cはここ最近のABC、ARCで気づけずに苦しめられたbit全探索で復習が生きた感じがします。E問題が本番中に通せませんでしたが、冷静に考察すれば気づけるレベルだったので反省点です。 では、早速解説へ!

A - Rotate

問題概要

タイトルの通り文字列をrotateする。先頭文字を末尾へrotate

制約

文字列は3文字

解法

一番何も考えなくていいのは、s[1], s[2], s[0]の順に出力するだけ。 C++を使っている方はrotate関数があります。(他言語は各自お調べください)

rotate(先頭, 先頭に持ってきたい要素のイテレータ, 後ろ)で書けます。 つまり、

rotate(s.begin(), s.begin()+1, s.end())

こう書けます。僕もrotateの存在を知ったのは結構遅かったので知っておくと良いかもしれません。 stringだけでなく、vectorなどでも使えます。

B - Visibility

問題概要

 H*Wのグリッドマスで位置 (X,Y)から見えるのは何マス?

制約

 H, W \leq 100

解法

今いる位置 (X,Y)から上下左右を壁にぶつかるか、障害物#にぶつかるまで数える。 制約が緩いので各方向にfor文を回せば終了です。

この問題自体は簡単ですが、似たようなシチュエーションで難しい問題がたくさん出題されています。 この機会に復習、解いたことのない人はチャレンジしましょう。(diffは緑以上、難易度順です)

atcoder.jp

atcoder.jp

atcoder.jp

C - ORXOR

問題概要

長さ Nの数列 Aをいくつかの区間にわけ、区間内でORを取り、ORを取った区間値をXORを取る。 上手く分けてできるだけ最終値を小さくする。

制約

 1 \leq N \leq 20

解法

制約から見て数列の間に仕切りを入れるか入れないかをbitで管理できそうというのが思いつきます。 bit列の長さは、植木算的に考えて19です。 2^{19}が全探索できるか不安な方はpythonとかをサッと立ち上げて計算すると十分間に合うことがわかります。全探索中に数列を一回舐めるので計算量は O(2^{N-1}N)。 意外と実装でミスるところが多かったのかもしれません。(僕はintにしてWAをもらいました...)

ll ans = 5e18;
rep(s,1<<(n-1)){
    vector<ll> tmp;
    ll c = a[0];
    rep(i,n-1){
        if(s>>i&1){
            tmp.push_back(c);
            c = a[i+1];
        }else{
            c|=a[i+1];
        }
    }
    tmp.push_back(c); // これ忘れがち
    ll res = 0;
    rep(i,tmp.size()){
        res^=tmp[i];
    }
    ans=min(ans,res);
}
cout << ans << endl;

これが緑diffは意外でした。最近bit全探索の問題多いので気づいた人も多いと思うのですが。 bit演算(OR演算、XOR演算など)を初めて知った方はいい機会なので勉強しましょう。 わかりやすい記事です。僕もお世話になっています。

ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜 - Qiita

D - Opposite

問題概要

正N角形の頂点 (x_0, y_0), (x_{N/2}, y_{N/2})(順番は反時計回り)が与えられるので (x_1, y_1)の値を求める。

制約

 Nは偶数 入力値は全て整数

解法

ABCでは珍しい幾何の問題ですね。 頂点 (x_0, y_0), (x_{N/2}, y_{N/2})が与えられている時点でめちゃめちゃ正多角形の中心を求めたくなります。ここら辺はわからない時は図を書くことが大切です。中心から (x_0, y_0)を回転すれば (x_1, y_1)が求まります。回転角は \theta = 2\pi/Nです。 回転の仕方は色々ありますが、ここら辺は完全に数学の知識なので数学苦手な人はきつかったのかもしれません。

f:id:shu8Cream:20210328124749j:plain:w400

回転1

行列の知識があれば回転行列で操作できます。

 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} =
\begin{pmatrix} cos\theta & -sin\theta \\ sin\theta & cos\theta \end{pmatrix} 
\begin{pmatrix} x_0 \\ y_0 \end{pmatrix}  

こういう式になるのですが、注意点としてこの式多角形の中心点が原点と一致する時にしか使えません。 じゃあどうすんだよってなるかもしれませんが、一回中心点を原点に平行移動して回転させた後に元の位置に戻せばいいです。 以下の図の通りです。

f:id:shu8Cream:20210328124818j:plain:w400

 x_0 = x_0 - x_m, y_0 = y_0 - y_mと事前にしておき( x_m, y_mは多角形の中心点) 行列を全部展開すると  x_1 = x_0 cos\theta - y_0 sin\theta, y_1 = x_0 sin\theta + y_0 cos\theta これを最後元に位置に戻すために  x_1 = x_1 + x_m, y_1 = y_1 + y_mとすればおしまいです。

回転2 複素数平面に多角形が載っていると考えます。複素数平面上だと回転を考えるのが楽だったり便利なことが色々あります。 ただ複素数平面自体が数IIIの範囲なのでガチガチの理系じゃないと履修してないかもしれません。(昔は複素平面と呼んでいたそう) 文系プログラマの方も多いと思うので知らない方は勉強するのも良いかもしれません。コードに落とし込むのはこちらの方が楽な気がします。 pythonの記法ができると断然こっちが楽ですね

こちらの解説は気が向けば追加します。

感想

今回の問題セットは得意不得意が人によってはっきり出てしまう回だったみたいです。不得意部分がはっきり見えた方は今後対策しやすいかもしれません。個人的には爆速35分で4完できて満足です。関係ないですが、段々とはてなブログtex記法もコツを掴んできました。 また、解説を書くのでよろしくお願いします。

ABC196に参加しましたPart1

ABCで絶賛伸び悩み中なので、しっかり復習をしようという目的で解説を書いていきます。今回のABC196からだんだん遡る感じになりそうです。ブログ書きながら、新たなABCにも参加するのでブログが投稿される日時とナンバリングがぐちゃぐちゃになりそうですが、ご了承ください。灰diff下位の、よく解法ツイートで「はい」とか「やるだけ」みたいなのは端折る可能性があります。

あと、基本的にC++で書いてます。

A - Difference Max

b-cするだけ  

B - Round Down

stringで入力受け取り、頭から見ていって小数点が来たらそれ以下は捨てる

C - Doubled

問題概要

 1から整数 N以下で条件を満たすものの個数を数える。 条件:偶数桁かつ文字列で見た時、前半後半が一致している

制約

 1 \leq N \lt 10^{12}

解法

1. 本番で通した解法

個数が増えるのは、偶数桁の時だけなので奇数桁の時はそれ以下の偶数桁の条件を満たすものの個数全てである。

例えば、奇数桁の N=100の時、条件を満たすのは11,22,33,...,99の9個、

 N=10000の時、1010,1111,1212,...,2020,2121,...,9090,9191,...9898,9999の90個、プラス上記の N=100の時の9個で合計99個

のような感じで奇数桁であれば、桁数/2個、9が並ぶ数になる。

考えなければいけないのは偶数桁の時、上記の9が並ぶ数プラスどれだけあるのかを考える。

例えば、 N = 123456の時

f:id:shu8Cream:20210321130016j:plain:w400

こんな感じで数えます。また、前半部の方が大きい場合は、ちょっとだけ変わって N = 654321の時

f:id:shu8Cream:20210321130636j:plain:w400

こんな感じで数えられます。 ソースコードは以下へ。本番中のコードなので読みづらいかも

atcoder.jp

 これの計算量は Nの桁をdigとすると[tex: O(dig2)](これ間違ってるかも、指摘下さい)

2. 別解(全探索)

冷静に考えるとこんな複雑なことしなくていいですよね!

半分つまり[tex: N = 106]までなら全探索できるので、[tex: 106]まで一つ一つ N以下の数になるか確かめていけばいいです。本番でさっさとこれができれば…泣

ソースコードはこんな感じ

ll n;
cin >> n;
string s = to_string(n);
int dig = s.size();
ll num1 = n / (ll)pow(10,dig/2);
int ans = 0;
for(int i=1; i<=num1; i++){
    string t = to_string(i);
    t+=to_string(i); 
    if(stoll(t) <= n) ans++; 
}
cout << ans << endl;

 実装がめちゃめちゃ楽でした。計算量は O(\sqrt{N})

反省

考察し終わるまではスピーディでしたが,実装で大ポカをしました。これぐらいの実装はバグらせてもちゃちゃっと直せないといけないと思いました。目指せ緑!!

今回はここまででD, Eは改めて書こうと思います。

マラソン初心者のAHC001参加記

つい先日終了したAHC001に参加しましたので、参加記を書きます。AtCoderで初めてレーティング対象のヒューリスティック型のコンテストでした。最終順位は881位764,972,517,923点でした。(暫定順位は869位39,273,784,564点)山登り法や焼き鈍しはできていないので、伸び代はあると信じています。いろいろがんばった記録です。

他のつよつよ競プロerの方の記事がちょっと辛いよ、ムズイよって方向けに参考になれば幸いです。

 

問題

大きい広告スペースにたくさん企業から広告掲示依頼が来るので位置 x, yや大きさ rの要求をできるだけ叶えてあげるような掲示方法を探します。

 

atcoder.jp

 

思考過程 

点数が低い方から解法を挙げていきます。 

1. 一番簡単解法

823,090点

 
 コメント

とりあえず点数が欲しい、早めに順位表に乗りたい大体の人が通していた方法。

来た広告依頼に対して、 1*1の正方形の広告を出す方法。制約上、広告が被ることはないので一番簡単に思いつく方法ですね。めっちゃちっちゃい広告を出してあげます。これは企業からクレームが来そうですね。

 

2. 縦細長広告

27,266,837,345点

広告版を縦に区切って、その区間に細長広告を出す方法。広告依頼を xの値でソートし、順番に横幅を決めていく。

注意点

 xの値が同じ場合は 1*1の正方形の広告にする。(これはよくないけど、とりあえず提出するため)

3. 縦横細長広告

28,147,006,780点

基本の考え方は2と同じだけど、横にも同じことをして縦と比較して点数の稼げる方を採用。ここでコスト関数(スコア計算用の関数)を実装。
ラソンコンテストはコスト関数の実装絶対いるのはわかってるけど、最初はやる気が起きないです笑
長いのでとりあえず低めの点数取ってアップが終わってから実装したいお気持ち。

 

4. 縦横細長広告 改良ver

28,346,239,854点

3の解法の x yの同じ値が来るときの広告の形を 1*1から長方形の短冊状に変更。微増ですね。

 

5. 縦横細長広告 広告のサイズ最適化

39,273,784,564点

ここで大幅に点数が上がります。スコア関数を作って一つ一つの広告の満足度を見ていたところ依頼サイズの小さい広告であれば、広告のサイズを小さくしていくことで満足度が上がることに気づきました。(遅い!!)面積に応じて広告の長さを変化させます。小さいサイズの広告であれば満足度100%に簡単にできます。が、しかし、この細長形状でやっているせいで、面積を小さくする方にしか最適化できません。

見た目はこんな感じ

f:id:shu8Cream:20210316000108p:plain

解法5の様子

 ここまでで終了でした。もうちょっとうまくやれば400億点台にも乗せれそうでしたが、その後の伸びがイマイチそうです。

簡単な工夫でここまではなんとかなります。おそらく誰でも到達できるのでは?

解法5のソースコードです。REしてるのがいくつかあってこれが最終順位がちょっと落ちた原因ですね

atcoder.jp

 

最後に

つよつよな方々が素晴らしい参加記を書いているので恐縮ですが、弱いなりに色々まとめてみました。つよつよな方々はエンジニアとしても素晴らしく、TypeScriptとかで自作ビジュアライザを作っている方もいらして、マラソンの世界の深淵を覗き込んでしまった気分です。山登りや焼き鈍しはAHC002までになんとかがんばって勉強したいと思います。

アイコン描いてもらいました

こんにちは、shuです。

大学の後輩に依頼をしてアイコンを描いていただいたので紹介したいと思います。

描いてくれたのは、ちくわゐさんです。Twitterはこちら

twitter.com

 

で、今回描いてくれたアイコンがこちらです!!

f:id:shu8Cream:20210117150751j:plain

新アイコン

すごくいい感じに仕上げてくれました。(語彙力)めちゃめちゃ気に入ってます! 

僕のTwitterとか色んなアイコンがこれになっていくので見慣れていって下さい。

ちくわゐさんは、MVとか作ってたりするので観にいきましょう!あと、依頼もできたりするのかな?もし気になった方は、相談してみて下さい。

 

 

【2021年】新年の目標

あけましておめでとうございます!

2021年が始まって数日が経ってしまいましたが,今年の目標を記しておこうと思います.一年後に振り返りやすい場所に書いておこうと思いました.

 

目標

競プロ

  • 年度内に緑コーダー
  • 年内に水色コーダー

その他

今年はいろいろ国内旅行したいですね〜

今年も気楽にゆるゆるといきましょう

 

自分へ

ちょいちょい確認しに来てると思うけど,達成できているかはあんま重要じゃないので途中までやったのか,どこまで進んだか目標の修正に使ってください.これで辛くなるならやめてもいいのでw

 

最近の精進と反省会とおすすめ

色変記事を書いてひと月ぐらい経ったので、最近の勉強についてまとめたいと思います。プラスで、最近停滞気味なので今の気持ちと反省を残しておきます。最後には、近況として好きなことを書いてます。

 

 

最近の精進

ここ最近は、相変わらず茶色、緑の問題を地道に解いています。加えて、レッドコーダーが教えるシリーズ中級編のQiita記事の精選100問も解き進めています。難しい問題は、後回しにしてできるだけ解説読まずに時間かけてでもACしようと頑張ってます。

qiita.com

新たに勉強しているアルゴリズムとしては、DFS・BFS・ダイクストラ法です。ここら辺を中心に木の持ち方だったり、実装の仕方を学んでいます。応用が効くようになるまでにはまだまだ時間がかかりそうです。

DPの勉強も進めたいと思っていて、実際に問題を眺めて解説も見ながら取り組んではいるのですが、いまいち自分の中でしっくり来ていない部分が多く、コンテストには頻出で重要項目なのは承知の上でじっくり時間を掛けながら進めています。

最近のABCでは、自分にとって非常に教育的でいい問題が多くコンテスト中に調べて勉強して通すことやコンテスト後に復習することも多いです。特にABC183, 184はいもす法やマージテク、マンハッタン距離・チェビシェフ距離、確率DP、半分全列挙など勉強するいい題材をもらってる感じで非常に楽しいです。

 いもす法

これはABC中にサイト検索したら、例題と問題がほぼ一緒だったのですぐACできました。応用や使える問題の例も下のサイトで紹介されているのでみんなで練習しましょう。

imoz.jp

マンハッタン距離・チェビシェフ距離

先日出題されたSuper Ryumaは、茶diffでもなかなか難しい問題でしたが、自分としては解けないとダメだったなと感じています。その理由がこの問題。

atcoder.jp

解いたときに分からなくて、解説読んでACしたんですが、結果的に身についてませんでした。問題を見てマンハッタン距離しか出てきてなくね?と思ったあなたチェビシェフ距離との関係も調べましょう。必ずしも使わなきゃ解けない問題ではないですが、その発想を覚えておくことも大事だと思ってます。

確率DP

これを参考にしてます。ネットで拾った北大の競プロerの方のプレゼン資料?です。

https://compro.tsutaj.com//archive/180220_probability_dp.pdf

 

こんな感じで勉強に活用しているものをまとめてみました。

後もう一つ進めていることがライブラリの整理です。ある程度分量のある実装が必要なアルゴリズムや頻繁に使うようなものを参照しやすいようにGithubを使ってまとめています。けんちょんさんのライブラリを参考にしながら、徐々に充実させようと思っています。現状では、約数列挙やDFS・BFS、二分探索、UnionFindなどを整理しました。素数判定や素因数分解なども近いうちに整理したいですね。

反省

ここは個人的な反省です。

最近停滞気味なんで反省を書き記しておきます。ここ2週間は、いらない勘違いをして解法があっているのにACまで結び付けられないという事態が発生しています。一つ目は、long long型で 10^{18}を受け取れないと勘違いしたせいで合っていた解法を変えてしまう、もう一つは、問題文をよく読んでいなくて、余計な制約を付け加えて考えていたせいで場合分けを一つし損なってしまう、というものでした。型の受け取れる最大値はlong long以外のものも一度しっかり確認しました。そして自分がしたミスをHackMDのメモにまとめてコンテスト中詰まったり悩んだら見ることにしました。そしてそして、詰まったときには1文字1文字問題文を読み返すのもコンテスト中冷静さを取り戻すために必要なことだと感じています。

最近のミスは、しょうもなすぎて心にきていますが、精進ができていないわけではなく確実に難易度の高い問題も徐々にですが解けるようになってきている感覚はあるので次のコンテストにつながるようにしていきたいですね。

後、使っているメモツールも悩んでいるところです。github, HackMD, Scrapboxを復習や知識整理に利用しているのですが、だんだん煩雑になってきたのでそこの整理もしなきゃなと思っています。皆さんはどんなツールを使っているんでしょうか?数式(Tex)とソースコードがまとめられてどの端末からもアクセスできるツールって限られている感じもするんですが。。。

近況

ここからは、競プロ関係ないです。

最近ハマってるYouTubeが「週末養蜂ちゃんねる」です。

www.youtube.com

ニホンミツバチの養蜂をしている方の動画で、蜂の巣の構造きれいだな〜とか思って見てます。蜂たちがせっせと蜜を集めている様子やはちみつを取っている様子がなんでか見てしまいます。将来ニホンミツバチの養蜂するのもいいな〜なんて。(勘違いされても困るので、私は基本的に虫は嫌いですw)

 

もう一つ、最近ハマってるバンド。昔から知っていたバンドではあるんですが、最近また聴くようになって「F1RST TAKE」で公開されているバンド演奏は結構な頻度で見てます。聴いたことない人におすすめな曲は、「Mela!」、「Shout Baby」、「sabotage」。ポップで聴きやすいと思います!ボーカルの歌うますぎぃ!!

ライブとCD音源で演奏を変えているようなので、比較すると楽しんで聴けます。

www.youtube.com

AtCoderで茶色になった

AtCoderで競プロを始めて約2ヶ月、2020/11/01 のABC181で茶色になったのでブログ書きます。自己紹介をしつつ、これまでどう勉強したのかまとめてみました。

 

f:id:shu8Cream:20201102200230p:plain

現在のレート

 

 自己紹介

職業:大学4年(情報系)

競プロ歴:約2ヶ月(20/09/13開始)

使用言語:C++

生息地:shu (@shu8Cream) | Twitter

twitter.com

大学で勉強したことも触れつつまとめてるので参考になったら嬉しいです。

僕の簡単なスペックとしては、プログラミング力は、自分ではよくわからないので大学の成績をあげると真ん中ぐらい、なのでそんな程度だと思ってます。数学力としては、大学受験でいうとセンター数学IA・IIBともに9割以上で2次試験も数学で戦ってた感じはあります。競プロ界隈では数強の方も多いので自分が数強だとは言えないですが、数学は好きで趣味程度に楽しんでます。

レートについて

競プロ界隈にいると上にいる方々が凄すぎて、自分なんてという気持ちが強くなるんですが、茶色も凄いぞって感じで褒めてくれたり、評価していただけると僕が嬉しいです。

正直、茶色の難易度の問題でも本番で解けないことも多々あります。スピードも実装力が求められる問題だとかなり時間がかかったり、数学でゴリ押せる問題だと似たようなレートの中でもかなり早く解けたりするのでまだまだ不安定な部分もあります。

 AtCoderでのレート

レート 補足
1600~1999 なれたらいいな
1200~1599 ここになりたい
800~1199 次の目標
400~799 現在地(427)
0~399 戻ることはないようにしたい
未参加  

 目標としてはこんな感じで最終的には水色を目指しています。青にもなれたらいいですが、今のところ現実味がないです。

茶色コーダーになるためにやったこと

競プロの取り組み方

まずは、AtCoder Problemsの記録をみてもらうのがわかりやすいと思うので載せときます。

 

f:id:shu8Cream:20201102200600p:plain

Streak

f:id:shu8Cream:20201102200459p:plain

解いた問題

こんな感じですね・・・って言ってしまったらこの記事終わるのでちゃんと説明します。解いた問題数は画像の通りなんですが、はじめ頑張っていたのは以下の3つです。

  • 本番の形式に慣れる(バチャコン参加)
  • 灰問題をひたすら解く
  • うーんと悩んで解けるぐらいの問題を毎日一問

僕は実装力が無いと思っているのでひたすらコードを書く事を意識しました。あとは、APG4bで解説されるようなSTL関数やSTLのコンテナは本当によく使うので、実際の問題で試しまくりました。慣れると「この問題set使えるな」とかすぐ頭に浮かぶようになりました。

覚えたこと

  • 線形探索
  • bit全探索
  • 二分探索
  • 累積和
  • Union Find
  • (modint)

意識して覚えたのはこんなところです。どれにしても応用の難しい問題は解ける気はしてないです。とりあえず理解して基礎問題は取れるぐらいにしました。最後のmodintはACLにありますが、使い方覚えていた方が圧倒的に便利です。

 

大学でやったこと

初めにも触れましたが、情報系の大学にいるため嫌でもアルゴリズムやデータ構造は勉強しました。ここにまとめるために残ってた授業資料見直したんですが、強くなるために必要そうなものは網羅されてそうでした(もう覚えてないけど)。

出す順番が無茶苦茶ですが、一通り知っているので改めて勉強するにも取り組みやすかったです。まだ復習できていないものに関してもそうだと思います。ただ問題は実装がちゃんとできるのか、これが大きい問題で僕自身の課題です。地道にやっていこうと思います。

目標とこれからやりたいこと

入茶したので今後の当分の目標はです。期間は年内までに、と言いたいところですがそんな甘く無いと思うので年度内までに入緑できるよう精進したいと思います。

具体的にこれから取り組みたいことと言えば、

  • 高校数学の場合の数、確率+数列の復習
  • DPの勉強(EDPC)
  • けんちょんさんの本を読み進める(現在DP頑張ってます)
  • 茶diff埋め

こんな感じです。競プロ勢のみなさん数学が得意な方もいっぱいいると思いますが、僕は色々抜け落ちている部分があるので高校数学の復習をしたいと思っています。そして、DPは慣れというのも見聞きするんですが、ひたすら精進あるのみですね。最後に茶問題を解ききろう!って感じです。

茶色コーダーのみなさん一緒に頑張りましょう!

おすすめの本

以前から持っていた本や読んだ本をいくつかまとめておきます。

 プログラマの数学

https://amzn.to/34vQe0B

数学ガール』シリーズを書いている結城浩さんの本でプログラミングに役立つ数学の知識がわかりやすくまとめられています。ソースコードが多く載っているわけではないので、これだけですぐ競プロに使えるほどではないですが、論理・剰余・順列・再帰など高校数学の復習知識やプログラミングする上で大事な基礎の考え方がまとまっています。けんちょんさんの本(一つ下で説明)もいきなりだと難しそうと感じる人は読んでみるといいと思います。数学に苦手意識のある競プロerは『数学ガール』シリーズもおすすめです。(ただ僕が好きなだけ)

問題解決力を鍛える!アルゴリズムとデータ構造

https://amzn.to/3rfPGFS

僕が説明するまでもないと思いますが、けんちょんさんの本です。実際の競プロで役立つ知識満載の競プロerなら買いの一冊だと思います。本格的に競プロで戦っていくために学ぶべきものが詰まっています。競プロ本として有名な蟻本だとちょっとむずくて厳しいと感じる人はこの本から始めるといいかもしれません。(こんなふうに紹介してる方が結構います)僕は「蟻本むずそうだな〜」と手を出そうか迷ってる時にこの本が出版されたのですぐ買いました。

まとめ

以上が入茶するまでにやっていたことです。初めてブログを書いたので拙い文章ではあったと思いますが、ここまで読んで下さりありがとうございます。今後も気が向いた時に書いていこうと思うので僕のTwitterで動向を見ていただけると嬉しいです。