2025-12-29

ラテの3daysハッカソンインターン参加記・後編　～「絆」を覚えた日～

Long Time No See

お久しぶりです。まっちゃラテです🍵

あの、今年の振り替えを書こうと思ってたんですけど

めっちゃ忘れてました後編書くの★

...てことで後編を書きます。今ちょっと元気が出ないので前編のようにバカみたいな感じで書けるかと言われると、難しいと思いますが、最後までお読みいただけますと幸いです✨
（特に過去の俺が喜びます）

でもやっぱり、オフラインだと共有がマジでしやすい。
いつもホワイトボードで自分なりにまとめてた考察をSlackに挙げていた、といったことを繰り返していたので、この手間がなくなるだけですごく心が楽になりました。
というか、オフラインの方が本当に向いてるんですよね。雑談とかもしやすいし、なんで...？って思うんですけど俺でも。

ただその分、説明力が必要だったのが、自分の弱点を突かれた瞬間でした。ただでさえ日本語ができない人なので、、、

そうしてフロントはUIの修正を、バックは座席管理クラスのバグ直し。私は目に炎を浮かべながら無我夢中でコーディングの手を進めていきました。集中して、メンバーと話し合いながら。
この時の雰囲気、実際にグループ開発を行う場合も、こういう静けさの環境の中取り組めるんだろうな、って思うとちょっと心がわくわくしてました。私は趣味で個人開発をしていたのですが、こういうときって大抵孤独になりがちだったんですが、今回のグループ開発では孤独に感じなくて。なんか心がほっこりしたような覚えがあります。

これってやっぱり、自分と同じようなプログラミングっていう分野が好きって感情から伝わってくるもんなのかな...？
フェロモンくらい伝わってきました（？）♡
フェロモンと違って甘い香りじゃなくて、なんというかすこし...塩っぽい（？）感じがしみじみと伝わって。だから本当に楽しかったです。

個人的にインターンって

個人で参加して、でもその方たちが集まってチーム開発をする。だから一人一人で活動はしてるんだけど、チーム全体で一丸となって開発してる。でも一人って感じるときがあるから孤独に感じる。それでも"チームの目標"のために頑張る。

こういう孤独に感じる瞬間が多く感じるイメージがあったんですが、今回は違いました。しっかりこう、「チーム」であることを感じられて、めっちゃ嬉しかった記憶があります。
人生の中でもこんな、チーム一丸っていうことを実感できたことはマジで1,2回くらいしかなかったので...

話逸れちゃいました。
とにかくバグ直しを行いました。協力はしてたんですが、やはり共有もGitHubを使ってたわけでもなかったので、難しくて。なので対面という状況を利用してそれぞれフロント・バックの担当で座席を分割して一緒に考えるフェーズに。

フロントはUIについてメンターの方々と協力しながら。実際何回も頭を抱えて、うーんって考える姿を見たのですが、思い返すと自分の今までの精進の姿に似てて、

頑張って考えてる...俺も頑張らないと！！

っていう、さらなるやる気の灯火に油を注ぎました。こういうの情に流されがちなんですよね私は。

なので、私のバックエンド担当もバグなんかで泣いてる暇はないです。発表まで残り2時間。
どうにかしてバグを探しまくるしかなかったです。自分を中心として。

正直この時も、個人開発しまくっておいてよかったと思ってます。尚更競プロを与えてくれた母校のPC部、この界隈で育ててくれたFFの方々には感謝しかないです。だってこれをきっかけにプログラミングの楽しさに気づかせてくれたので。

（またお涙ちょうだいというわけではないです）

そうして色々デバッグをしまくって、ここがデータの同期取れてないとか、元居た座席が空席になってないなどを私が指摘しまくって、相方と一緒に考えながら、リアタイABCのように紙とペンを使いながら、問題文から本質を突くようなアルゴリズムをひたすら見つける、というわけではないですが、デバッグ結果を見ながらバグの原因を探すような挙動をしてひたすら直す、という、競プロとの類似点や相違点があって、不思議な気持ちになったことをよく覚えています。ほらね？競プロは実務で役立ちます。特に経験が。

そう偉そうに言いますが、やっぱり競プロ力はここでも引き出されると思うと、自分は競プロをやっていてよかったなと心から思います。毎回言ってますねこれ。
あれですからね、「好き」って人に言いまくることで愛が軽くなるとかじゃないですからね！？マジで競プロはやっててよかったと心から強く思ってますからね？？

そうしてデバッグし続けて、発表まで残り45分。
来ました。バグをようやく見つけました。
急いで原因を整理して、対策を紙に書きなぐりました。実際最終的にフロントと接続しなければならなかったので、時間はかけられませんでした。その時間を短縮するときは、私は対策を行ったときの関数群をひとまとめにする、といった手法を取るのですが、今回もそれを行いました。

そうして発表まで残り25分。フロントもついにバグ修正を完了させたので、急いで接続しました。
でも、え、エラーが出るんだけど。いや、このコードだったら...つながった！！！！✨
この瞬間は、このインターン史上一番の安堵が訪れた時だったと思います。

そもそも時間制限がない中で開発していた自分だったので、時間がないとこんな焦らされるんだね人って...と思いました。なんというか、本当に納期に間に合わせる、といった感覚を経験できました（本当の実務ならもっと焦るんでしょうけど...）。

プレゼン発表会

これにて、ようやくデモ版が完成し、発表を行いました。発表は私以外のメンバー2人が代わりにやってくれました。本当にありがとうございます。
他チームの発表も見てみたんですが、人って様々な価値観を持つ、といったことは知っていたんですが、これも改めて学ばれたような気がしました。正直、全部面白いアイデアでした。

人ってこんなアイデア思いつけるんだ...すげぇ。
自分が次回する開発のテーマにも活用できそうだったので、なおさら勉強になりました。

懇親会

そして無事に発表会が終わり、懇親会へ。
たくさんの人と話す機会はここしかない！！って心ではわかってるんですけど、やっぱ行動ってなると難しいんですよ、、、、
話題も思いつかない、沈黙が流れたらどうしよう、面白いこと言えるのかな...とか、いろんな不安があって。

ね、強化学習の塊だよね人間って。
この一言は特に意味はないです（じゃあなんで言ってんだよ過去の自分）。

色々考えて、自分のチームメンバーと話していたら、なんど技術部の部長さんが自ら話しに来てくださって...✨
絶対に貴重だよねこの時間？（当たり前だろ）

ということで色々聞きまくって話しまくりました。相変わらず自分は、人の話をうんうん確かにって聞く担当でしたが、それでもやはり、自分って人の感情を読み取るのが得意だったりするのか...？それともただの同情？こう、やはり雰囲気を壊さないために話題を頭の中で整理しまくって、失礼のないような振る舞いで話してました。そしたら案の上、私の日本語の構造は思い返すとすっげぇぐちゃぐちゃでした★（部長さんごめんなさい）
でも部長さんはベテランで、そりゃ聞きたいこともたくさんあって。「どういう経緯で入社されたんですか」「開発の際の設計はどうやってやってるんですか」的な、貴重な話。
さらに人事部の部長さんも来てくれて、さらに私は緊張していました...()

でも明らかに貴重な時間だったので、しっかり話をして、聞きました。
この経験を通じて、コミュニケーション能力って、人と話せる力というよりは、ビジネス的な対談力って意味でもあるんだなって思いました。

こうして懇親会を終え、今回の3daysハッカソンインターンは幕を下ろしました。

感想・反省点

さぁ、いかがでしたでしょうか...()
こんな感じで、今回のハッカソンインターンに参加しました。

反省点としては、設計に関しては自分流の開発を行っていたので、その共有方法に時間を取ってしまったこと。対談面に関しては、事前に聞きたい質問を用意してなかったこと、だと思っています。
このインターンに参加する前、自分が参加して経験が得られればいいやー程度で、軽い気持ちで臨んでいたので、そこが全体としての反省点だと思いました。特に、インターンに参加する意味をよく考えなかったことです。確かにグループ開発という、すごく貴重な経験をさせてくれましたが、チームとしての貢献などは考えておらず、ただ単に開発をしたいといったことだけでした。気持ちの上辺だけで参加した、といったらいいでしょうか...
この参加意義をしっかりしてれば、もっと、その目標にどれくらい貢献できたか、詳しく自己反省をできると思いました。

ただ、このインターンで得られた経験は、"自分は一般社会になじめる可能性が高まった"、ということです。
就活を始めた当初は、本当に俺なんかが社会に馴染めんのか...？という不安はあったのですが、今回の経験を通じてその不安は和らいだということは、すごく大きな収穫であると強く感じました。

また、このような収穫があったことから、"自分から興味あるものには行動をする"、といったことの大切さも改めて知ることができました。まさにDo Itです。自分からアクションを仕掛けないと（経験って意味でも、親愛関係って意味でも）何も得られないといったことは、すごく思い知らされました。

自分ってある意味特殊な存在なので、人間の感情について考えることがあるんですが、"感情を読むためには会話をせよ"、といったことと強く結びついたと思います。
コミュニケーション能力って、どの時代でも大切なのかもしれないな、といったことはマジで思いました。

おわりに

実は懇親会の後に、自分のチームに加え他のチームメンバーと二次会に行ったのですが、正直私は不安でした。こういったことは大体何等かの事件に巻き込まれることが多い印象だったので。
でもすごく貴重な時間を過ごせました。こう、自分と同じプログラムをたくさんやってます！みたいな人が沢山いたし、自分から話しかけてもみんな優しいし...励ましてくれたし。
こういう機会も、自分は本当に、学ばされました。色々と。

今も人間関係においていろんな苦悩がある自分ですが、

これからも自分らしく、でもできるだけ人と関係を深めて、生きていこう。

と思いました。

Epilogue

本当にここまで読んでくれた方、ありがとうございます。
こんな超大作書くのは今回が初めてだったので、読んでくださった方には本当に心から感謝いたします。
もう多分、そんな長文の記事を書く気力もなくなってくるので徐々に...()

これからも、私を応援してくれると嬉しいです。
もう一度言わせてください。本当に皆さん、ありがとうございます。

今年も終わりですね、もう（2025 12/29執筆）。
よいお年をお迎えください！

End.🏔✨

2025-09-14

ラテの3dayハッカソンインターン参加記・前編　～設計と戦って、実装で守り、バグ取りで勝つ～

Long Time No see

お久しぶりです。まっちゃラテです🍵
今回は、なんとあのラテがインターンでハッカソンに参加してきたので、その参加記を記そうと思います。

この参加記を書くにあたって一番怖かったのは、「時間」です。
あのー早すぎです。あの時まで就活なんぞ考えていなかったのに、なんか

「大学3年から就活始まるんだ～。ちょっと調べてみるか...あ、そういえばPaiza様のサイトにスカウトコンテンツがあったな。見てみるか。」

で、軽い気持ちで見たらなんか大量のスカウト来てて？？？になってました。

まぁ何を隠そう、私は高校1年の頃からPaiza様を頼ってきているヘビーユーザーなので✨
この頃はまだ B ランクでしたが。

そんなこんなで、ある企業様のインターンで、ハッカソンという文字が見えたので、
興味で、参加してみよう！！まぁ緑コーダー経験してるし開発しまくってるし大丈夫っしょ！！✨って感じで、参加しました。

またそういう参加記を記していきます。
結構長いと思われますが、最後まで読んでいただけると幸いです。私の当時の心の情景を踏まえながら見ていただけるとなお嬉しいです！！！

day1　～アイデア思いつくって、難しいね^^～
- アイデアソン
- プロトタイプ設計
- プロトタイプ設計　－コード・クラス設計ー
day2　～プログラミング歴6年目の威厳発揮～
- ハッカソン　－コード設計編ー
- ハッカソン　－フロントとバックの橋渡し編－
day3　～デバッグ大臣の試練～
全体の感想

(相変わらずサブタイトルが好きな人です)

では、書いていきます。
久々すぎて記事の書き方忘れてますが、自己流ということでお見知りおきください、、、

day1　～アイデアを思いつくって、難しいね^^～

今回のハッカソンは、4人で一つになって開発を行うチーム開発でした。私はいままで個人開発を行ってきたので、すごく緊張していました。
自分が本当にチームに貢献できんのか...？という不安を胸にしていましたが、今のプログラミング力があるなら、大丈夫と、自信をもって挑みました。

アイデアソン

ということで、ハッカソン最初の関所、「アイデアソン」が始まります。アイデアソンはその名の通り、アイデアを出そう！というものです(ざっくり)
アイデア×マラソン、ということですね！今回の開発テーマは「業務効率化」でした。...だとしても俺は何も思いつかない！！
本当に色んな企業様は、開発したいなーってアイデアって、どうやって思いつくのマジで？って疑問に思います。本当にすごい。

なので、当初私はすごく自信が無かったです。
自分はこの社会のシステムにはあまり不便さを感じたことが無かった(それとも自分がこの世の利便性に鈍感なだけなのか)ので、作りたいことも特になく...という感じでした。

でも、今回のアイデアソンではすごく親切で、アイデアを出しやすくしてくれたのです。
それが、 「マンダラート」 という手法です。これを使うことで、アプリケーション開発における利用者(ステークホルダー)を把握できるのです。
この人向けに開発したい！でこの悩みを解決したい！っていうことを一気に書き出せるといったものなのです。

特殊な存在である(?)私はとにかく、意味わからんけどこういう悩みはあるだろってプライドで書きまくりました。本当に合ってるかは正直不安でした()
でも意外とチームメンバーの方もそんな感じで、なんなら自分より少なかったので、正直安心していました()
(※別に下を見て安心する悪魔みたいな性格では決してないです)

そして、このアイデアたちをカタチにしていく、「アイデアスケッチ」を行いました。これも正直マジで思いつかなかったです...
とにかく、これはできそうだなー、これは悩みまくりそうだなーってものをピックアップしていきました。
自分は [AIを使った部署担当割り振りシステム] の自動化を思いついてました。工場でもなんでも応用の範囲は広く感じたので。

そうして他のチームメンバーの方のアイデアなどを見ながら検討したところ、[プログラマーに対するローテーション勤務型運動不足解消システム] というものを採用しました。
理由は面白そうだったからです★(応用も効きそうだったし)

プロトタイプ設計

そうしてアイデアが定まってきたので、いよいよプロトタイプの設計に入ります。
プロトタイプとは、いわばデモ版みたいなものです。最小限の機能を実装しよう！というフェーズです。

...の前に、まずは構成確認やコード設計の検討を行いました。
自分はもちろん(?)、バックエンドが好きだったのでバックエンド担当になりました。

この設計をしている時、私は驚きました。
まさかここで自分が今まで培ってきた競プロ力が発揮できるとは、思っていなかったのです！！✨

そう、なんとこのシステムで、最短経路探索アルゴリズム、ダイクストラ法を使おうとしていたのです！！正直めっちゃわくわくして一人で笑みがマジで止まらなかったので、多分私はあの時チームメンバーに不審者だと思われたことでしょう^^

そして技術、言語選定に。
自分がとあるプロジェクトを開発しているときに、フロントエンドで Flet (Python版 Flutter) を使ったことがあります！って言ったら、

良さそうですね^^

というふわふわな採用が決定されたのです！！正直結構わくわくしましたこの瞬間。

ということで、今回言語は Python 、フレームワークは Flet (Flutter) を使うことにしました。
あと言い忘れていたのですが、今回他のチームメンバーの方の開発経験はあまり無いようだったので、なんか勝手に私がプロジェクト・マネージャーになってました★

責任が重いっっっ！！！
(でもプロジェクト・リーダーは他のチームメンバーの方が担当していました。なんだこれ紛らわしい！！(心の声))

あ、しかも Flet も初めましての方が多かったので、基礎だけ自分が丁寧に教えてました。ちょっと...やっぱ俺って人に物教えるの好きなのかもしれない！！(なんかこの時興奮してた)
でもマジでこういうことがあるので、自分はプログラミングが好きで良かったなぁって、やっぱり心から思いました。

プロトタイプ設計　－コード・クラス設計ー

そうしてプロジェクト・マネージャーになったので、設計は丁寧にいかないといけない...！バックエンド担当はもう一人いたのですが、こういうシステム開発は行っていないようで、、、

しょーがないなー
じゃあ全部設計してやるよ俺が！！！

という感じで意気揚々とコード・クラス設計に挑みましたが...

「待て、どうやって設計をすればいいんだ...？」

ということになっていました。
ずっと個人開発で好きなように可読性優先で作ってきたので、いざチーム開発の設計となるとそんなわけには当然いかないのです。

day1が終わった後。
個人開発では「一人なら好きなようにできる」ということは身に染みていたので、実際に一人で設計を考えていました。
(なのでプロトタイプ作成にはまだ至ってなかったんですよねここまでで...)

流石は一人の時間。頭で煮詰まっていた設計思想がどんどん思い浮かんでくる...！！✨
って思いながら、一人(寂しく)頭で思いついた設計を書きなぐっていきました。

書けた...！！けど、また問題が。

「チーム開発で、しかも二人で、クラスってどうやって担当を分けるんだこれ...？」

やはり個人開発との差がここでも現れました。

# 私の設計思想としては、まず「コードの雛形を一度関数・クラス無しで作ってみて、そっからロジック分離させる」っていう手法だったのです。
今でもこの思想は変わってないです。でないと、いろいろごちゃごちゃになるので。特に頭の整理ができていないときは尚更....

でも今回はぶっつけ本番なので、しかも、私の今までの開発より大きいシステムの開発だったので、雛形を作ろうにも作れない...！！どうしよう！！となっていたんですよね...

じゃあ全体像を見据えるしかない。
てことで、全体でどういう挙動をするか、フローをホワイトボードに書きなぐりながらどうにかして、設計を行いました。
多分結構考えていたと思います。少なくとも2時間以上...？なんせしっかりとした設計は初めてだったので。

設計が終わっても、ここでも私の性格が出て、

「勝手に実装するクラス担当、振り分けちゃっていいのか...？相手は嫌がらないかな...？」

本当にチーム開発は大変です。身に染みてわかりましたこの時。
どのクラスも重要なところばかりで、本当に正直に言いますが、開発をあまり経験したことが無いのに大丈夫かな...とも思ったりしました。
(※嫌味では決してなく優しさで言ってます誤解しないでください)

いや、その心配は私にもありましたが...多分後で書きますが、自分の担当するクラスが一番、整合性って面で大変だと思いました()

大丈夫です。
私を誰だと思ってるんですか？
プログラミング歴6年目を舐めんじゃねぇ！！！🔥

ということで、本当のday1の終わりを迎えました―
そうして day2、ついに実装の幕が上がります。

言い忘れてました。自分にとって余裕の最短経路探索アルゴリズムは、秒速で完成させました。
実際に書いたプログラムを以下に載せておきます。チームメンバーの方を配慮して、なんなら自分のリファクタリングのしやすさを考慮して一つの関数にまとめた点が、自分なりに工夫した点です！

(原文です。ちなみにダイクストラ法はPythonで実装したことなかった(おい)ので、実装が楽なワーシャル・フロイド法を用いました)
(あとheapq使ってないですねこいつ)

import heapq

# グラフを保管するクラス(最短経路計算用)
class Graph:
    def __init__(self, node_count):
        self.node_count = node_count
        self.edge_count = 0
        # 仮想的な無限
        self.INF = 10 ** 9

        self.points = []

        # ダイクストラ法で使う用(隣接リスト)
        #self.graph = [[] for _ in range(node_count)]
        # ワーシャルフロイド法で使う用(隣接行列)
        self.matrix_graph = [[self.INF for _ in range(node_count)] for _ in range(node_count)]
        
        for i in range(self.node_count):
            self.matrix_graph[i][i] = 0

        self.init_points()
        self.init_graph()

        return

    # 座席の座標を初期化する(今は固定)
    def init_points(self):
        for i in range(self.node_count):
            x = i // 4
            y = i % 4
            #print(i + 1, x, y)
            self.points.append([x, y])


    # 座席をグラフ化する
    def init_graph(self):
        # 座席IDだけど机を遮る場合は辺は張らない
        edges = [
            [1, 2],[1, 5],
            [2, 3],
            [3, 4],
            [4, 8],
            [5, 6], [5, 9], [5, 10], [5, 11], [5, 12],
            [6, 7], [6, 9], [6, 10], [6, 11], [6, 12],
            [7, 8], [7, 9], [7, 10], [7, 11], [7, 12],
            [8, 9], [8, 10], [8, 11], [8, 12],
            [9, 10], [9, 13],
            [10, 11],
            [11, 12],
            [12, 16],
            [13, 14],
            [14, 15],
            [15, 16]
        ]

        for e in edges:
            u, v = e
            x, y = self.points[u - 1]
            x2, y2 = self.points[v - 1]
            self.add_edge(u, v, self.calc_manhattan_dist(x, x2, y, y2))

        return

    # マンハッタン距離を計算する
    def calc_manhattan_dist(self, x, x2, y, y2):
        return abs(x - x2) + abs(y - y2)
        

    def add_edge(self, u, v, cost):
        # 0-indexedに変換
        u -= 1
        v -= 1
        # (無向グラフの場合はu -> v, v -> uの辺を張る)
        #self.graph[u].append([v, cost])
        #self.graph[v].append([u, cost])
        self.matrix_graph[u][v] = cost
        self.matrix_graph[v][u] = cost

        self.edge_count += 1
        return


    # 全点対最短経路探索(node_count <= 500)
    def warshall_floyd(self):
        wf = self.matrix_graph
        for k in range(self.node_count):
            for i in range(self.node_count):
                for j in range(self.node_count):
                    if wf[i][k] == self.INF or wf[k][j] == self.INF: continue
                    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
        return wf

    # 一点対最短経路探索(1 node につきnode_count <= 100000)
    # def dijkstra(self):
    #    pass

    def print_all_dist(self):
        wf = self.warshall_floyd()
        print("Node count:", self.node_count)
        print("Edge count:", self.edge_count)
        for i in range(self.node_count):
            print(*wf[i])


    def calc_shortest_distance(self):
        wf = self.warshall_floyd()
        return wf

day2　～プログラミング歴6年目の威厳発揮～

さぁついにやってまいりました、ハッカソンのお時間です！！ハッキング×マラソンですね！
さぁ私は何を隠そうドMなので()、待ちに待ったコーディング地獄、待ちわびたプログラミング祭り...！！！プログラミングが大大大好きな自分にとってはすごく興奮していました。
ここで約5年間培ってきた可読性優先競プロコーディング力が発揮されるんだ...！！って。

そうして書きまくりました。...の前に、クラスは誰が実装するんでしょうかという問題が。
個人開発なら自分だけで実装できるし、整合性も取れるように細かくチューニングしながらできるけど、チーム開発なので...
細かくバグを見つけながらゆっくり実装していくにもいかないので...(時間がないため)

だからこそ慎重にクラスの設計をし、適当に関数・変数名を我流に合わせるように考えていました。私の我流の実装のモットーは「自分に見やすく、人に見やすく」なので、大丈夫なはず。リファクタリングもやりやすくするし。

ここでもやっぱり、チーム開発の難しさを感じました。我々人間は他の人の頭の中をありのまま感じ取ることはできない生き物なので、情報共有もしづらかったです。しかも、どうやって共有すれば自分の言いたいことが伝わるかわからなかったです。

なんか突然ですけど、この記事を見ている方へ
個人開発を経験している方がほとんどだと思いますが、一度これを経験してほしいです。本当にむずいから。(by 過去に参加記録をメモしていた自分)

ハッカソン　－コード設計編ー

とりあえずここで止まっていても仕方ないので、実装を優先しました。
フロントエンド担当は他の2人に任せたのですが、残りの一人と私でバックエンドを担当していました。

ていうか今分かったんですけど、フロントエンドってUI設計なんですね...画面遷移なんですね...！！
個人開発はごちゃごちゃにして開発していたので、正直フロントエンドとバックエンドは違いが曖昧だったんですよね...

そうしてバックエンドの実装を行いました。なんとかクラス担当を割り振り...
自分は、あるボタンを押した時の時刻管理を行うクラスを担当しました。この理由は、正直時刻管理は大体バグり散らかすし、他のデータとの同期を行うと思うと絶対大変なことになる、ということで、このクラスは今までつらい思いしてバグをこr...倒してきた自分が責任もって担当することにしました(メンバーとの兼ね合いで独断しました)。
他に、ある座席表を元にした座席管理を行うクラスもありましたが、そちらはもう一方のメンバーに託しました。

ふふふ...❤この時のコーディングの楽しさと言ったら...💕
大好きです。プログラミング。結婚したいですこの子と。
変数名決めるのも、関数を定義するのも、エラーがバンバン起ころうと、バグがどんどん出てこようと、もうすべてが楽しかったです。チームメンバーにとって読みやすくするって可読性も良く考えてたし。

これも正直、可読性を重視しながら今までプログラミングを行ってきたので、その力が役立てたと思っています。

あと、あの FF さん二人のおかげでもあると思っています。
私は前に、ある競プロの問題を実務的な可読性重視コーディングに直してみる！！っていうことを、開発の練習として行ったことがあるのですが、その FF さん二人が評価してくれたんですよね。しかも、しっかりと評価してくれて。
あの時クラス設計の評価とかしてくれなかったら、今でも複雑な設計になってたと思います。本当に心から、感謝いたします。ありがとう。

バックエンド担当の相方も、やはりクラスのコーディングは慣れていないようで...でも自分が教えられたので、ちょっと嬉しかったことを覚えています。
そうしてなんとか設計を終えることができました。

ハッカソン　－フロントとバックの橋渡し編－

さぁ...来ました。次はフロントエンドにあるボタン類と、バックエンド処理をつなぐ橋渡しを行います。多分チーム開発で一番の難所のような気がする...？
この処理もなるべく簡単にしようと、さらにクラスを2つに分けました。いやクラス分けすぎじゃね！？って思いながら、バグを取りやすくするならクラスを増やした方がマシだ(本当か？)という思いで分けました。

そのうち一つを自分が実装しました。これも、自分の手でこのシステムを作り出せるんだ...//💕って思うと、マジで楽しかったです。
おかしいこと言うかもしれませんが、苦しいとは本当に一回も思わなかったです。マジで。
(いや業務委託とかだったら泣いているのかもしれませんが...)

でも正直ボタンの処理を接続する作業は、個人開発で経験していることだったので、あまり怖くはありませんでした。なので普通の気持ちで実装していました。

ここまでで合計9時間くらいはPCと向き合って実装していたと思います。でも、やっぱり楽しかったです。

そうしてやっとフロントとの接続がやってきました。
正直に言いましょう。フロントとバックの概念が曖昧だった自分では、この接続もマジでわからなかったです★
バックエンド処理がよくわかっていても、フロントも同じように接続できるかというと、いけない！！

やっぱりここでも一人で考える出番。勉強ってみんなでやるより、一人の方が点数が取れるっていう意味が分かったような気がします。
いや、自分が I (MBTI)なだけかもしれませんが...

そうして一人でフローで全体の処理を整理。共有。検討。これの繰り返しです。
でもやっぱりそんなに、分からない時が確かに苦しかったけど分かった時がガチで爽快です。分野は違えど、まるで競プロの問題を解いているみたいでした。
もう薬物に近いです存在が。薬物やってます私(※やってません)

いや、こんなことをのんきに言っていますが、全然簡単ではないですよもちろん？？
接続前にもバグはフロントでもバックでもあります。ぜんっぜん簡単ではないです。

光ファイバなら線先丸くして斜めに摩耗して(この方法の名称忘れた...)上手くくっつければ戻り光や反射が起きないかもしれないですが、プログラムはくっつけても線先が違えば全然別の問題になります。これも、チーム開発で難しかったところでした。

正直フロントは何も指図していなかったので、どんな仕組みになっているか予想もつきませんでした。
しかもチームメンバーも、自分より開発経験が少ないから、全然対処法も思いつかず...なので思ったより100倍大変でした。

そうしてうまくくっつけようとしていますが、くっつけられない...
くっついてもバグが起こる。直す。再実行。エラーが大量に出る。本当にこの繰り返しです。
プログラミングが大好きと言えども、ちょっと泣きそうにはなってました。でも、心の中で

大丈夫、自分だって高校1年の時にエラー大量に出しまくって、バグ出しまくって、プログラミングやめそうになって、記事見ても何もわからなくて、泣きそうになって、ABCで思ったよりいい成果も出せなくて病んで、スコさんに八つ当たりしまくって、人と話せなくなって、人生が嫌になって。
こんなマジメンヘラみたいな自分という醜い人生を経験してきてるんだ。
こんなん序の口だよ！！！🔥🔥

って。思いました。マジで。

今いる逆境の立場は、過去の自分の逆境を思い出す。そうすると自然と打ち勝つ気力が湧いてくる。

そうして今も人生を気合だけで生きている私は、めげずにバグ探しを続けました。今までバグを探すために生み出した自分、「デバッグ大臣」も発動させながら。

よし...！！！やった！！
なんとかつながった！！

ん？でも今度はバックエンドの処理でバグが起きてる、、、><
そのバグはメンバーの相方が実装した、座席管理クラスで起きていました。なぜか、自分が担当した時刻管理クラスは正常に動いていました。
(※決して煽っているわけではありません)

そうか...と思いながら、day2の開発は終わりました。
明日(day3)も、この直しやんのー楽しハッカソン^^って思いながら、day2のインターン時間外はプログラミングをせずに、何も考えずに寝ました。

ここまででも、私がプログラミング大好きな感じが、伝わってくるでしょう...？
本当に好きなんですから。

あと、言い忘れてました。あのクラス設計を行ったときに、フロントエンド担当に 「なんでこんな多く関数を分けるの？クラスを分けるの？なんでもっと複雑にしてんの？」 って言われたことがありました。
個人的には、バグを取りやすくするためって答えましたが、実際それが正解とは限らないとは思ってます。
自分もつよつよの方のコードの真似で生きてきたのであまり良くわかってなくて...

でも、今までの開発でその恩恵を受けてきているのでマジで。多分合ってるはずですよね？企業で働いているプロジェクト・マネージャーの皆さん！！！

？

えーと、ここまで読んでくれて本当にありがとうございます！！
気づいたら12000文字に到達しようとしています^^こわ

ちょっとday3をここに書くと20000字突破しそうなので...一旦ここまでにしておきます。前編は。

day3はですね...今、自分過去にメモっといたものを見ながら書いてるんですが、なんか「フェロモン」って単語が見えるんですよね。
え、フェロモンってあれですよね？好きな異性のタイプがいたら首から匂いがする...ってやつですよね？過去の自分はいったい何を考えて書いているんですか？？おい過去の自分

ということで、無事12000字を突破しました。
後編へ続きます。まさか参加記で2構成にするとは思わなかった、、、

では、また後で。

追記？

チームメンバーは、同性3人です。
なおさらなんでフェロモンって単語が出てきてるのかが、謎！！！

2025-05-01

TOUPC正直参加記～沢山話して沢山恥かいた日～

(※前回の自分の記事たちを見ると大分ふざけたような感じで書いているようだったので、今回から真面目に書きます。ご了承ください)

Prologue

お久しぶりです、まっちゃラテです🍵
今回は前回の記事と打って変わって、TOUPC(Tokyo Online University Programming Contest: 東京通信大学プログラミングコンテスト)へオンサイトとして、参加したという参加記を記していこうと思っています。

色々ハプニングやトラブルはありましたが、、、

オンサイト

このオンサイトコンが開催された日は直近の、4/26です。
で、会場は東京電気通信大学の学内で開かれるのかなーと思ってたんですが、国立オリンピック記念青少年総合センターで開かれました。

結構、それまでにたどる道としては迷いますが(自分も少し迷ったし)、建物は大きかったのを覚えています。で、教室も意外と広かくて驚いていました。

コンテスト前

(多分、なんかコンテストへの不満を書いている気がしますが、個人の意見なので受け流してください...)

コンテストは、3,4人のチームで取り組んでいました。
まずコンテストはTOUPC独自のコンテストサイトで問題を見て提出してっていうのをやるのですが、そこでAOJのログインが必要になりました。

でも自分はAOJのアカウント(自分用)を持っていたのでそれを使おうとしました。
しかし主催者様から受けた説明では、「チーム用のアカウント」を作ることを指示されました。

絶対ちゃんと主催者様は説明していて自分が聞いてなかった(おい)だけかもしれませんが、とりあえず自分のアカウント作って、それをTOUPC独自のコンテストサイトでチームアカウント作っていぇーい ↑ ってやればいいんでしょって思ってて()
自分がチームアカウント作る！！って言って先陣切った挙句、勘違いでスタートが出遅れる始末になってました★
(チームの皆さん、あの時は申し訳ございませんでした、、、)

あであと、コンテスト始まる前に、実は(自分のプライドで)あってはならない、暴言を吐いていました()
違いますよ？コンテストへの不満の爆発じゃないです。

自分のPCがなんかバグりにバグりすぎて、フリーズしてたんですよ★

...いや、まぁね？
オンサイトとか全然慣れない環境で、多分PCも恥ずかしくて穴があったら入りたいみたいな気持ちで強制フリーズを仕掛けたというのもあるかもしれないですが

コンテスト当日、しかも始まる直前でそれはないわ...って、自分のPCに引いてました。
で、マジで強制シャットダウンしてもなんか治らず、UIがめっちゃ小さくなるし、PC内のメモリがバグってるせいかシステム内部エラーめっちゃ出てくるし、画面おかしくなるしで、マジで「え、これ治るん？^^」って思ってたので怖かったです。。。

とりあえず強制シャットダウン(多分うちのPCめっちゃ痛めつけてる)を2回施してなんとか治りましたが...
スタートはうちのチームだけめっちゃ出遅れました★

でしかもいまだチームアカウントの登録ができてない、、、泣
しかもチームアカウント作った時に自分が登録したパスワードを自分で忘れ、多分アカウントのデータベースに余計なものを残していってしまい()
(すみませんでした)

で、やっと初めてチーム連携ができました★(開始してから5,6分経過してる)

そういやコンテストの不満を書きたいのですが()
同一ネットワークの同時接続数の限度があるのか、コンテストサイトに重くて繋がるのに結構時間がかかってました、、、
繋がらな過ぎて、最初は携帯のモバイル通信を使って携帯で問題を見てました。

そこを改善してほしいです！！(要望)

席のグループごとに違うネットワークを使っていたのですが、これはいいアイデアですが...そこだけが不満でした

?

え、でもなんか私のPC謎フリーズ現象、実は去年の「緑以下コン」というオンサイトがあったんですが

そこでも同じ現象起きてて泣きそうになった覚えがあります^^

なので、もうフリーズには慣れ

てないよ！！！泣

コンテスト中 (問題ネタバレあり!)

とりあえず正気を取り戻し、遅れを取り戻すようにできるだけ貢献しました。コンテストの問題は全部で 14 問(A~N)で、自分はそのうち 2 問(D, I)を解きました。他に 2 問を考えていましたが、思うような実装や考察ができずに沈黙(という名の他力本願)をしていました。

自分が担当した問題は、全部自分の得意分野でした！！！✨

D

こういう問題でした ↓ (問題文要約)

A と B からなる文字列 $S$ があります。
今からそれぞれの文字を独立で A か B に好きなように変えることができます。
操作後の文字列において、どの連続する $k$ 文字を見ても A と B が両方含まれているようにしたいです。
そのためには少なくとも何回の操作が必要ですか？例えば $S$ が AAABB、 $k=3$ のとき、AAA と AAB 、ABB が連続する $k$ 文字の部分文字列となります。
そこで AAA (1~3 文字目)に関しては B が一つも含まれていないので、例えば 2 文字目を B に変化させて ABA とすれば、問題の条件を満たせます。

自分はこれを見て、最初は A と B の個数を数えながら $k$ 文字の間隔を維持しながらスライドして数えていく、という方法でした。
でもなんかサンプルもあってない^^

てことで色々考えました。チームの人々と話し合ってたら、次はランレングス圧縮を思いつきました。
チームの方と一緒に実際に書きながら考えてみたら納得してくれたので、その実装方針で行きました。ACしました！！

D 自分なりの解説

公式の解説とちょっと違っていたので、ここで説明します。厳密性とアルゴリズムの具体性については、ちょっとあれかもですが...

とりあえず書いて思ったのは、A と B を連続する区間ごとに分けて考えるということです。
例えば $S$ が AAAAABBBB 、 $k=4$ を考えてみます。今のままだと 1~4 文字目、2~5 文字目、6~9 文字目が問題となっています。
これの条件を満たすためには、例えば 2 文字目および 9 文字目をそれぞれ B と A に変化させればよいです。

これをランレングス圧縮の観点から見てみます。
与えられた文字列を圧縮すると、 $(c,p)=$ (A, 5), (B, 4) という組が順に生成されます。

ここでそれぞれの組に注目すると、変更するべきは各区間において、連続する文字数が $k$ 以上のものです。
そのような区間における部分文字列には、少なくとも $\lfloor \frac{p}{k} \rfloor$ 回の操作が必要になることが分かります。これは実際に実験するとわかります。というのも、その区間内で新たな「条件を満たさない文字列の区間」を作らなければよいためです。

前の例でいえば、例えば 5 文字目を B にしてしまうと、今度は (B, 4) という圧縮が操作によって(B, 5) になってしまい、変更する箇所を一つ増やしてしまいます。
つまり、端的に言えば「1 つの区間内に新たな、長さ 1 の区間を作る」といったことを行えばいいです。
(絶対この説明わかりにくいですが、公式解説の「見ている連続部分文字列の右隣の文字とは別の文字に変更する」といった趣旨に乗っ取っていることが分かります)

#

長くなっちゃいました。とまぁ、このような感じで解いてました。
ちなみにランレングス圧縮が思いつく前の方針で解いてるのもあって、結構もうこの時点で大分経ってる気がします、、、

I

こういう問題でした ↓

今から $N$ 個のボール $C_1, C_2, \dots , C_N$ が順に流れてきました。
これらのボールにおいて、同じ色のボールが $M$ 個連続する箇所をすべて抜き出す、という操作を繰り返します。
この操作を終えた時、あり得る残っているボールの総数の最小値を求めてください。

自分はこの問題を熟読したところ、もうstack + ランレングス圧縮しか考えられない！！と思いました。実装したら、ACしました！！
(これは昔のABCの問題で同じようなものを解いたことがあったので比較的楽でした)

#

こんな感じで参加してました。他に問題を考えていましたが、結構考察してもむずすぎだろ！って問題と、得意分野だ！実装できるけどなぜかWAになる、、、みたいな問題が多かったです。
でも、自分はこうやってオンサイトで真面目に問題と向き合える時間っていうのはすごく貴重だったので、解いててめっちゃ楽しかったです。
というか、やはり問題を自分(とチームメイト)のコーディングで解けるということがそもそも幸福だと思いました✨

というのも、通常、「競プロ」ってコンテストに参加している時はずっと孤独の身じゃないですか。
でもこうやってチーム戦で、自分が問題が解けることによって「チームメイトと一緒に協力できてるんだ...！自分、チームに貢献できてるんだ...！！」っていう喜びがすごくこみ上げてきたのを覚えています。

だからこそ、オンサイトコンって本当に行く価値がある(というかそれしかない)と思っています。
なんというか、「自分も競プロができるんだ...高校から継続してきたプログラミングの能力が付いてるんだ...！！✨」っていうモチベの向上にもつながるし、いいこと尽くしだと思っています。

問題が解けなかった時の感情？

もちろん、先ほど記した「緑以下コン」では、自分は散々な結果に終わってめっちゃくちゃ悔しかったこともありました。
それでも競プロを続けられてるのは、なんというか自分のプライドもありますが、

多分この界隈の圧...()(いい意味で)

というか、やはりこの自分のいる競プロ界隈は、プログラミングを実用化できるように勉強していることより、プログラミングを楽しんで「遊び」として学んでいることを、優先？している方が多くて、それに自分も自らのっかっていると言ったらいいでしょうか、そんな感じがしてます。
こういう方々のXのツイートなどを見てみると、「日々精進を楽しんでいる人がいるから自分も頑張ろ」とか、「やはり根っからの競プロerだなこの人()」とか、励まされたり(いい意味で？)呆れたりとか、いろんな感情を抱いています今でも。

だからこそプログラミングをやめられないというか！！！！
いや、自分は絶対やめる自信なんて0なんですけど、本当に謎の競プロerさん達の「静かな圧」がかけられていて、やめたくてもやめられないと思っています。

でも、ふと考えるんですけど

今の競プロ界隈が無くなったら、自分ってどうなるんだろう...？

っていうのは思ったことがあります。多分、これを考えていたらキリが無くなりそうなので書きませんが、そういうこともたまーに考えます。
(というのも未だ鮮明な答えが出てないです、、、)

(でもこれは「自分は絶対やめる自信なんて0」って言葉と矛盾するのでプログラミングはやめては無いと思うけど、うーん...)

あ、で、話題を戻します。
こういうことがあって、別に解けなくてもいいやー^^という訳では決してなくて、マジでめっちゃ考えたけど解けなかった悔しさをぶつける...という意味ではないですが、競プロerさん達のツイートを見て励まされるということで、今の競プロ人生が継続できると、自分は思っています。

ま、自分はなんでも根性で生きている人なので、競プロが嫌になっても絶対にプログラミングを嫌いにならないっていうプライドがある🔥のもありますが、、、とりあえずそう思っています。

話を戻して...

ごめんなさい話過ぎました。
とりあえず、コンテスト中はすごく静かで(最後の方はちょっと他のチームの皆さんの独り言が多かった気もしますが...())集中できるような環境でした。自分は考察用としてページを自由帳を持ってきましたが、考察系が多かった？と思うので結構な勢いで役に立ちました。

で、解説も丁寧に教えてくれました。コンテスト主催者(ウルズニャーさん(Xのプロフィールに飛びます))の解説も、ちょっとした歓談もあって聞きやすかったです！
(最後の問題の解説だけ、個人的に何もわからないので寝そうになりましたが...())

懇親会

解説後に閉会式を行い、その後は同じコンテストに参加した競プロerさん達との懇親会が行われました。
もちろん、自分もしっかり話しました！！

...えーと、正直言うと思ったより話せてないです^^
(だってやっぱり大人数での会話ってなんか知らんけどめっちゃ緊張するもの！！)

それでも話せたつもりではありますが...もっと積極的に話してみたかったです。

でも勘違いしないでほしいのは、「やっぱり同じ界隈同士の人との交流は楽しい」ということです。なんというか、(自分含め)個性的な人がたくさん存在しているので、不思議な気持ちにはなりましたが色んな価値観を持つ人(自分含む)との会話を楽しめたので、すごく楽しかったです✨

懇親会に行ったことがないけど行ってみたい！っていう人は、ぜひ来てみて実感してみてください。
自分も、「緑以下コン」の懇親会が最初だったのですが、マジで不思議な気持ちになります。爽快感と、不安が入り混じったような感じになります()
でもそれ含め、その感情にしろ沢山の人と交流ができるので、「今日は充実したな～」という自己満足感を得ることができます！！(多分)🍵

懇親会その後

懇親会の後に沢山の競プロerさん達を引き連れて、ご飯に行きました！！✨✨

って、やりたかったんですが、東京のお店が小さくて...(いや、人が多すぎて空き場所が無くて)。
どんどん解散していきました(泣)

そこで得た教訓は、「夜ごはんは予約しろ」でした★

感想

今回のオンサイト、実は自分は 3 回目のオンサイトでした。なのであまりオンサイトの経験はないのですが、それでもやはり、思いつく言葉は「コミュニケーションは大事」ということです。
いや、自分もそうなんですが競プロ界隈の方々は、なんというかあまり会話に活発的じゃない感じが個人的にします。でも、天才しかいない、みたいな。
もちろん活発的な方もいます。でもこう、自分の言いたいことをよく人に明かさないような方が多い気がして。いや自分がそうですが。

なので、興味ある人・ちょっとでも知っている人には自分から話しかけてみるっていうことは、こういう場合に限らずどの時でも大事だと思いました。いや、自分がそれできてないんですが、、、努力はしてるつもりですこれでも。

風の噂から聞いた言葉だと、

"聞くは一時の恥、聞かぬは一生の恥"

というものがあります。意味は

知らないことをたずねるのは、その場は恥ずかしい気がするが、聞かずに知らないままに過ごせば、生涯恥ずかしい思いをしなければならない。知らないことは積極的に尋ねるがよい。

です。(引用元: コトバンク)

個人的な説明とは意味が違うような気がしてますが、自分も「自分が知らないことを知っている相手に話す」「自分が知っていることを知らない相手に話す」ということに関しては少し恥ずかしい感情を持っています。理由は正確には言えないのですが(隠してるわけではなくて本当に曇って見えない)、なんというか、絶対に失礼な話題じゃないのに失礼な話題として処理されてしまって、そのまますーっと消えていく...みたいな感じです。

それで言いたいことを話せなくて後悔をすることが多い自分ですが、「やらない後悔よりやる後悔」を優先して生きているので、「とりあえず話せ」と内心から外心にずっと話しかけてます。まぁそれで結果論として後悔するということはありますが...マジで良くない話題とか話さない限りは、日常会話をした方がいいということは、自分の経験上で結構知っています。

もうなんか自分の性格を語ってるみたいになってるけど...

とにかく！！話すことは大事ということ！！
話さないと何も始まらないので！！

ごめんなさいもっと自分語りしますね()
去年の大学 2 年生の自分、なぜか仲良い友達と話さなくなってそっから話しかけようと思っても勇気でなくて今全然話せてない、、、みたいな状況になってるので、本当にマジなんでもいいから話す！！ということを心掛けたいです自分が。
(それでも相手の状況も状況なんで、、、仕方ないことではないけど仕方ないみたいな...)

以上自分語りでした。
でも、自分はオンサイトってコミュニケーションがないと成り立たないと思ってて、結構熱心に書きました。チームで組むも個人で取り組むも、どっちにせよ誰かに助けを求めるようなものなので、自分はこの感覚を体験して改めてコミュニケーションの大事さを教わりました。

もちろん、競プロの能力や知識を確立するってのも大事ですが、自分はよわよわ緑erです。
本当はこの問題のレベルは自分は解けないといけない！！っていう問題が解けないこともありました。

でもコミュニケーションはそれ以上に大事なものだと思いました。
コミュニケーションなんて、人と人との交わりで初めて成り立つものだし、競プロの知識の確立は正直一人だけでもできると思っています。

その一人で知識を付けるからこそ、人とはあまり話さないってのもあるし、しっかり人と向き合った方がいいということは、言えると思っています。

コミュニケーション基礎 I という人生の必修科目も取れてない奴が言うことじゃないですね！！！泣
自分も競プロもコミュニケーションも頑張ります。

そんな感じのことを思い出された、貴重な経験をしたという日記でした✒

Epilogue

Question

精進の時間を取る前に、課題とレポート終わらせないと、、、あとバイトも入ってて、どこで精進すればいいと思いますか？

Answer

心の中に、いつも"競プロ"はあります。

End. ✨💻🖊

2024-09-03

ラテのAHC036冒険記～バイトも集中できないほど熱中した、夏の終わり～

前提

この記事でいう「H」は、ヒューリスティック(Heuristic)の頭文字をとったものです。
決して卑猥な意味ではないということを念頭に置きながら、お読みいただけると幸いです。

Prologue

お久しぶりです。UnionFind教信教者ことまっちゃラテ🍵です。

いつもABCに本気になりながらレートが全く増えずに泣いていた(実際は泣いていません)私が！！
今回、AHC036に参戦しました。気分転換替わりです。
(いや、レート減らないっていうから...！！)

AHC参加者さんたちは必ずといっていいほど記す「冒険記」を、パクr
参考にしながら、個人的な情緒を勝手に混入させながら記そうと思い、この記事を書いています。

Hはねぇ...いいですね。
過去に自分、一回※1だけ参加したことあって、その時にも冒険記を載せたと思われます。
あれもあれで大分備忘録チックで、ふとした時に読み直したことがあったんですけどマジでわかりずらいな...と思いました。

今回こそは説明と、この日この日で何を考えていたかを詳しく簡潔に

記そうと！！！！！！

思いますが全然書けませんでした...
それでも、意図をくみ取って読んでいてくれれば幸いです。

ちゃんとは書いています。ちなみに、Hしてる最中で実際に書いた日記そのものも一応書いていますので、H初心者の方は書き方を参考※2にしていただけると嬉しいです。

では早速、冒険の幕開けと、させていただきます。引用されている箇所がありますが、これは私の日記の原文です。読まなくても勿論、大丈夫です。
問題文などは、こちらのページに載せておきますので、参加していなかった方はぜひ解いてみてください！！

※1 実はAHC3回目ですが、2回目はマジでむずかったのでほぼ参加してませんでした...
※2 日記とは、「自分で行ったことを自分なりにわかりやすくまとめたもの」です多分。私はだいぶ端折っているので参考にはならないかもしれません。

day.1

ラテのAHCが始まった。
過去の経験からしっかり問題を読み、マジで理解してない部分あったけどとにかく実装を頑張ることにした。

「実装を頑張る」...？

長期コンテストは、大体サンプルコードがあるはずである。
そうこの男

サンプルに全く気が付かずに自力で最初から実装としていたのであった！！！
(自分はH初心者なのでだいぶ無謀な行動を行っていることになる)

しかもこの実装は $3$ 時間かかり、しかも、まったくACできないという、まさに逆の意味で最高の瞬間といったところであろうか。
皆さんは私のポストを見ればわかると思われるが、めっちゃ焦ってたね☆

(実際のポスト)

やばいH熱くなってきた！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

←スタートに立ててない人
— まっちゃラテ@🥠 (@matcharate_12) 2024年8月23日

サンプルに気づくのに5時間かかるバカ、ここに参上--------------------

無事、サンプルを提出し、正の得点を得る。 $460593$ 点。この時点では暫定117位。ふむ...

そしてサンプルをちょっといじくる。ここで最初に考えたテクニック

「BFS+経路復元、復元に従って最短経路を移動をする」

を、愚直に実装した。そして関数化。バグらせまくる。泣きそうになりながら(早い)、この日のHを終えた。

サンプル気づくのに5時間かかる。サンプル提出して460593点。この時点で117位。
単純パスの求め方が関数化させるとバグる^^

day.2

この日は、頂点の移動方法について吟味していた。
サンプルでは「DFS+ $(x,y)$ に対するユークリッド距離による最短経路」で移動を、としていたけど、これを「BFS+経路復元」に変更。
day.1 で泣いていた関数化は、隅々までデバッグしまくって(約 $2$ 時間)、やっと完成。

このコードを seed=0 のケースで実行すると、サンプルのままでは $6863$ 点だったが、このコードは $6107$ 点！！
もう、楽しいこの時点で。提出すると、 $356812$ 点。2日目の変動があって暫定166位。うんうん、いいんじゃない？いいよね？？

さらに改善を進める。次は、この問題のお味噌である、 $B$ をどうやって確定させるか、を考えた。
サンプルでは、 $A$ から1つ1つを $B$ の同じ index の場所に入れていたが、これは明らかに無駄。
ということでこの時は $B$ をふんだんに使う作戦に変えた。

ここでは、一回の操作で1つの頂点の信号を青にする操作を「一点信号操作」、複数の頂点の信号を青にする操作を「区間信号操作」と言うことにします

$B$ をふんだんに使う作戦、すなわち

「 $B$ をとりあえず $L_b$ 個全部つけておく作戦(一点信号操作)」

を実行。そして実装。提出すると、 $302528$ 点。暫定218位。順調ではあるけど順位変動大き～！！

深夜。
Hしか考えられなくなった私は、またPCに向かってコードをカタカタ書く。次は、 $A$ の構築方針である。
このとき考えたことは、「最短パスに含まれる頂点番号の配列を元に構築する」方針であった。これは勝手にハフマン符号と呼んでいた(定義とは全く違うと思われるが)。

そう、 $A$ を構築することに頭を回していた。まずはね。最初は、 $A$ のどこに頂点番号があるかどうかの配列を定めた。

しかし、Heuristic の神様ことThunder様の本(通称 Thunder本)を読んでいた自分は、今回は伊達にHをするだけじゃなかった。

ビームサーチ....

DFS+ユークリッド距離最短でパスを求めるのを、BFS+経路復元でより最短パスを求めるのに変更。
sampleコードをseed=0で実行するとscore=6863、BFSのコードではscore=6107(約700強減少！！)
このコードを提出すると356812点。2日目の変動があって166位。
次にBをふんだんに使って、Lb個のパス頂点をつけておく作戦。このコードを提出して302528点、218位。変動大き～

深夜。最短パスに含まれる頂点番号の配列を元に、Aを構築する方針に決めた。Aのどこに頂点番号があるかどうかの配列を定めた。
いまだビームサーチは思いつかない...

day.3

$A$ の最適な構築をまたもや模索中。うーん、無理！！！！！！
とりあえずday.2の方針を採用して、頑張って実装。なんかうまくはいってるぽいけど...

そうすると一点信号操作が多くなっちゃった。なのでとりあえず $A$ の連続部分列 $[x,x+L_b$ ] $(1\le x\le L_a-L_b+1)$ の領域を $B$ にそのままどーんと突っ込んでみる。

しかし、それでも最短パスとして含まれない頂点は、明らかに何も考えないで最後に取ることになるので、一点信号操作になっちゃった。ケースによってはスコアは変わらないなと思った。
一旦、この日の提出を見送ることにした。

(時間は待ってくれないというのに...)

リファクタリングday。これは方針が思うように思い浮かばなかったことを意味する。
最短パスの再計算無しで、連続するAの領域をまるごとBに格納する、区間信号操作の方針に変えてみた。でもそれで最短パスに含まれない頂点は1点信号操作なので、ケースによってはスコアは変わらん気が...
一旦提出は無し。

day.4

day3で組んだハフマン符号作戦では、最短パスに含まれる頂点数に従って...って計算するとバグおきた。最短パスの長さが $0$ とかになったりしてた...
なのでいったん $4$ 頂点のハフマン符号(?)として実装。沢山のリファクタリングを通し、私の恒例行事夏のHバグ散らかし祭りの主催者となり、デバッグ大臣と化する。

...自分もしかして人間デバッグなのでは！？！？✨

と錯覚したのも束の間。
実装を終え、seed=0 のケースで実行すると、スコアは $8100$ 点。さぁ何が起きているのかわからないが絶対によくないことが起こっていることだけは確認できる。

しっかりと方針をフィードバックしてみる。すると、確かに最短パスに含まれる頂点はすべてあっているが、その後に移動できる頂点が限られてしまっていたらしい。これにより一点信号操作が多くなっていた。

ということで
我が家の秘宝、"""BFS""" を使って全頂点対最短経路を $O(N(N+M))$ で計算することにした。わーシャルフロイドを使ってもいいけど時間がかかりそうだったので。

そして、沢山の $A$ からの採用候補がある中で最適なものを選ぶ必要がある。で、採用基準となるスコア evaluated_score を定める。
BFS実装前の採用基準は「最短パスに含まれる頂点の個数が多い方を採用する」だけだったので、あまりにもむにゃむにゃしてきている気がしたのだ。

訳:
1ターン先のことを考える貪欲なので、これが本当に最適かどうかわからなかった。

ということでもう一回フィードバック。次に移動する頂点はどこを採用するかを、直感的に次の3つが思いついた。

採用した $A$ の区間に対する、距離の総和の平均値(小さい方を採用)
採用した $A$ の区間に対する、距離の中央値(小さい方を採用)
採用した $A$ の区間に対する、今いる頂点における最短距離が $2$ 以下の頂点の個数(大きい方を採用)

まず平均値を実装。できた。テスト。

全然うまくいかない☆

次に中央値を実装。中央値、どうやって効率的に調べられるんだ...？と思っていると
あの時解いたことある問題を思い浮かべた。中央値の定義から単調性を見受けられたので、二分探索が適用できそう。

そして実装。案の定ガッタガタな実装。ABCだったら明らかにWAだろの実装。
それでもAHCの神様は大目に見てくれる.....と思っていた。

まったくスコアが減らない☆
どんな基準にしようとスコアが悪化する。
神様は大目に見てくれない。しかしその誠実さは環境の良さのものをいう。ただ自分のデメリットが垣間見えている。

さぁ、自分はどうしたらよいのだろう...？

深夜。またもやHしか考えられない。
もう一回フィードバック。一点信号操作、 $L_b$ 個の領域すべての操作よりも、もっと $B$ の空き場所を活用しなければ無理だということが結論になる。
ということで 「 $B$ に対して $B_{index}$ に一点信号操作を行うとき、通過した(次ターンでは使わないと仮定)頂点の信号操作を排除する」方針にする。

まぁ理想的な更新ではあるけど...
これをするなら、 $B$ のどの最大長の連続区間を計算しながら、という感じに変更することになるので、めげずに実装。

B.back() (back 関数は配列の末尾を返す) は現在いる頂点として固定。なのでこの位置は「「変えちゃいけない」」のでここは固定。

さらにどこかのパスをつなぐ方式。今までは一点信号操作をしていた。
ここからさらに効率的に動く必要がある。

ここで考えたことは、とりあえず無駄な部分に次の $A$ の候補を突っ込むことで、効率的に $B$ を更新すること。その名も、「つぎはぎ作戦」を強いることに決めた。

いまだビームサーチは、何もわからない。

(原文)

4頂点パスハフマン符号の方針を、始動。たくさんのリファクタリングを通して、バグ散らかし祭りを開き、なんとか...
と思ったらスコアはseed=0で8100↑。
確かに最短パスに含まれる頂点としてはあっているが、その後に移動できる頂点が限られる。
ので、全頂点対最短経路をN(N+M)で計算して、今いる頂点と近く...
距離の総和の平均値、中央値、dist<=2の点...何してもスコアが悪化する。これは潮時というものなのか...？

1点更新、Lb個固定更新よりも、もっと活用しないと無理という。とりあえず、b_idxを操作して、通過した頂点信号は無しとする。
これが理想的ではあるけどこれをするなら、Bのどの最大長の連続区間を計算しながら、
B.back()1点更新+どこかのパスをつなぐ方式、すなわち"つぎはぎ作戦"を強いるしかない。ビムサは分からない。

長っ！！！！

お風呂に入ってきます。ではまた後程🌙

こんにちは(^^♪

お風呂から出ました。眠いですが折返し頑張りましょう！！

day.5

day4 の方針を実装してみる。できた。さぁテストしてみよう。バグった。

バグってる。

バグってるね。。。

ぶつぶつモニターに文句言いながら、計 $4$ 時間越えの地獄のリファクタリング＆デバッグ。目が無事死亡。

とにかく、前に記した $B$ の採用基準を、「必ず最短パスで移動する」こと前提に、基準を「最短パスに含まれる頂点のうち大きいもの」とした。

ABCでWAになるコードはAHCでもWAになる！！！ということでガタガタだったにぶたんによる中央値計算を廃止。
そして、ついに「つぎはぎ作戦」を実行。あまりにも、目が死んだ。。。。

苦労の末、seed=0でテストしてみた。なんと $4611$ 点！！！
提出してみると、 $231000$ 点！！(暫定380位)
Niceすぎる！！！！！✨✨✨H楽しすぎる！！！！✨✨✨

day4のバグりまくった箇所を気合で修正(計4時間かかった)。
最短パスで必ず移動する、として、貪欲法はただ最短パスに含まれる頂点の個数を評価方法とした。
中央値などは廃止！こうして、つぎはぎ作戦を始動し、seed=0で4611点！！
提出してみた。231000点！！(380位)素晴らしい軌道修正を行った。

day.6

day5で起動修正を喜んでるのもつかの間、まだまだ順位は伸びない...

ついに、"アレ"に手を付けるときが来たか。

あれから、 $A$ の構築がマジでうまくいかない。これがうまくいかないせいで、 $B$ の評価も悪いということに気づいた。
でも何も思いつかない。さぁどうしたものか....

はっ
と思い立ったのは、Thunder本(敬)に乗っているテクニックを思い出した。

焼きなまし法...！！！

あまりにもH初心者のやつが...こんなのに手を付けられるわけがn

いや！！！
やるしかない。

やる！！！！
時間を犠牲にしてでも実装してやる！！！

(あれから $3$ 時間後)

できた！！！まずは山登り法を実装した。そのために関数化をグローバル化することにめっちゃバグらせていた。
山登り法は、「最短パス移動を固定」とした前提での $A$ の近傍評価を試してみることにした。このときの近傍は「ランダムに選んだ領域を、反転させる」というものだった。

(でも今考えたら明らかに近傍として悪い気するな...)

よし、上限シミュレーション回数はどうだろうな～(ホクホク)^^...

え

$40$ 回で $2300$ ms ...............................................

(^o^)/

こうして私のHの幕は、下ろされたのであった。

Fin. ✨

いや待て！！！
この方針が悪かっただけだ！！！

ということでめげずに次の方針を考える。ここでも、はっとして

ビームサーチ...！？

というのも、普通のビームサーチを実行すると $B$ の選び方と頂点の移動の仕方とかたくさんあるのであんまりちょあよ...

訳: $A$ の選びも $B$ の選びも次行く頂点の選びもあって時間絶対間に合わないだろこれ！！！！泣

いやこれできるのかこの実行量で！？という半信半疑の念を抱きながら、いざ実装。
(もちろん、Thunder本(敬)を読みながら)

えーシミュレーション回数が $20$ 回で限界です☆
ということで、おやすみなさい🌙

え！？！？！
さらに時間量を減らさないとアカンの！？
何！？絶対スコア計算で時間かけてるじゃん！！！

だってどうやって差分計算するのこれ。。。。。。。。。

軌道修正で喜んでいる束の間、望んでいたヒューリスティックアルゴリズムを試してみた。
Aに対する最短パス移動固定山登り法、pos_from->pos_to愚直ビームサーチ...
どれも実装に時間をめっちゃかけたのに、1回の計算で暫定スコアを計算するのに時間がかかりすぎていてシミュレーション回数が30以下で間に合うか間に合わないかの瀬戸際だった。泣いた。

day.7

初心に帰ろう。

「こんな灰色Herが高度なアルゴリズムを扱えるわけがない！！！！」

初心に帰った。
のほほんとVisualizerを見ながら、移動の際の無駄な部分を探して、そこをチューニングすることにした。

まず、区間信号操作が全然できてないことに気づく。この操作の回数を計測すると、全体で $4600$ 回の操作に対し区間操作はわずか $900$ 回。つまり一点信号操作が大半を示していることになる。

一点信号操作は便利だけど、スコアはどんどん悪化していくだけ。これをもっと小さくさせないとスコアは下がらない....

そこで、「最短パスに含まれる頂点数」が高い順に $B$ として選ぶんじゃなくて、「頂点 $u$ と頂点 $t$ の距離が $L_b$ 以下であるような $t$ の個数」が大きい順、という基準を追加してみる。

テストしてみるとseed=0のケースで $4311$ 点！！提出すると、 $216406$ 点。(暫定順位は忘れました)

さらに現時点の $B$ でどこか $1$ つの要素が無駄になるので、そこを優先して次に行く頂点番号に更新、ということをしてみると

もっと良くなる。

そんな無駄な要素を見つける基準でも、「頂点 $u$ と頂点 $t$ の距離が $L_b$ 以下であるような $t$ の個数」基準を追加してみると、seed=0で $4156$ 点！！！

そして提出。 $205406$ 点！！！(暫定順位は忘れました)
まだまだ $20$ 万の壁を乗り越えられない....

そして人類が寝てる間、一人明かりをつけてHをする始末。
まだあの焼きなまし法をあきらめていない。← まったくしぶとい奴め。

とりあえず少しでも...！
ということで簡単な改善から入る。

まず $B$ に対して、頂点番号 $k$ がどの index にあるかどうかを高速にすることを考えた。「 $B$ に入っている頂点と、その要素番号」を組として(連想)配列として管理することで、 $O(L_b)$ から $O(1)$ に落とすことを考える。

なぜにここでもバグる！！！バグの女王様は自分を弄んでるように見える...

めげずにデバッグ( $1$ 時間)。でも、 $B$ に同じ頂点番号が複数入ることを考慮していない私は、この時点でも女王様が思わず笑みをこぼす。

このときのデバッグに assert 、あと cerr (エラー出力) を何個入れたか全く覚えてない。。。。
そして儚く時間だけが過ぎ去っていく。

配列だけじゃ、複数indexをまとめられない。
え、じゃあ map (連想配列) を使うのか...？マジで？

B_index、最適なものを探すことになるのか...？
ねぇ、それこそビームサーチじゃない！？！？！？

結局ビームサーチじゃん！！！！
差分計算が高速にできないと話にならないじゃん！！！
何、私のこと嫌いなの！？！？！？
もういいよじゃあ！！！私たち別れよ！！！！
Hくんなんか大嫌い！！！！

はい。予想しましょう。
盛大に滑りましt

とにかくどうしたら、ビームサーチが、できるんだろう...？

ラテの冒険は続く。

そいえば自分灰色Herなのでそんなアルゴリズムを扱えるわけがない！！てことで初心に帰る。
Visualizerを見ながら無駄な部分を探して、そこをチューニングするしか思いつく手はない。

ということで「最短パスに含まれる頂点数」基準でなく、加えて「dist[u][t] <= Lb なるtの個数」基準を加えた。
seed=0で4311点に！！提出した。216406点。
さらに長さ1の1区間で次回見ようとしている最短パスを考慮し、消していいようなB-indexを計算し、貪欲的に採用してみた。seed=0で4170点！！
さらにfind_B_index関数の計算でも「dist[u][t] <= Lb なるtの個数」の方針を採用。seed=0で4156点！！
提出。205406点！！20万の壁はまだまだ厚い...
またしても要点を洗い流すことにしてみる。

O(Lb)->O(1)(log Lb)に落とすことを考えた。しかしB_idxの全単射性が保証されてないのでバグる！！！->setにすることで解消(ただしfind_1_indexで採用するのは最大indexの場合に限る)
そうすると、同じ要素が入ることになる -> 複数のindexから最適なindexを見つけることになる.....
もう終盤戦...あとはAのチューニングだけかもしれない。

(相対評価スコア=全体スコア) 10Bまで、あと0.5B。

以上です。

以上、H冒険記でした。どうでしたでしょうか....？

明らかに変な文がありましたが、こんな情緒で参加しておりました。
でも、本当にHは楽しい！！！ただ、本当にわからないときがあるので、H精進する以外の選択肢はなくなりましたね。絶対やる。

Q. day.8~10は？

あきらめました。ごめんなさい。
どんなアイデアも思いつけませんでした。差分計算はどうにもこうにも高度アルゴリズムでも使うんだろうな～(しら～)となりながら何か時間が過ぎていました。

提出履歴

day毎に、一応提出コードを張っておきます。(デバッグだらけですが...)

day1: (問題のsampleコード)
day2: https://atcoder.jp/contests/ahc036/submissions/57018744
day4: https://atcoder.jp/contests/ahc036/submissions/57096073
day4(2つ目の改善): https://atcoder.jp/contests/ahc036/submissions/57175197
day5: https://atcoder.jp/contests/ahc036/submissions/57177890
day6,7(最終提出): https://atcoder.jp/contests/ahc036/submissions/57232510

他の提出もありますが、スコアが悪化したものを提出しているので見てはなりません。見たらUnionFindくんにたたられますよ。

感想

久しぶりにHに参加できました。今までは、勉強とか、趣味とか、精進とか、バイトとかでめっちゃ予定ぎゅっと抱きしめられていましたが、今回はちょうど予定が空いていたので、気分転換に参加していました。
が、やはり精進不足を感じる点がいくつか見受けられました...もっと精進して、次回こそ400位以内、狙ってみたいです。

...欲を言えば100位以内...(超小声

Epilogue

Hは、現実でしっかり応用できるから、好きです。
これからも絶対精進します。

ビームサーチ、ちゃんと使えるようになってきます。もっと強くなって帰ってきます。

またどこかの記事でお会いしましょう。では。

🚪バタン

付録: H中に考えたこと

(原文、大分見ずらいです)

dist[u] <= Lb なるuの個数の最大を達成する区間を採用(区間操作が+100(=1100)回になった) -> dist基準にするなら、ケースによってmin_distも変わってくるはず -> 次の頂点への最短パスも考えないと効率的じゃない
区間操作の際に余計な頂点を光らせてる気がする(多分Aの選び方が悪い)
区間操作を採用する回数が1点操作より圧倒的に少ない(4600回に対して1000回しか採用してない)
信号操作の回数、を基準にすればいいので必ずしも最短パスに行かなくてもok...?(moveが多くなる分には構わない) -> 隣接点の信号が青ならそっちに行って最短パスを再計算した方がいい、か、しない方がいいか決めたい... -> ビームサーチ?^^
やはりAのチューニングが悪い説が -> [最後の方のi%Nに関しては一個も使ってないので無駄になってるのはある] -> (対策: 最短パスに含まれる、と、distとして短い方を先、長い方を後、とすると後ろの方にしわ寄せができてしまうので、短い方と長い方をいい感じにrandomで配置？->それこそAの焼きなましでは...?) -> 確率推定の技術が欲しい:(
とりあえず今は、最後の方のAの領域を有効利用することを考える -> A_idxは複数持つことになるけど...(今は貪欲で我慢)
seed=0に関してはN+50くらいなので微妙だけど、これが3N-6のケースならA_idxは最小5つくらい持ててもいいけど、ってなる -> 待てそれこそビームサーチじゃないか、終わりです
(x)(シミュレーション回数が十分じゃない...)最短パスの移動を固定としたAの山登り法+焼きなまし法-> 近傍は長さ3~6区間反転
(x)貪欲法 -> ビームサーチできないこれ...！？(評価関数 = どの頂点に移動するか、深さ...幅...どうすんだよこれ)
貪欲法で補えない点をちょくちょく変える
現在最高でBFSを呼び出す回数は1800回、つまり最悪で1800(600+1800)=18002400回呼び出してる気がする
現時点ビムサのシミュレーション回数は100が限度そう...

2024-03-31

ABC347 D - Popcount and XOR (ゆるい)解説

3/31 に開かれたABC347-D問題、解説とは違うことを実装していたので一応ここに書いておきます。

ところで、お久しぶりです

皆さんこんにちは、まっちゃラテです。初めましての方は、初めまして！抹茶大好きな競プロerと認知してくれると幸いです✨
で、皆さんご存じの通り(?)、意地でも緑にまで再び上り詰めた人です。そして次のABCで1年ぶりのHighest更新になりそうです。

今回はABC347-D問題で解説とは違ったことをしていたので、需要ないと思われますがここに記しておきます。

では

※解説は全く持って厳密さを求めず、分かりやすさ重視で書いています。厳密さを求める方は、気を付けて読んでくれると(?)幸いです。

問題(要約)

$a,b,C$ が与えられる。次を満たす整数組 $(X,Y)$ を一つ求めよ。

$0\le X,Y\lt 2^{60}$
$\text{popcount}(X)=a$
$\text{popcount}(Y)=b$
$X\oplus Y=C$

$\text{popcount}(x)$ は $x$ を $2$ 進数に変換したとき、桁に含まれる $1$ の個数を表す(ex. $7=111_{(2)}$ であるので $\text{popcount}(7)=3$ )。また $\oplus$ は排他的論理和を表す。

制約

$0\le a,b\le 60$
$0\le C\lt 2^{60}$

解説(ABC公式)

公式解説では、「 $X,Y$ の $k$ 桁目が $(0,0),(0,1),(1,0),(1,1)$ である個数」を管理してがりがり計算して、場合分けで解くといったことをしています。
しかし、正直に言いましょう。私はこの方法は全く思いつきませんでした。思いつかない代わりに、全探索が思い浮かびました。

では、自分なりの解説を記します。

解説(自分流)

まず、A問題全埋めした私は、 $X\oplus Y=C$ を見て、この問題を思い出しました。

atcoder.jp

この問題の解説を見て重要な教訓を得たことがあったのです。

$x\oplus y=z$ は、 $y=z\oplus x$ と同値変形の関係にある

つまり、この性質を用いることで今回の問題に戻ると $Y=C\oplus X$ と読み替えることができ、さらに次の問題に言い換えることができます。

問題(言い換え)

$a,b,C$ が与えられる。次を満たす $1$ つの整数 $X$ を一つ求めよ。

$0\le X\lt 2^{60}$ ※
$\text{popcount}(X)=a$
$\text{popcount}(C\oplus X)=b$

※ XOR によって桁が増加するわけではないので、 $Y=C\oplus X$ は $2^{60}$ を超えることはありません。実際に $Y$ の最大値を計算すると $2^{60}-1$ (すべてのビットが $1$ のとき)となります。

この問題(言い換え)を解くことを考えます。この言い換えにより、答えに依存するものは $C,X$ のみとなります。 $X$ が定まれば $Y$ が自然と定まるためです。
ここで最初 $X=0$ (すべてのビットが $0$ )としておき、この $X$ を貪欲にビットを立てていくことを考えます。

ではどのように立てていくかというと、まず初心に戻ってビット全探索を考えてみます。今回の制約ではそれでは間に合いませんが、次のように動作をしていることが分かります。ただし $X'$ は $X$ を $2$ 進数に変換したものを表します。

① $C'$ の $i$ 桁目が $0$ のとき $X'$ の $i$ 桁目を $1$ に変える (popcountは増加)
② $C'$ の $i$ 桁目が $1$ のとき $X'$ の $i$ 桁目を $0$ に変える (popcountは変化無し)
③それ以外はpopcountに影響しない

このとき③の部分を見ると、このときが無駄な探索であることが分かります。
よく考えてみると、今回の問題においてビットを立てる順序は関与しないため、①②を貪欲に操作できればいいことが分かります。popcountの減少の操作がありませんが、この $2$ つの操作だけで $\text{popcount}(X)$ が $0,1,2,\dots,59$ の値を取り得るので問題はありません。たぶん。

ここまでまとめると、

$X$ においてビットを立てるか、立てないかを選択する
$Y=C\oplus X$ から $X$ が定まれば $Y$ が自然と定まる
$X$ のビットを立てる順序は関係ない

といった性質が見受けられます。これらより、 $C'$ ( $C$ を $2$ 進数に変換したもの)の $i$ 桁目に一致させるか、異ならせるかを全探索すればよいことが分かり、これなら最悪でも $60\times 60=3600$ 回の処理で終えることができます。
具体的に「 $C'$ の $j$ 桁目が $1$ であるときにおいて $X'$ の $j$ 桁目を $1$ にする個数」、「 $C'$ の $j$ 桁目が $0$ であるときにおいて $X'$ の $j$ 桁目を $1$ にする個数」を定めて愚直に探索をしていくことになります。

そうしてできた $X'$ で popcount を数え、また $Y=C\oplus X$ であるためこれを計算して popcount を数え、それぞれ $a,b$ に一致できるならそれを出力し、一致するものがなかったら $-1$ を出力することで、私はACできました。

元ACコード汚すぎて見せられないです。すみません.... 代わりにちょっとリファクタリングしたものを見せます -> Submission #51900029 - AtCoder Beginner Contest 347

※実際には進数変換もあるのでざっくり [tex:60³=2.2\times 10⁵] 回くらいの処理を要します。すこし定数倍もありますが十分高速だと思われます。
※ビット立てる操作を一回もせずに条件を満たすときもあれば、すべてのビットを立たせることでも条件を満たすことがあることに注意してください(私にはデバッグ大臣が誕生しました)

Epilogue

今回は人生で $2$ 回目の緑diff ACでした。めっちゃうれしい！！！！！！
これからも精進絶やさずに頑張ろうと思います。

解説って分かりやすさを求めるとこんな大変なんよね...でも分かりやすさをさらに砕いて説明するのも...

いいよね！！！！！！！✨

(なんか結構な勢いで間違ったことを言っている場合は、Xで私に言っていただけると嬉しいです)

p

Cは解けませんでした :(

2024-01-15

典型？もしくは怪訝？ラテのこれまで作った問題まとめ (2024.1月版)

Prologue

どうも、まっちゃラテです。今年二回目の登場です。
今回は、どっかからの綺麗な白鳥さんなのかスコティッシュフォールドなのかよくわからん人からのリクエスト企画です。

早速ですが、急に寝る直前にX(旧Twitter)でこう言ってきたんですよ。

「あのさぁ、君の問題沢山解きたいから、記事にまとめてくんね？」

まず、言わせていただきましょうか。お気持ち表明。

ありがとうございます。何より、すげぇ横暴※な言い方ですが、すげぇありがたいことです。
こんな現茶元緑コーダーが作った問題を解いてくれることが、本当に何より暖かいです。もしかしたら、おふとんより暖かいかもしれません。

(おふとんに銃を突きつけられる)
いや、やっぱおふとんには勝てませんね。やはり。正義。神。結婚対象。

※本来の言い方より259%誇張しています。本来の言い方はもっと丁寧であり、丁寧です。

本題へ戻りたい

本題へ戻ります。この記事は先述した通り、私が今までに作問し、公開してきた問題をまとめるといった、なんともシンプルな記事です。
言っておきますが、もちろん悪問であったりすることもあります。これは人によって難易度の捉え方、問題の解釈の仕方で違ってくるので、一概に「こいつが作った問題すげぇ最高な問題だらけです」とは言えません。

前置きがすげぇ長くなりました。では、どうぞ。

※これらの問題でこの先不具合が見つかっても、修正しないかもしれません。重大であれば修正します。ご了承ください。

始まりの作問er (Thanks to yukiCoder 様)

No.1805 Approaching Many Typhoon 記念すべき最初の一問。不具合の指摘だらけで作問の厳しさを実感しました。
No.1828 Except 3 この頃は灰梅に夢中でした。その類題として作問したと思います。
No.1849 Three Times Value これも確かどっかのABCのB問題の類題として作ったと思います。Tester解が天才すぎてすごすぎたことを覚えています。
No.1882 Areas of Triangle $この問題で使うアルゴリズム$が結構慣れてきた頃だったと思います。個人的に昔は好きな問題でした。
No.1890 Many Sequences Sum Queries これも$この問題で使うアルゴリズム$が好きになって作った問題だと思います。ケースで罠に引っかかってくれた方がたくさんいてうれしかったです^^
No.1940 Escape through + - 初の数学的知識を問う問題。しかし、考えてみれば簡単です...たぶん。

調子に乗ったラテ (Thanks to MojaCoder 様)

(これは裏話の記事に一言が書いてあるので省略)

GTXC(第一回目の単独コン)

MRSC(第二回目)

MSABC(第三回目)

※裏話書いてないけど、本当に書くことないです。。。すみません。(単に忘れてるだけ)

GTXC-GS(第四回目)

やばいね

改めてまとめましたが、こんなに問題作ったんだ....
全然実感がないです。こりゃあ、緑になってないと努力と能力に矛盾が生じますね...本当に。
申し訳ございませんでした(?)。これからも精進を沢山やっていこうと思います。

継続は、力なり。

Epilogue

ありがとあの白鳥さん！！！！！！！！
おかげで自分の無力さを実感したよ！！！初心って大切だね！！！✨✨✨✨✨✨✨

End.

2023-12-28

今年の冬も、緑茶と一緒に。～4回目の単独コンテスト~

Prologue

こんにちは。久しぶりですね。
今年も私、まっちゃラテは4回目の単独コンテストを開きました。

その名も
Green Tea's Xmas Contest ~Grand Snowing~ : GTXCGS

※サブタイトルに特に意味はありません。

今回は、このGTXCGSのうらばなしをしていこうと思います。
こんなテンションな私ですが、背景ではかなり厳しいことが山積みであったりして...

なぜコンテストを開こうと思った？

ええ...これには別に深い理由はないのですが、もうほぼ、毎年恒例行事となったというか...本当に

「作問スタックもたまってきたし、いっちょコンテスト、開くか☆」

という浅い一心でした。そう、この決心は確か...9月？あたりですかね、そこらへんに決定したのです。

突然ですが、皆さんはレポートというものをご存じでしょうか。なんかの科目の授業に対して、どういう原理で、どういうことを学び、どのように活かすのか、をまとめ、人に発表するといったようなもので。文理問わず、一回くらいは書いたことがあるでしょう。
私の大学では、9月は後期が始まったばかりでした。これは何を示しているのかというと、このころは、まだレポート課題がマジで少なかった時代でした.....

なので、コンテストを開く余裕を持っていました。
あの地獄を、突きつけられる日が来るまでは。

9月: コンテスト問題調整

9月。課題がとりあえず余裕な日々が続きました。
問題をスタックから取り出そうと思い、散策しました。というか、探索してました。...え～.....

案の上、コンテストに向いていない問題たちでした。取り出したのは、たった1問。
そう、つまりほぼすべての問題を1から考え始めたのです。

はっきり言いましょう。マジで、きつかったです。この理由は、後程わかります。

10月: Tester公開に向けて、最終調整

10月。ここから課題がたまってきました。いうてもまだ余裕くらいですが。
さぁ、ここから地獄のテストケース作成、解説作成、問題文調整です。これが地獄の作業かどうかは、作問者の天才の度合いによって変わるので一定に地獄とは言えないですが、マジで地獄でした。

というのも、この時期はもう勉強に力を入れないと授業に追いつけない(そんくらいの難易度)だったので、せっかくのABCも参加できず、まともに精進の時間も取れないといった日々が続きました。

つまり

私の知識と能力は、茶色にとどまったまま、でした。

ええ。これからわかる通り、作問適正難易度が茶色であったにも関わらず、過去の自分が開いたコンテストの問題を見直してみると、

緑、
水色、
青色...

どれも足を踏み入れたことのない領域です。

嘘です。一度はあります。

でも、でも！！！当時の私にはどれも解くのにまだ脳が足りない時期...
この頃から、精進の時間が足りないと自覚しはじめ、課題は先におわらせ、精進の時間を取ろうと思ったのです。

しかし、大学生はそうはいきません。

バイトという奴が、一筋の光に通ずる道に向かう私の行く手を阻んでいたのです。

私が受けるバイトは、週3。1日5時間弱。ええ、こんなに時間が無駄...いや、お金をもらっている身なので決して無駄にはならないのですが、精進の時間をとるためには、本当に邪魔だと思っていました。正直。

こうしてバイトに嫌悪感を感じ、また問題調整の時間が夜中しか取れず、午前はおふとんタイム(こういう時間も無駄に感じるかもしれないが、一種の癒しなので💕)であり、時間の大切さを、知り始めました。

というより、時間が本当に早く過ぎていくんだ...と思い始めたのはこの辺ですかね...><

あ、で、問題調整の話に戻るんですが、課題とバイトのおかげで精進の時間が取れず、まともに解説がかけず、自分を責めるみたいなこともしていました。

なので皆さん、作問するときは絶対適正難易度で作ったほうが、無難です。
この経験から、精進の大切さを改めて知りました。

?

え、なんかテンション低くないかって？記事の文からして？
いや、気のせいです。風邪の病み上がりなので、読者の皆さんがバイアスをかけられているだけで、私は今すごく元気です！！！！！！！！！！Fooooooooooooooooooooooooooooooooo↑↑↑↑

(無理やり)

11月: Testerが天才しかいなかった件

11月。ええ、言わずもがな、レポートがどしどし入ってきました。そして苦手科目の課題もたくさん入ってきました。面白くなってきたねぇ！！！！！！

この月は、やっとTesterさんを集め、テストをしてもらいました。

ええ...

問題の不備が、多い？

終わりです。
そう、問題の不備が多すぎて、これはコンテスト開こうと思った自分は大バカ野郎なんだなとおもいました。

確かに、確かにね！！
ディスコのある競プログループで、こう言われたんですよ。

「1B(1年生後期)でコンテスト開くなんて、結構大変じゃない？」

あの頃の自分は、課題が本当に少なかったので余裕をこいていたんですが、
この時期になると、あの言葉が、しみます。体中に。緑茶を体中にかけて染みわたるような、あの感覚。(?)

いろいろありました。本当に。
なので、ちゃんと精進して能力をつけてからコンテストを開こうと思いました。

それもありますが！！！
まずTesterさんを集めてテストしたんですが、Testerさんが天才すぎて追いつけませんした。理解も能力も。

やばい、書くの面倒になってきた。書きますけど！！！！！！

そう、特にEx問題。これ、水~青を狙って考えたものなんですが、えー解説も実装もきつかったです正直。でもTesterさんが天才すぎて、トポロジカルソートしてDPという。え、何言ってんのこの人たちと思いましたもの！！！

たくさん質問しました。でも、知っているでしょう。

私が負けず嫌いなことを。

なので、あんまり人に頼りすぎない程度で自分で解決したかったので、あえて質問しないといった最悪の選択をしましたが、ええ...

トポ+DPは、そりゃ思いつかないよねぇ...
私は最初、ダイクストラ法の応用を解答例にしていましたが、嘘解法なことがわかってですねぇ...本当につよつよerに見てもらうって大事ですね。。。

そんなこんなで、いろいろメンタルを壊されていました。
大学とバイト、無くなればいいのに！！！って思い始めました。時間が、ほしい。。。

12月前半: メンタル壊れかけのラテ

12月前半。レポートは当たり前のように残り、勉強は当たり前のようにむずい。
これはやばいです。勉強がついにきつくなってきました。

せっかく誕生日(12/5)だってのに、レポートは無慈悲に出されていました。誕生日の夜に気合で終わらせました。

コンテスト調整もやっとラストスパート。...だと思ってた私がバカでした。

解説コードのバグ、
テストケースの不備、
解説の記述不備、
問題文の修正......

あんなに自分だけで調べて！！！！Testerさんは本当に鋭いところを突いてきました。同時に自分の今の能力に喧嘩売ろうとして(?)、メンタルは「壊れかけのラテ」になっていきました--

多分、私のX(Twitter)のFFさんならご存じだと思いますが、壊れてましたね...
ABC出れなくて嫉妬して。バイトの際の態度悪い客の悪口を言って。望みもしていないのにお気持ち表明して。唯一のストレス発散だったと思っています。

そんなこんなで、私のメンタルは崩壊寸前でしたが、気合で泥を泥で洗い返しました。ストレスに、打ち勝ったのです。

そして、12/28。無事、コンテストを開くことができました。
あそこであきらめなくて、本当に良かった....✨✨

問題分野別のうらばなし

ここからは問題別のうらばなしについてご紹介していきます。 ※ネタバレ注意！

A: Swap to Right

どこからともなく、swapという言葉が出てきて、文字列操作の問題を作ろうとしたら、こうなりました。
これは特にうらばなしはないです。

diff予想は、10~60くらい？

B: Footprint 2

前回のGTXC↓ mojacoder.app

この回では、Footprint(足跡、という意味)という、なんとも綺麗なタイトルの問題を出題しました。
このインスピレーションを受け、今回は2作目として作りました。そしたら、LRUDで移動の看板が立っており、雪玉を大きくするといった問題ができました。

正直、良問を作るのがきつかったです。
ただ、問題が綺麗だったので、これで行こうとなりました。

そして、今回も重実装を狙ってみました。やっぱBはこれくらいじゃないとねGTXCは特に！！！！！！^^

diff予想は、100~250くらい

C: Graph Palindome

ええ、言わずもがな、一番の良問だと思いますこの回においては。
これはスタックから取り出した問題です。でも当時はまともに解けなかったのでお蔵入りにしていましたが、なんか解けるようになっていたので採用することにしました。

今回のコンテスト、伝家の宝刀であるUnionFindちゃんを用いる問題がなかったので、せめてCにグラフ要素を入れようと思いました。
そしたら偶然にも、UFを使って実装できたので、got a kotonakiを得ました。

diff予想は、300~500くらい

D: Prevented to Carry Snowman

実は、去年の冬、雪が降ったのですが、その時に思いついて作ったものです。その改題です。
前回の問題は、幅優先探索の評価式の変更を問う感じでしたが、Overflowやら不等式だけど小数誤差があるやらで、なんとなく恐怖を感じたので、さらに簡易化したら、いつのまにか根付き木になっていました。
まぁ、現代に応用できるかと言われればできると思ったので、これを採用しました。

diff予想は、450~600くらい

E: Jingle,Jingle,Presents!!

これも、スタックから取り出したものです。yukicoder様のサイトで出題しようとしたやつですが、いつの間にか忘れ去られた神殿になっていました。
なんと問題はそのままを採用しました。ただ、ストーリーがめちゃくちゃになったのだけは、後悔しております。。。

F: Walnuts in Xmas Lease

3回目に開いた夏のコンテスト、Matcha's Summer Amazing Part-time Contest -MSABC- 🏝🍉 | MojaCoder に出題しようとしましたが、いろいろ不備あってお蔵入りになったやつです。
でも、優先度付きキューを用いれば簡単になることを知ったので、どうにかしてもっと難しくしたいと思った結果、こうなりました。

Testerの方たちは、二分探索などでさらに高速になるといっていましたが、メンタルのおかげで脳が言うこと聞いてくれなかったのでこんな制約にしました。

diff予想は、700~1000くらい

G?: From matcharate12

驚いたでしょう^^
題名に私の名前を入れて、手紙の題名ぽくしてみました。

まぁ、そういう意味もあるんですが、本当は、「タスクをほどよく切って、楽に生きよう」というメッセージを込めた問題にしたのもあります。

え、なんか問題文を言ってる内容が違う？
そうです...その問題は、bitDPを用いる問題になってしまって、私の能力不足で絶対解説書けんと思い、なんか互換の操作の問題になっていました。

実はこの問題もスタックから取り出したものです。本当は辞書順最小からK番目に相当するように、互換の操作をしろみたいな問題を作っていたんですが、この「辞書順からK番目に相当するような順列」を計算するのが調べればすぐに出てくることを知って、冷めたのです。

なのでこうなりました。

diff予想は、800~1100くらい

Ex: Prevented to Carry Snowman REVENGE

D問題をさらにむずくしたやつですね。Ex問題、本当は全く別問題を考えようと思っていたんですが、メンタルといい心の健康状態といい自分の能力の度合いといい、無理でした(直球)。
ストーリーもなぜか最後は意味深な感じになっていますが、別に私は「本当は雪が大嫌いなんですよwww早く夏になればいいのにwww肉まん食いてぇ」という意思も別になくて、雪が大好きなのは本当です。じゃあ真実の顔の口に私の腕を当てはめてみましょう。

腕が、取れなくなれましたね。

じゃなくて！！！

とりあえずここの問題は！！！考えるのが！！！！むずかった！！！！
だからこそ精進は大切であることを知りました。色々な観点から問題を見ることは、大切です。皆さんも気を付けて人生を過ごしましょう。

diff予想は、1100~1500くらい

終わりに

皆さん、本当に今年もありがとうございました。今年は、3回もコンテストを開いたようです。
来年は、コンテストを開くかどうかは、決めていません。なぜなら、精進しないと強くなれないし、というより緑に戻らねばならないという使命感が強いためです。

なので、コンテストを一回も開かないかもしれないし、逆に599回くらい開くかもしれません。
1回も開かないなら、私はやりたいことに夢中になっていると、解釈してください。時間が、ほしいのです！！！！

Epilogue

来年は、さらに充実するような年にしたいな。まずは、目指せ水色！！！
そして、コミュ力も同時に身に着けて...

To be Continue...🏔✨🌅

ぴょこっ

皆さんは風邪にお気を付けください。はっきり言って、この記事を書く気力がありません。
なので文がめっちゃアレになってましたね、、、今度からは万全の状態でテンションMAXで書きます。

では、またどこかで。

Long Time No See

目次

ハッカソン最終日 ～「心」を修正せよ～

プレゼン発表会

懇親会

感想・反省点

おわりに

Epilogue

Long Time No see

目次

day1 ～アイデアを思いつくって、難しいね^^～

アイデアソン

プロトタイプ設計

プロトタイプ設計 －コード・クラス設計ー

day2 ～プログラミング歴6年目の威厳発揮～

ハッカソン －コード設計編ー

ハッカソン －フロントとバックの橋渡し編－

？

追記？

Prologue

オンサイト

コンテスト前

?

コンテスト中 (問題ネタバレあり!)

D

D 自分なりの解説

#

I

#

問題が解けなかった時の感情？

話を戻して...

懇親会

懇親会その後

感想

Epilogue

Question

Answer

前提

Prologue

day.1

day.2

day.3

day.4

長っ！！！！

こんにちは(^^♪

day.5

day.6

day.7

以上です。

Q. day.8~10は？

提出履歴

感想

Epilogue

付録: H中に考えたこと

ところで、お久しぶりです

問題(要約)

制約

解説(ABC公式)

解説(自分流)

問題(言い換え)

Epilogue

p

Prologue

本題へ戻りたい

始まりの作問er (Thanks to yukiCoder 様)

調子に乗ったラテ (Thanks to MojaCoder 様)

GTXC(第一回目の単独コン)

MRSC(第二回目)

MSABC(第三回目)

GTXC-GS(第四回目)

やばいね

Epilogue

Prologue

なぜコンテストを開こうと思った？

9月: コンテスト問題調整

10月: Tester公開に向けて、最終調整

?

11月: Testerが天才しかいなかった件

12月前半: メンタル壊れかけのラテ

問題分野別のうらばなし

ハッカソン最終日　～「心」を修正せよ～

day1　～アイデアを思いつくって、難しいね^^～

プロトタイプ設計　－コード・クラス設計ー

day2　～プログラミング歴6年目の威厳発揮～

ハッカソン　－コード設計編ー

ハッカソン　－フロントとバックの橋渡し編－