2022年12月、アルゴで茶色になった少し後から、だっただろうか。
「AHC、やってみたい…」の気持ちを抱え続け、はや1年。
ついに、その時がきました🎉
対象
1. まだAHCやったことない、やってみたいけれどよくわからない…な人
2. ただ、ぶりの感想文を読んでみたい人
高尚な解法などは一切なく、小学生でも考えられるものです。
問題ネタバレがあるパートは、見出しに【ネタバレ】と記載し、ネタバレ部分はサマリーにしています。
それではいつも通り、感想文！よろしくお願いします🔥
そもそもAHCって何？
という説明🐬？と思ったけど、形式的に一応
※イメージ優先で書くので、細かいところは目を瞑ってもろて…
ABC/ARC/AGCなどのアルゴリズムコンテストと異なり、最適解を出すのが難しい問題に対し、出来るだけ良い解を作成するコンテストとなります。
(AHC003 TOPページより引用)
簡単に言うと 絶対的に正しい解がない 1問を、時間をかけて考えるコンテストです。「ヒューリスティック」「ヒュ」などと呼ばれます。かわいいねえ、ひゅ。
「正しい答えがないなら、何で競うの？」というと、スコアで競います！
例えば、アルゴリズムコンテストの問題はこんな感じ。
2以上100以下の、整数Nが与えられます。1以上の2つの数の足し算で、解がNになるパターン数を出力してください。
例：N = 5
答：4（1 + 4, 2 + 3, 3 + 2, 4 + 1の4パターン）
提出するコードはこんな感じですかね。みんな大好きPythonちゃん！
N = int(input()) ans = 0 for a in range(1, N): for b in range(1, N): if a + b == N: ans += 1 print(ans)
※N - 1を出力してもいいのですが、そこは置いておいて。。
アルゴの提出コードは、このように コード全体が、必ず正しい答えを出す関数 みたいになっています。
N = 5 という入力に対して、4 という出力がだせないコードを提出すると、不正解（WA）が付きますね。かなしいね…
では、ヒューリスティックはどんな問題でしょう？
絶対的な答えがない解…むずかしいですね。世の中にはそんな問題で溢れているのに😢
ということで、身近な バイトのシフト を問題としてみます。
A社には、N人のアルバイトがいます。それぞれを人1〜Nとします。
あなたはこれから、M日分のシフトを組もうとしています。
N行M列のシフト希望表があります。1 <= i <= N, 1 <= j <= Mとします。
i行目には人iの、j日目における「働きたい時間」が記入されています。休みたい日は「0」となっています。
1日のシフトに入れるのは2名、営業時間は10時間で、重複する時間は0とします。与えられる入力はいじわるなので、全員の希望を全て叶えることはできません…
ここで「うれしい度」を定義します。うれしい度は
10 - ( 人iがj日目に希望した働く時間 / 組んだシフトの、人iがj日目に働く時間 ) と定義します（うれしい度は、0〜10となります）。
入ることを希望しているのに、シフト上で0になった場合、うれしい度は0。かつ、希望時間を超えても0になります。うれしくないので！
全員のうれしさが最大になるようなシフトを、N行M列で出力してください。
まあこれDPとかで最適解出せそうですが、これはイメージの話なのでいったん、置いといて…
いろんな方法がありそうだし、どんなコード書けばいいか、多くの日本人はパッと思いつくことがむずかしそうです。
ヒューリスティックは、こんな感じの、考え甲斐のある 最適化 （どのようにすれば最適な答えになるか？）問題が出ます！
そして、上記の問題でいう「うれしい度の合計」が スコア となり、その高さを競います。
極端な話、N行M列に1〜8の数字をランダムに出力してもACとなります。（これ、コンテスト中に気付いて驚愕した）
そして、その結果に応じたスコアが付与され、順位表に躍り出ます！
脳みそをこねこねするのがお好きな方は、きっと楽しいはず✌️
チャレンジ歴
ここで、私のチャレンジ歴もとい挫折歴を晒しておきます！Foo!!!!!
Introduction to Heuristics Contest
問題文を読んではみたが、何も分からず惨敗。未提出😢ヒューリスティック系Discordサーバー「皆解会」
ainemさん主催のこちらのサーバーにて開催されたチーム戦コンテストに参加しました！
「チームを組めば、きっといける！」と信じ、果敢に挑戦。「初心者におすすめの記事は何ですか！」と聞いたところ…テストケース生成、ローカル環境構築、ビジュアライザなど、情報がいっぱい詰まった記事をいただきました！
実は、これが第一の 勘違いつまづきポイント で…情報や、分からない用語が多すぎて。どこから読めばいいか、 そもそもこれを全て理解しなければ、ヒューリスティックに臨めないのでは…？ と不安になっちゃったんですよね。
チーム戦が始まる前に、ローカルでRustの環境構築を行い、うまくいかなく、自信を喪失。
その上、体調を崩したり、仕事が繁忙期だったり（先生業の、4月。どうして気付かなかった？）で、チームメンバーが楽しくヒュってるのを横目にかなしくなり、結局参加できず…（土下座祭り）
その後も、コンテストに参加するぞー！とポチりしてみたものの、問題文が理解できなかったり、理解できてもインタラクティブ（入力と出力が交互に、複数回ある問題）の書き方が分からないまま、時が過ぎたり。
ずっと、 何が分からないのかが分からなくて 、くじけていました。
そうして、どんどん手を出しにくくなっていたヒューリスティックさん。ひゅ…
…でも、みんなの話や、TLで見るAHCの楽しさを眺め 「楽しそう、いつかやってみたい！」 の気持ちを貯めることだけは、続けていました。
今年の2月、正社員になって生活時間が変わり、土曜夜のアルゴコン参加も難しくなりました。
「AHCなら、空いた時間にできるのにー」と思っていた矢先、そんなタイミングを、ついに見つけてしました！
短期コン…！？しかも、出られる！（今日！！）
でもでも、不安だ。ただの初回参加じゃない、1年半くらい挫折し続けてきた人間の初デビュー戦が、短期でもいいのか？と。
しかーし、そこで諦めるぶりではない！
信頼できるつよつよの方々に相談したところ「良いと思います！」とのこと。うれしいことに、アドバイスもたくさんもらいました！らぶ！
- まず提出すること（その後、順位表を見たらやる気が出ちゃう！）
- サンプルコードがあれば、出してみること
- Web版ビジュアライザをいじってみること
- とにかく、貪欲を書くこと
- 正の得点（ACを出して、1点以上のスコアを）取れれば満点！
などなど…！
そして、背中を押された制度としては、AHCはレートが減らない！ ということ。
いやまあ、初回参加なので、0より下はそもそもないんだが！笑
開始前にやったこと
参加ボタンを押すだけ！ 広告みたいだな。
Rated / Unrated選択も、参加アンケートもなく、本当に「ぽち」と押しただけ。シンプルイズベスト
いざ開始！
開始の19:00時点、ローソンでスモールワールドミュージアムの発券と、区役所への手紙を発送していたわたくし！「やばい！！」と焦ったけど、なんとヒューリスティックコンテストさん、提出の速さは得点に関係ないのです✌️
とりあえず、問題文を読んでいると「あれ？理解できるかも」と思った。これがとってもうれしかった！
コンテスト中にやったこと
まず、問題文を理解し、まとめた。
今回の問題はアルゴっぽかったので助かった…！
N, M, Kの値は、どのサンプルでも一定だと読み解くのに、少し時間がかかった。 ここらへんアルゴとちょっと毛色が違いましたね。
でも…問題文を理解しただけでは、どんなコードを書けばいいのか、そもそも何をすればいいのか、見当もつかなかった。
なんせ、AHC自体の仕組みも、よくわかっておらず…
けど、ここでくじけちゃ、相談に乗ってくれた人たちに顔向けできない！うーん！
正の得点とやら、取りたい！！
という思いで、とりあえず、Web版のビジュアライザを開いてみました。
「あ、TLで見るやつだ」と、ちょっとわくわく。
デザイナー魂によりカラーコードが原色だらけで気になったが、一旦思考の隅に置いといたの、大変えらかったですね。いざ自分が使うぞ！となると、色の強さが気になってしまた…職業病😢
まず、再生ボタン、サンプル切り替え、速度調節など、動作がわかるところから触ってみました。これがかなり良い作戦だった！
その後、アウトプットを手動でいじり、30分少々ビジュアライザと問題を堪能。
いじりながら「なるほど。このアウトプットを出力するようなコードを書けば良いのね」と理解。
ありがとうビジュアライザ！ありがとうアドバイス！！
考えたこと【ネタバレ】
ビジュアライザをいじりながらと、小さな数に置き換えて考えたことなどを、goodnotesにまとめてみました。
まとめたやつ(click!)
一応、この段階で、鉄則本のヒュ項目を読んだけど「こういう手法があるんだな」を目視するにとどめた。
今回の目的は、高い得点を得ることではなく、あくまで 「問題文を理解し、可能であれば提出すること」 だったからなので…！
問題については、最悪何もせんとも0出力するだけで得点になる系と理解し「現状よりも、1点で良いからスコアをあげよう」を軸に、できること・わかることから組み立てて、コードを書いていきました。 これを、81回繰り返す。小学生レベルの方針(click!)
...という方針を、コードに落とすのに2時間近くかかった😭
しかも書き換え後の配列保持がちゃんとできず…競プロ力の著しい低下
初提出
提出にあたり、まず、ビジュアライザのinputと、paiza.ioの入力に同じサンプルを置く。
そして、paiza.ioで出力したアウトプットを、ビジュアライザのoutputに貼り、その結果同士を見比べて、遊ぶ。というのをしました（ややこしい）
とりあえず計算量は大丈夫な自信があったので、TLEは回避できるかな…？と、提出！！
150のテストケースを迎えうち、無事…AC！わーい！！
ヒュでの初ACは、アルゴよりもずっと濃厚で、味わい深いものでした。ねっとりじっとり。
と、同時に、安心と達成感でおなかがすいてしまい…そう、晩御飯を食べていなかったのです。
そして、晩御飯を食べつつ、改善案を練っていたら、眠気も練っていた。ねむねむねむねだ。
眠気の先には…（気絶）
終了
気づいたら終わっており、TLを見ると、上位勢の美しいビジュアライザがシェアされていました、すごい。ルービックキューブみたいで感動しました。
鉄則本に書いてあった、例のやつを使っているらしい。すごい。とりあえず何が起こっているか分からないが、すごいということ、同じ問題を解いたからこそわかった のがうれしかったです！
そんなこんなをしている間にレーティング更新があり、ヒュのレートが64に！
やったね！色がついたよ！
感想 / 反省
初参加が短期で良かった！ です✌️
考え方にもよるので万人におすすめ！というわけにはいかないが、以下の利点がありました。
- 手軽にできる。
- 問題文を解読しやすい
- 終わるのが早いので、他の人の方針を知れる期間も短い。他の人との会話の内容を気にする時間も短い！
今回、時間もアルゴに近かったため「レートが下がらないアルゴ」という認識に近い感覚で、出ることができました！
（この時間の開催が初だったのは、知らなかった）
反省
- どうして関数化しなかったの…？
- 構築がかなり甘かった。普通の貪欲すら書けてない
- これからどう勉強すれば良い？がちょっと重く感じる。まず復習から始め、やりたかった貪欲を書けるようになる→鉄則本やる→AHCイントロダクションやる。かな？
などを考えています…！
やり方がわかったので、やっぱり次は、長期にチャレンジしてみたいです！ゆっくりじっくり考えるの、とっても良かったです！
ここまで読んでいただき、また、アドバイスくださった人々、めっちゃありがとうございました！
ヒュもまずは茶目指して頑張るぞー！
