ABC202(3完)　list型とdict型

ABC202に参加してきました。今回は参加前の目標である3完達成出来ました！今回はC問題を解いた時点で50分ほど余っていたので初めてD問題に挑戦してみたりもしました。(全然実装できませんでしたが…)以下今回の感想です。

 

A問題

3つのサイコロを振って出た目の反対にある面の和を求める問題でした。さいころの目は全ての面において表と裏の和が7になっているので出た目を(a,b,c)とすれば求める解が21-a-b-cと出せますね！

 

B問題

0,1,6,8,9からなる文字列が与えられます。それを180°反転したような文字列、つまり文字列を反転して、6⇔9といったことをすればよいです。自分は与えられた文字列Sともう一つ空の文字列ansを用意してSを一文字目からforで調べて6 or 9であればもう一方を、それ以外であればそのままansに加えていって、最後ansを反転したものを出力して解きました。

 

C問題

長さがNとなる数列A,B,Cが与えられて、その中からA_i = B_(C_j)となる(i,j)の個数を求める問題です。自分はまずAの中に含まれる数字の個数をカウントしたリストを作成。その後B_(C_j)にその数字が出てきたらその数だけ事前に用意したansに加えていくといった解き方をしようと思いました。この方法だとTLEになってしまい通りませんでした。その後の解説を見る感じ自分はAの中の数をカウントしましたが、B_(C_j)の数をカウントして、それに対してA_1～A_Nまで数えれば通ったらしいです。自分はもとの解法でAの中に含まれる数字の個数をカウントしたリストを作る部分を、リストでなく辞書型で行うと計算量がものすごくはやくなりました。正直通ったのはいいのですが、リスト型と辞書型の計算量の違いを理解していないのでなんで通ったのかわからないです…分かる人がいたら教えてください～。とりあえず今回の復習としてこれからちょっと調べてみようと思います。なお今回の実装には以下のブログを参考しました。

inarizuuuushi.hatenablog.com

 

以上今回解いた問題の感想でした。最後挑戦してみたD問題なんですが、考察はそれなりに出来たと思うのですが、実装が全然できなかったです。何でか知らないけど文字列の操作苦手…

【疑問】芸能人が結婚したら株価が暴落するのはなぜ？

　先日、新垣結衣さんと星野源さんが結婚を発表したことで世の中で大きな話題になりました。お二人を祝福する人やショックを受けた人など、色々な声がSNS上などで挙げられました。しかし、その中に少し異色の嘆きを見かけた人もいると思います。それは

「ガッキ―ショック」とも言われた株価の暴落についてです。過去にも芸能人の方々が婚約などを発表したときに日経平均が大幅に下落したというニュースがありました。実際に今回もビットコインの相場が大幅に下がりTwitterのトレンドになるほど話題になっていました。そこで、そういった現象がなぜ起こるのか疑問に思い調べたのでその結果をまとめておこうと思います。

 

芸能ニュースと相場の関係

　まず結論から述べておきます。色々と調べた結果、芸能ニュースと相場の下落には因果関係はないそうです！つまり今回のガッキ―ショックや昨年あった石原さとみショックなどは単なる偶然だったということです。それ以外にもジンクスとして噂されるほどの事例はあるのですが、それら事態に因果関係はないというのが結論の様です。(あまり面白くない結論ですが、あれだけ噂されていることが偶然というのが衝撃的だったので思わずブログにまとめてみました…)

 これほど過去に事例があるのにそれらの因果関係は見られないそうです。ただ何もないのに株価が下がったというわけでは無く、例えば今回のビットコインの場合だとイーロン・マスクがビットコインに関する懸念を示したことが原因であると言われていますし、石原さとみショックのときも原因はシステムバックアップの機能不全が理由であるとしているそうです。これらのようにそれぞれの事件が起こった原因を調べたら何かしら別の要因が重なってこのような噂ができたのだと思います。なのでもっと詳しい関係を調べるのであれば1日当たりの相場の推移を詳しく見ていったり、○○ショックと言われなかった事例を調べたりしていけばもしかするといまはまだ言われていない法則が分かるかもしれません。

 

ABC201(2完)　解法の選択

今回のABCは2完でした。C問題を見たときにこれは解けるかなと思ったのですが、何度実装してもACがとれなかったです。以下今回の僕の考えをまとめておきます。

A問題

長さ3の数列が与えられて、それを並び替えて第1項と第2項の差=第2項と第3項の差となるように並び替えられるか判定する問題でした。長さが決まってるので素直にソートして順番をそろえた後に実際に差が等しくなっているか確認、といった方法で答えました。

B問題

山の名前と高さがそれぞれがまとめられているリストで与えられて、2番目に高い山の名前を出力する問題でした。自分は高さのリストをソートして新しいリストを作る→2番目に大きな値を見つける→元の高さのリストの中での見つけた値のindexを取得する→そのindexを使って求める山の名前を出力する、といった解法で解きました。考えるよりも思いついた順番に実装しようと思って実装しましたが、入力のときに2番目に大きな値を保存するようにするなど、工夫したらもっとシンプルに出す方法がありそうだなと思いました。(解説にもそんなことが書いてありますし)

 

C問題

0～9までの数字のうち、暗証番号に確実に使っている数字、使っているか分からない数字、確実に使っていない数字が与えられるので、4桁の暗証番号として考えられる数字の組み合わせの総数を出力する問題でした。この問題は数学かアルゴリズムのどちらかを上手に使えば解けるという問題でした。自分はアルゴリズムを使った解法が思いつかなかったので地道に場合分け(確実に使う文字が0,1,2,3,4,5以上の場合)をしてすべての場合でどうなるかを考えて実装したのですが、場合分けの数が多いのもあり正確に実装しきれませんでした。工夫を思いつかないときに愚直に実装しようとするのは大切だと思うのですが、それが簡単ではないということを実感しました(ケアレスミスとの戦いにめちゃんこ弱い)。実際10^4個調べる解法は思いつくのは難しいですが、実装としては今の自分の実力でも十分できそうなので、自分の実力と相談しながら解放の選択ができるようになりたいです。

ABC199

2度目のABC

2度目のABC参加です。今回の結果は前回と同じく2完でした。一応前回よりもスムーズに回答することができていて、パフォーマンスが少しだけ上がっていたので嬉しいです。ただB問題で>=にしないといけないところを>にしてWAを出してしまったのでそういった細かなミスを無くしたいなと思いました。後から死ぬほど悔しいので。今回のC問題なのですが、何度やってもTLEを回避する方法が時間内に思いつきませんでした。今はいかに実装できるかという勉強しかしていないのですが、計算量を考えれるようにもならないといけませんね。

 

リアルが忙しいので簡単にですがこんな感じで感想を書いておきます。

初めての競プロ(ABC198)

競プロ始めました

　先日行われた AtCoder Beginner Contest 198 で競技プログラミングデビューをしました。これから緑色になりたいな～くらいのモチベーションでやっていこうかと思います。特にいつまでになりたいとかそういった期限を設けるわけもなく、強いて言うなら緑になるまでちゃんと続けるって気持ちでのらりくらりとやっていきます。

 

--------------------------------------------------------------------------------------------------

ABC198

 

　今回はA問題とB問題の2完でした。C問題は全然分かりませんでした・・・ 緑になる基準がおそらくC問題がどれくらい解けるかどうかなのでまずはB問題までをスムーズに解けるように練習しつつ、たまにくらいでもC問題が解けるといった感じにしたいです。

A問題

A問題はN個のお菓子を互いに最低1つは持つように分ける分け方を求める問題。持ちうるお菓子の個数は1～N－１個なのでNー１を出力したらいいだけです。

B問題

B問題は10進法で与えられた数の先頭に0を加えることで回文にすることができるかの判定をする問題。自分は先頭に0をつけて回文になる→末尾にも0があるはず(それか最初から0が無い状態で回文)→文字列として考えて末尾の0を消して残った部分が回文になるかで見分けよう！って感じで解きました。ただし解説での解き方は制約が0≤N≤109

程度なので直接先頭に0をつけて判定しても数回のループでできるって解き方でした。別に僕の考え方でも解けたので別にいいといえばいいのですが、僕は10⁹
が見えた段階でループ回せないかなって勝手に思い込んでたのでそれは治さないとこのさき困りそうです。

C問題

2次元平面の原点から目的の座標までの最小の移動回数を求める問題。自分は座標を考えることができた時点で座標をどうやって表現したらいいかってことばかり考えてたのでもうこの時点でダメでした。座標で考えてると入出力例3を見た段階でもう何も考えられなくなります。プログラムは手で行う数学と違って膨大な数の計算ができるので座標で考えるというよりはこの領域にいればとりあえず具体的な動きを人が考えることができなくてもこういう条件をみたせるって考え方をしないといけませんね。そういう考え方が難しい。

 

といったところで簡単にではありますが今回の感想を終わります。これからもABCと同程度のコンテストはできるだけ参加してまずは沢山参加するように頑張ろうと思います。