Category: C++

こんにちは。RockinWoolです。久しぶりの投稿になりました。メンタルを病んでパソコンに向かえない日々が続いておりましたが、なんとか乗り切ることができました。そして先日ついに茶色コーダーになることができました。さて、今回もAtcoderの挑戦日記になります。 二分探索法の問題 #365のC問題は色々計算して閾値を求めるよりも、二分探索で無骨に求める方が速さ的にも良いという(クソ)問題でした。解けなかったのは素直に悔しい。こういう閾値を求める系の問題が出てきたら二分探索法を疑うようにしなければ。二分探索法をコードは以下に示します。 これでmidに改良の余地がある限りはmidが調整されていき、最終的に一意に求まるという関数ができます。この考え方はよーく覚えておきたい。 低い方から辞書順に並べる問題 Atcoder367のC問題は初見では解くことができませんでした。そもそも解き方を知らないと対策できない系の問題でしたね。肝心となるのは「辞書順に低い方から並べる」という部分です。こういう数列の問題が出てきたら再起関数の実装問題なんだという合図のようです。 この関数の形は基本的に使いまわししたほうが良さそうなので、今後も同様の問題が出てきたら使えるようにしておきたいですね。 まとめ 二分探索法と辞書順に並べる問題の解き方について復習しました。目指せ緑コーダー！

こんにちはRockinWoolです。最近は結構頑張って活動できていると思います。頭痛も寒さに慣れたからか軽減できていますしね。さて、1週間前の話になりますがABC#336を解いてみたので、解説と比較していこうと思います。今回は45分で3問も解けたので自分を褒めたい一方で、4問目で完全にスタックしたので解法を確認していこうと思います。それでは。 A問題 龍文字列 なんのことは無い平凡なA問題です。oをN個付ければ良いだけなのでかんたんでした。 B問題 CTZ 2進数化した時に、末尾に何個0が連続するかを算出する問題です。一般的に使われるc++のライブラリではstring型で出てこないため0の個数を確認することができませんでした。そこで、自作でstring型の2進数を返すtoBinaryを作ってやれば解決します。 ちなみに公式ではbitsライブラリを使って下記のように解いていました。 まずint nがbitとして扱えることに驚き、次に1を左にi個シフトするのを1<<iと表現するのがびっくりですね。あとは、左にi桁シフトした1とnでandを取って0でなければ0がi個あることになるという仕組みです。1<<iの挙動に関しては下記プログラムで確認しました。 これだとn=3で8, n=2で4, n=1で2, n=0で1を出力します。左にn個シフトしていることがわかりますね。 C問題 EvenDigits 5個の数字{0,2,4,6,8}のみを使って低い順に並べて、i番目に低い数字を答えるという問題。これは{0,1,2,3,4}だったとしたら5進数を答えれば良いと気づけたので、B問題のtoBinaryを流用して5進数を算出する関数を作ればクリアです。 コードの質と量は全然違いますが、公式でもまったく同じ解き方をしていたので嬉しいですね。公式から学べることとしては、for(int i=Fifnary.size()-1;i>=0;i–)の部分をreverse(Fifnary.begin(),Fifnary.end())と書けたということでしょうか。 D問題 ピラミッド数列 ピラミッド数列を考えるときにまず困ったのは1,1,2,2,3,2,2,1のように、もともとの数列の中心を軸にピラミッドを作ると121が算出されるけれど、本当の最大ピラミッドは12321のパターンです。結局これが解けなかったのでこの問題でスタックしました。さて、公式の回答をここで見てみましょう。 解説を読んだのですが、かなり複雑で難しいです。解説を写経してなんとか意味はわかったのですが、これを時間内に解くとなるとなにかが必要ですね。 まとめ D問題に初めて挑戦してみましたが、かなり難しいですね。これからも精進していつかは解けるようになりたいものです。それではまた次回！

こんにちはRockinWoolです。C++のプログラムが大きくなりそうだったので、クラスを作ってわかりやすく管理してやろう！と思ったわけですよ。しかし、なんか見知らぬエラーが連発してなんじゃこりゃってなったので、対策方法をメモして残しておきます。先に言っておきますが、かなり初心者レベルのことに今更気づいてドヤ顔しているので内容は結構恥ずかしいです。 おかしい。クラスを読み取ってくれない。 最近読んだリーダブルコードにもありました通り、本質的では無いコードはutilに突っ込んでメインは読みやすくしたい。そのためにはクラス化してpublicな関数とprivateな関数に分けてやろう！と意気込んだわけです。しかし、問題が。下記のようなプログラム構成にしたのですが、関数の定義が見つからないよというエラーが出てしまうのです。 「関数が定義されていない」というのであれば関数は定義されていないのでしょう。さて、何が問題だったのか？ CMakeLists.txtにライブラリファイルの登録をする必要があった 上記のミスはCMakeLists.txtに設定を追記していなかったことにより発生しておりました。下記にChatGPTとの会話を載せておきます。簡単に言えばadd_executable以外にもadd_libraryとtarget_link_librariesの2つを設定する必要がありました。 したがって、CMakeLists.txtは次のように書き換える必要があります。 ヘッダファイルからのincludeは不要 さて、上記のエラーを解決するのにはかなりの時間を要しました。というのも、このCやC++の仕様が気持ち悪くて何回躓いても納得できない！過去の自分と同じエラーで引っかかったので悔しいを通り越して怒りになっているのですが、サンプルプログラムを作ったりしながら試行錯誤を続けているうちに気づくことができたのは偉かった。エラーの原因ですが、utils.hに#include util/myclass.cppを書いていたのが原因でした。utils.hを読んだ時にクラスの定義より先にmyclass.cppの中のMyclass::hoge()関数を読もうとして、「Myclassなんて無いんだけど？」ってなったのが先のエラーです。確かにあとから見ればそんなの当たり前に感じますよね。でも、これってCMakeLists.txtに追記した内容を理解していないと遭遇してしまうと思うんです。pythonを書き慣れている私からすると、親子関係にあるプログラムは親でimport宣言をして子の関数を呼び出せるようにするのが当たり前。ということはutils.hで宣言する関数も実際に書かれているmyclass.cppからimportしなければならないのでは？と考えてしまうのです。（今でもその感覚は抜けていない）なので、ヘッダファイルで行っているのはあくまで関数のプロトタイプ宣言であり、utils.hとmyclass.cppでライブラリを作ったあと、utils.hとmain.cppでメインを作って、それらをリンクさせるという一連のCMakeLists.txtの動作を理解しないと、この違和感は払拭できないわけです。 まとめ 結局このエラーを解消するのに半日使ってしまったので、今となっては完全にやる気が削がれてしまいました。しかし、この経験をバネに日記を書いて次回につなげて行こうと思います。それではここまで長々とお付き合いいただきありがとうございました。