競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。お金の大切さや今後の生き方も併せて伝えられたらと思います。

競技プログラミング~ABC167前半~

おはようございます。しほみんです。

 

ABC167の見直しです。といってもE問題解けてたのに最後変数を代入ミスでACできなかったのでつらかったです。とれたはずの水色パフォーマンスを失ったきつい回でした....

 

atcoder.jp

 

 

自分の競技プログラミングへのスタンスです。

<自分のプログラミング力>

・レートは800程度になりました。緑と茶をうろちょろしています。

・C#でクラスとかつかってアプリケーションは作れます。

<Atcoderでのスタンス>

・アルゴリズムについて問題でいろいろ学んでいる。PAST58点の初級レベル。

・基本的に時間がないのでぶっつけ本番でやっている。現在48回参加、もうすぐ一年。

・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色(1200以上)は欲しい。

 

今回はABCD、55分でした。パフォーマンスは過去最高1152で、緑後半でした。レートも無事818で、緑復活です。

ミスをしなくなったのがよかったです。ただ、先ほど言ったように解けてたのに実装できなかったことをしてしまったので大反省です。

こういうのいまだになれない...まだまだ実装力が足りないですね....

もういろいろなものは作れるようになったりライブラリが整ってきたので、あとは問題に対して適切なアルゴリズムを使えるかどうか練習ですね。

 

ということでE問題まで振り返りますが、長いのでA-CとD,Eで分けます。

今回はA-C問題まで書きます。

 

 

ここから問題です。

 

 

 

A問題

webサービスにID登録しようとします。

sをID登録したかったのですが既に登録済みでした。

なのでsに1文字加えたID登録しようと思います。

それがtなのですが、tがそれを満たしているか判定してください。

 

まあt = s+(ほかの1文字)なので、

sの文字列とtの最後の一文字以外が同じか判定すればよいです。

1文字比較かtを1文字消して考えればよいでしょう。

 

実際は前者で書きましたが、後者で書いてみます。

(構成例)

string s = Console.ReadLine();

string t = Console.ReadLine();

t1 = t.Substring(0, s.Length)

 

if(s == t1)

    Console.WriteLine("Yes");

else

    Console.WriteLine("No");

 

B問題

1, 0, -1の書かれたカードはA, B, C枚あります。

K枚取り出すとき、最大値はいくつでしょうか。

 

できるだけ1をとって、-1を取らないようにするのが最大です。

1, 0, -1の順にそれぞれA, B, C枚ずつ取っていきます。

K < Aであれば、全部1のカードなので、最大値はKです。

A<= K <= A +Bならば、1をA枚とって、残りを0にします。この時は最大値Aです。

A + B < K ならば、1をA枚、0をB枚、-1をK-A-B枚とります。この時はA-(K-A-B)です。

 

この条件分岐を書けばよいです。このとき、前の条件で分岐してしまったものは除かれるので、右辺だけ書けば十分です。すっきりしたコードになります。

 

(構成例)

if(K < A)

    Console.WriteLine(K);

else if(K < A+ B)

    Console.WriteLIne(A);

else

    Console.WriteLine(2*A-K+ B);

 

 

C問題

競技プログラミングを学びたいです。M個のアルゴリズムを覚えたいです。

それぞれの知識量は0です。

N個の本があり、その本のコストはCで、

本を読むとそれぞれの知識をMi得られます。

すべての知識が、X以上になることが目的です。

 

この時、与えられた本を使って一番小さいコストで目的を達成したいです。

最小コストを求めなさい。

 

制約条件を見ます。Nは最大でも12です。

よって、本の選び方は2の12乗で、高々4000通りです。

なので、全部調べてみて条件を満たす最小のコストを出します。

 

こういう時はこの本を選んだどうかだけなのでビット探索法が便利です。

それぞれのビットの位置が本の個数、ビットが1なら選択、0なら選ばないです。

例えば、10だと、00001010となり、8冊の本の場合、2,4冊目の本を選ぶことになります。(下一桁から1冊目とする)。

 

ということで実際実装例を挙げます。

全数は1 << n、i番目の本が選ばれたかは(i >> j) & 1が1かどうかで分かります。

for(int i = 0;i < (1 <<n);i++)

  for(int j = 0; j < n;j++)

             if( ((i >> j) & 1 )== 1)

                    count += cost[j];(costはj番目の本をコストを記録)

                    for(int k = 0;k < n;k++)

                          sum[k] = aj[k];

       (sumは今までの知識量の和、aj[k]はj番目の本のkの知識量を記録)

      for(int j = 0;j <  n;j++)(ここで条件満たすか判定)

            if(sum[j] <x)

               flag = 1;

               break;

      if(flag == 0)

             ans = Math.Min(ans, count);

 

少し複雑ですが、基本はビット全探索です。

 

今回はここまでにします。ではでは。

 

 

 

 

最近は昔のアニメを振り返っている~経済停滞で全部遅れてる~

おはようございます。しほみんです。

 

最近ようやく経済再開してきましたが....結局緊急事態宣言でほとんど1か月止まってしまったので、一か月ぐらい全部遅れている感じがします。

 

遅れていないのもありますが、やはり都市圏が経済を引っ張っている以上、そこが回復しないことには始まらなさそうです。

 

ということでアニメも遅れています。なので最近はdアニメで昔のアニメ見てます。

 

とはいっても昔一度見てもう一度見たいものを見ています。

というか昔の見てないアニメも見たいんですがもっとカジュアルに見れるものを考えるとどうしても昔の好きなアニメになりますね.....

 

 

ということで最近振り返ったアニメでも話そうと思います。やっぱ昔のアニメのほうが予算があったのか競争が激しくなかったのか、2クールだったり、EDいっぱい作った利してますね....。あとは傾向が違いますね。異世界転生はまずないですね....(ファンタジーが多い気がする)

 

あくまでぼく個人が面白いと思っているだけなので、ちょっと調べてみてもらえたら幸いです。

 

今日はこの2つにします。

・ちょびっツ

・はなまる幼稚園

 

・ちょびっツ

技術の進歩によってパソコンが人型になった世界。主人公の浪人生はゴミ捨て場に捨てられてたパソコンを拾い、起動してしまう。

パソコンと浪人生による物語。

 

全24話で、ヤング誌で連載されていたので下ネタ系が多いアニメです。前半はかなりふざけていますが、後半はパソコンがヒト型をしたとき、パソコンと人の恋愛は成り立つか?その時の人間の立場は?みたいな視点が書かれています。ほかのアンドロイド系のアニメを見ると深く考えられる気がします(プラメモとか、イブの時間とか)。

 

なにより原作者がclampなんで、clamp感が好きな人はお勧めできます。下ネタが多いぐらいで、普通によく考えさせられます(むしろ最後こんがらがるかも)

 

・はなまる幼稚園

幼稚園を舞台にした数少ないアニメ。クレヨンしんちゃん以外だとほとんどないレベルですね....。

これは日常系です。幼稚園の先生と幼稚園生とのドタバタ恋愛(?)コメディです。

めちゃくちゃ絵がかわいいです。

 

幼稚園児なのにすごく大人びている気もしますが、幼稚園児相応な感じでやり取りするので安心します。基本、園児が先生のことが好きって感じなのでクレしんとも違う感じですね。

 

なぜかヤング誌で連載されていたのが不思議ですが....漫画ではちゃんと落ちて終わっているので漫画もお勧めできますね。

 

人生ちょっと疲れたときに見ると穏やかな気持ちになれます。

 

最後に....

 

まあ、結局経済が進んでないと、昔を振り返るいい機会になります。これを機にいろいろ振り返っても行きたいですね。

 

ではでは。