初めてCTFコンテストに出ました(SECCON Beginners CTF 2023 参加記)

こんにちは。

今回初めてCTFのコンテストに出たのでその感想とかを書きます。

いつか強くなって振り返ったときに初心に帰る用です。強くなれるとは言っていません。

注意：SECCON Beginners CTF 2023 のネタバレを含みます。(一部問題の解法含む)

謝罪：この記事はwriteupを書くために書かれたものではありません。writeupを見る目的の方は他の記事をあたってもらえると良いかと思われます。

どなたかチームで出ませんかツイートをしたものの誰も集まらず一人で出る予定だったのですが直前でフォロワーの方が声をかけてくださって２人チームとして出ることになりました。ありがとうございました。心強すぎる。

＜開始前＞

キタキタキタキタ pic.twitter.com/M0ufJVdtF0

— おぉ味噌汁。 (@OxOmisosiru) 2023年5月25日

SECCON，椅子温め係とお茶汲み係を担当するので忙しい
ちなみに問題解く係はいません(?)

— おぉ味噌汁。 (@OxOmisosiru) 2023年6月3日

𝑺𝑬𝑪𝑪𝑶𝑵 𝑩𝒆𝒈𝒊𝒏𝒏𝒆𝒓𝒔 𝑪𝑻𝑭 𝟐𝟎𝟐𝟑 って𝑹𝑬𝑨𝑳𝑳𝒀❔前回𝙎𝙀𝘾𝘾𝙊𝙉 𝘽𝙚𝙜𝙞𝙣𝙣𝙚𝙧𝙨 𝘾𝙏𝙁 𝟐𝟎𝟐𝟐 受けたことないけど𝐖𝐀𝐍𝐆 𝐂𝐇𝐀𝐍𝐆あるっしょ。俺は𝑪𝒓𝒚𝒑𝒕𝒐,𝒲ℯ𝒷,𝚁𝚎𝚟𝚎𝚛𝚜𝚒𝚗𝚐,Forensics,𝔑𝔢𝔱𝔴𝔬𝔯𝔨,ℙ𝕨𝕟が極端に苦手なだけでⒺⒶⓇⓉⒽ ⓅⓄⓌⒺ

— おぉ味噌汁。 (@OxOmisosiru) 2023年6月3日

適当にツイートして開始を待ちます。

１週間前に詳解本を買っていましたが，全然読み進められていないので実質ノー勉です。cpawCTFとかでちょっと解いてはいましたが体系的に学んだことはほとんどなくといった感じで初陣でした。

＜開始＞

Welcome を通しました。(日本時間14:01)

全問 Welcome だったりしないかなと思ったが全然そんなことはなかったです。

相方が Crypto 得意ですので完全に任せて私は他の問題を見ることに。とりあえず解いたのは Half(reversing,Beginner) でした。

まず思ったこととしては，

・.tar.gz ←何？

・配布ファイルの横の文字列 ←何？

でした。実戦練習が無さ過ぎて拡張子にビビる人と申します。

ググると.gzが解凍できるらしいです。

.tarってなんだよ…と思いつつ適当にコマンドを打つか～と思ってstrings打ったらフラグでましたありがとう。初手でめちゃめちゃ困りました。 (14:38)

前提に立ててないみたいな問題が多くて最初はモヤモヤしてました。（バイナリファイル，動かしてみると…？実行しながら解析できるツールを～　←まず動かせないのですが　みたいな）

私が Half を通している間に相方の方は CoughingFox2 と Conquer を通していました。私は一体…？

次に目を通したのは Forbidden(web,Beginner) でした。

謎文字列は無視してとりあえず.tar.gzをダウンロードして，.gzを解凍。strings をかけるとなんかたくさん文字が出てきたので適当なテキストエディタ(サクラエディタ)で開いて中身を確認しました。ぱっと見た感じflagという文字列があればダメみたいなので/FLAGにして飛びました。F12押しても見えなかったページだしそんなことあるんか？と思いましたが冷静に考えたらそんなことありますね。F12で見えなくてもいいじゃんねということでフラグを獲得しました。(15:04)

私が Forbidden を通している間に相方の方は switchable_cat を FA していました。え？畏敬。

次に poem(pwnable,Beginner) , YARO(misc,Beginner), aiwaf(web,Easy) に目を通しました。

分からん！！！！！！！！！！！

分からないですね，はい。

ちなみに.tarも解凍できると知ったのはこの時(開始から2時間が経った頃)でした。解凍できると知ってひっくりかえりました。

poemも中身見てみて，-1とか入れましたが配列外参照でセグフォが起きてそれはそう…で詰んでいました。

YARO，中身見てPythonでインポートとかしようとしたが如何せん私のpython環境のPATHの設定がミスってるため中々上手くいかず頓挫しました。諦めんなよ。

aiwaf，普段pythonをなんとなくで読んでいるツケが回ってきました。普通になんもわからない。検知される方法しか分からなかったです👻。

唸っているうちに相方の方が cooking(crypto,Hard) を通していました。Crypto_GODに改名してみてはいかがですか。その時点でのチーム順位は10位でした。ええ…。

仰天しているうちに相方の方が poem,YARO,aiwaf (17:45)を通してくれました。チーム名の75%が私成分なの申し訳なくなってきました。99%あげます。

poemは配列外参照を利用(?)して -4 を入れればフラグ出るらしいです。アドレスの値的に配列外参照をすることでflagを参照できるようになるとのこと。「配列外参照はダメ」くらいの知識しかなく普通に目から鱗でした。もっとプログラミング勉強せねば…。

YARO は相方の方の解法をざっと聞いたのですがどうして分かるのかが分かりませんでした！いかがでしたか。writeup読むなりして勉強します。

aiwaf のコード内の[:50]って先頭50文字みたいな意味らしく，そこが分かればワンチャンあったなあとは思いました。知らんこといっぱいのコードでもしっかり読むことの大切さを実感しました。CTF，ありがとうございます。

ほえーすごいと言いながら Poker(reversing,Medium) を考えていました。

まあ結局フラグは入手できなかったのですが。

あいこと負けで持ち点０点になるという闇のゲームです。

strings だけではさすがに太刀打ちできなくなったのでググってみたところ，IDAとかGhidraというものがあるらしいので，頑張ってインストールして使ってみました。

逆コンパイルありがたすぎる。なんとか関係ありそうな部分は読めた感じがしました。

「ランダムで勝敗決めてそうで，勝ったら1点加算，負けかあいこで０点になる」

というルールそうなので，1点加算の部分をクソデカ点加算にすれば運でもなんとかなりそうです。慣れない手つきでその1の部分を探し出しやっとの思いでhexeditorで編集をし01→0Fとか(99にすると負になった　それはそう)にして，保存。うおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおいけえええええええええええええええええええええええええええええええええええええええええええええええええええええええええええええ$sudo ./Poker/pokerrrrいけいけいけいけいけいけいけいけいけいけ$sudo: ./Poker/pokerrrr: command not found！エ？？？！？！？？！？！？！？！？！？！！！？？？？！？！？！？！？！？？！？！？！？！？！！？？！？？？！？！？？！？！？！？！？！？！！！？！？？？！？！？？！？！？！？！？！？！！！？！？？？！？！？？！？！？！？！？！？！！！？！？？？！？！？？！？！？！？！？！？！！！？！？？？！？！？？！？！？！？！？！？！！！？！？？？！？！？？！？！？！？！？！？！！！？！？？？！？！？？！？！？！？！？！？！！！？！？？？！？！？？！？！？！？！？！？！！！？！？？？！？！？？！？！？！？！？！？！！！？

…。

………。

終わった…。 (スラムダンクの画像)

終わりました。編集前の実行ファイルはちゃんと実行できました。どうして？？？？？？？？？？？？？？（これ本当に謎なのでどなたかこれを読んでいる方で分かる方がいれば教えていただけると大変助かります。）

Poker はここで詰みました。根本的に間違ってなければ惜しいところまでは行ってそう(ほんとか？)なので悔しいです。後でwriteup読みます。

悪あがきで Three(reversing,Easy) にも取り組みました。

Ghidraで逆コンパイルしたものを読むと，どうやら flag_01 , flag_02 , flag_03 を順番に1文字ずつ取ったものを最終的なフラグ文字列としているようです。最初の3文字を試しに16進数から戻してみてctfが出たときのアドレナリンのドバドバ感はヤバかったです。生きてて良かった…………………………………………………………………………。

うまいやり方をやる前に手を動かした方が早いということで45文字手打ちしました。解けました。やったあ。気持ち良すぎる。(22:45)

Leak(web,Medium) にも取り組みました。これ知ってる！Wireshark使うやつでしょ！と思って意気揚々と開いたものの，対話で出てきた１つの謎文字列だけ得られて終了…。何だったんだ。

ここでコンテスト終了でした。

結果としては，

私：Welcome(50pts) , Half(50pts) , Forbidden(56pts) , Three(65pts) TOTAL:221pts

相方の方：CoughingFox2(58pts) , Conquer(84pts) , switchable_cat(179pts) , cooking(221pts) , poem(65pts) , YARO(74pts) , aiwaf(68pts) TOTAL: 681pts←強すぎる

を正解し，最終順位は 79 位でした。相方の方が強すぎる。イキってないですがイキってすみませんでした…。

CTF初心者of初心者ですが，見えないものを手探りでも見えるようにしていく，そんな面白さがあるように感じます。こういうのすき。

writeupなど読みつつ知識を増やしていきたい所存です。初めてCTFのコンテストに参加しましたが，とても楽しかったです。次回も是非参加したいです。Medium問題解けるようになりたいですね。

以上です。

ここまで読んでくださりありがとうございました。

『2147』ヒント・解説

このページは おぉ味噌汁。（@OxOmisosiru）が Twitter で公開した一枚謎，『2147』のヒント・解説ページとなっております。

まだ解いていない人，ノーヒントでまだまだ粘りたい人は，見ない方がよいです。

一枚謎『2147』

正解を見つけ出せ。

協力OKです。協力しなくても解けます。正解者が出ない場合，近いうちにヒント出すかもしれません。

正誤判定はこちらから→https://t.co/SCb7LivleV pic.twitter.com/6NJUNqeIxj

— おぉ味噌汁。 (@OxOmisosiru) 2022年11月16日

※ヒントは下にスクロールすることで見れます。

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

【 ヒント 】

下のヒントに進むほど，具体的なヒントになります。

ヒント１

検索必須です。つまり，この謎を見て考えて唸るだけでは解けません。

 

ヒント２

何を検索すればいいのでしょうか？

2147について検索するのではありません。

 

ヒント３

背景の色が手がかりです。（リプライに貼ったヒントからも，背景の色が関係していると勘づく人もいそうです）

 

ヒント４

色で検索すると言えば何を検索しますか？

 

ヒント５

カラーコードを検索します。

 

ヒント６

2147の背景色のカラーコードは #FEDCBA です。（ヒントのACEの方は，#ABCDEFです。）

昇順と降順でカラーコードがなっており，意図的な感じがします。

実際，カラーコードに注目するのは正しいです。

2147の解釈として，「2文字目，1文字目，4文字目，7文字目を抜き取ってつなげて読む」というのはありますが，カラーコードでそれを用いることは厳しそうです。（F#DA？）

 

ヒント７

ヒント６で，カラーコードで2,1,4,7,番目を読むのは厳しいと言いました。

7文字目くらいまでうまく対応できる，その色に対応した何かは，他にないでしょうか？

 

ヒント８

ヒント７での「何か」とは，９文字ある，アレです。

 

ヒント９

RGB値を調べてみましょう。

 

ヒント１０（ラスト）

RGB値は9桁あり，2,1,4,7文字目を拾うことはできそうです。

2147の方は #FEDCBA , RGB: 254 220 186

386の方は #ABCDEF , RGB: 171 205 239 で，ACE が導けるそうです。

です。

どうやったらACEが導けるかを考えてみましょう。

 

【正解】

背景色のカラーコードとRGB値を調べると，#FEDCBA , RGB: 254 220 186 です。

RGB値の2,1,4,7文字目を拾うと，5221 となります。

カラーコードの5,2,2,1番目を拾うと，「BEEF」となり，これが答えとなります。

 

【 あとがき 】

導線が極端に少ない謎（もはや謎と言っていいかも分からない）でした。

この記事が出る前にクリアできた人はすごいと思います。（メタ解きでもクリアはクリアです。）

この謎は導線が極端に少なく，内容自体も制作者が「カラーコードとRGB両方使ったら面白かったりしない？（自分が）」と思って作ったものなので，根拠があって「こういう解法になります」のようなことにはなっていません。本当にごめんなさい。ただの私のエゴです。ごめんなさい。許してくれ…　許してくれ…

ちなみに答えはBEEFですが，例としてDEADの例を載せようかなとか思ったりしていました。（カラーコード全探索して良い感じの組み合わせが見つからなかったので諦めましたが）

以上です。ここまで見てくださりありがとうございざいました。

何か質問とか指摘とかありましたら，以下のアカウントにDMを送るなどしてください。よろしくお願いします。

制作：@OxOmisosiru

くVC017 解説

くVC017 に参加していただいた皆さん，ありがとうございました。

初めて Writer をさせていただきました。楽しんでもらえたなら幸いです。

1位：hamukichi_nbr さん (ABCDEFG 3200 points , 13:00)

2位：udhiii さん (ABCDEFG 3200 points, 27:46)

3位：tomerun さん (ABCDEFG 3200 points, 31:46)

おめでとうございます！

FA者の皆さんです。

A：emthrm さん (0:06)

B：udhiii さん (0:22)

C：googol_S0 さん (0:52)

D：hamukichi_nbr さん (0:50)

E：nikuroll さん (4:27)

F：hamukichi_nbr さん (1:39)

G：hamukichi_nbr さん (1:59)

H：-

おめでとうございます！A~G埋まるの速すぎてすごくすごかったです。

以下，解答となります。

A (100 points)

問題：到着したSNSってなーんだ？

解答：ついたー / ついったー

SNSとして Twitter が挙げられます。「ついったー」と「着いた」の音が似ていることから，答えは「ついたー」もしくは「ついったー」となります。

コンテスト中AC者は 34 人でした。

B (300 points)

問題：めちゃめちゃ落ち着いている制度ってなーんだ？

解答：どれいせい

落ち着いている→冷静 の言い換えが重要です。

めちゃめちゃという修飾語はド～で表せます。

よって答えは，ド冷静 どれいせい(奴隷制) となります。

コンテスト中AC者は 9 人でした。

C (400 points)

問題：恥ずかしがる巣ってなーんだ？

解答：はにかむ

そのままです。恥ずかしがる→はにかむ は少しハードルが高いので，巣→ハチの巣→ハニカム = はにかむ と進めるかがポイントです。

コンテスト中AC者は 15 人でした。

D (500 points)

問題：生みの母ではない動物ってなーんだ？

解答：ふじつぼ

不 + 実母 です。

生みの母→実母 の言い換えがポイントです。

「ではない」は否定語の不で表せます。

コンテスト中AC者は 12 人でした。

E (500 points)

問題：花が相手に合わせて動く四字熟語ってなーんだ？

解答：ふらわいどう

提案時点では問題文に四字熟語はありませんでした。

「相手に合わせて動く四字熟語」→「付和雷同(ふわらいどう)」であることを軸に考えると答えが思いつきやすいです。

ふわらいどう に花要素を入れるために，2文字目と3文字目を入れ替えて，ふらわいどう とすることで，花・移動・付和雷同の全ての要素を表すことができ，これが答えだと分かります。

または，初めから 花→ふらわー を軸にして，四字熟語に付和雷同として音が似ているものが存在することを考えるのも良いでしょう。

コンテスト中AC者は 10 人でした。

F (600 points)

問題：道理を持っているか聞く性質ってなーんだ？

解答：あるかりせい

性質の要素を答えに入れると考えると，答えは「～性」となります。

道理を「～せい」で言い換えられないか考えると，「理性」が思いつきます。

持っているか聞くので，「あるか？」と「理性」を組み合わせて，答えは あるかりせい(アルカリ性) となります。

コンテスト中AC者は 9 人でした。

G (800 points)

問題：目標を吐き出すことをやめようとする問題ってなーんだ？

解答：ごーるどばっはよそう

2分弱でACが出る問題ではないと思っていました。

目標を「ゴール」と，吐き出すを「ドバッ」と，やめようを「止そう(よそう)」と言い換える必要があります。どれか1つでも適切に言い換えられれば答えはかなり思いつきやすくなると思いますが，厳しいです。

問題を，数学の問題ととらえることで，有名な数学な問題を全探索することで解くこともできるでしょう。

コンテスト中AC者は 5 人でした。

H (800 points)

問題：静かにさせて言うことを示す制度ってなーんだ？

解答：しっこうゆうよ

今回のボス問枠です。

静かにさせる→シッ と，言うことを示す→こう言う(よ) と，2つの言い換えが必要です。両方とも口語的な表現であり，辞書には出てこないため，かなりのひらめき力が必要になるでしょう。

さらに，執行猶予が制度として認識されにくいものであるため，答えから問題の照らし合わせをする手法も取りづらいため，かなり難しいです。

コンテスト中にACした人はいませんでした。

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

ボツ1 (400 points予定)

問題：たくさんの七面鳥ってなーんだ？

解答：ますたーきー

既出でした。（完）

ボツ2 (1000 points予定)

問題：夫婦の死に際の苦痛ってなーんだ？

解答：だんなつま

ボツ理由：既出でした。（完）

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

以上です。

改めて，ご参加くださった皆様，ありがとうございました！

入水しました！

おぉ味噌汁。と申します。

私は、2021-08-08 AtCoder Beginner Contest 213 にて、レーティングが $1235$ 、Highestを更新し、入水しました！\ﾋｭｰﾋｭｰ!/ \ﾄﾞﾝﾄﾞﾝﾊﾟﾌﾊﾟﾌ/ \ﾌﾞﾍｶﾞｼﾞｭﾌﾞﾍｶﾞｼﾞｭ(これは何)/

kakitamasziruさんのAtCoder Beginner Contest 213での成績：750位
パフォーマンス：1649相当
レーティング：1178→1235 (+57) :)
Highestを更新しました！#AtCoder #ABC213 https://t.co/ZEG1Rj8KYj

初入水から 40 回のコンテストを経て、ついに再入水です…！！！！！嬉しい！！！！！

— おぉ味噌汁。 (@OxOmisoCyan) 2021年8月8日

レーティンググラフの遷移はこちら↓

いや緑落ち期間長いな？？？？？？？？？？（正解）

再入水までコンテスト $40$ 回！笑っちゃうわなにわろてんねん

AC Count と Rated Point Sum です。

入水から少し経ってる時期に撮っているので実際はもう少し少ないですが、これくらい精進しました。$1500$ AC まであとちょっと！

ちなみに私は、30分くらい悩んだらすぐ解説見ちゃうタイプです。解けないまま放置はなんとなく嫌ですし、後で考えようとその時は思っても結局忘れてしまうためです。

名前と概要だけ知っているが、理解していなかったり、実装したことないアルゴリズムも多くある（畳み込み、数学的なアレコレ、ネットワークフローなど）ので、いずれ学ぼうと思っています。アルゴリズムを学ぶこと自体が楽しいですしね。

報告的なことはこれくらいにして、ここからはラフに。

入水記事だから少しの自己顕示は許されるだろうということで書いちゃおうコーナー！イエーイ！

Twitter で書くことの募集をかけました。

• 持っている/使っている ライブラリ 

現時点で使っているもの(過去問を含む)は赤

用意したものの使っていないものは緑

です。

二分探索

拡張gcd

Fenwick Tree

幾何（3点が同一直線上か , 直線の交点座標(バグってる) , 直線の中点 , 三角形の内心 , 1点の原点中心回転90° , 三角形の外心）

進数変換(10進数まで)

二項係数(Lucasの定理)

二項係数(逆元使うやつ $nCk$ の $n,k≦10^5$ くらいまでが解ける)

二項係数(フェルマーの小定理)

ポテンシャル付き Union-Find

Union-Find

赤で書いたライブラリも 8 つのうち 4 つは過去問のみでそれも 1 回ほどしか使ったことがありません。

これら以外は全てその場で書いています。Dijkstra 法や Warshall-Floyd 法といった典型(個人的)アルゴリズムはもう書き慣れたので、ライブラリにする必要性を感じていません。今のところは。

• 好きなミネラルウォーター

これは何？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

よくわからないので適当に書きます

第 1 位 ： 「奥大山の天然水のやつ」感想：これぞ水って感じで見せつけてくれました。

第 2 位 ： 「そもそも水を外で買って飲まなくないですか？」感想：正解

• 好きな問題トップ$998244353$

これは何？？？？？？？？？？？？？？？？？？？？？？？？？？？？？2

おぉ味噌汁。くん「$mod 5$ とします。」

第 $3$ 位 AGC037-E Reversing and Concatenating

「お？高難易度イキリか？」と思ったそこのあなた、正解です。

この問題は元々赤diffで、赤にしては簡単ということで挑戦してみることにしました。

（若干のネタバレ注意）

紙に書いて丁寧丁寧丁寧に考察すると、実は実質考えなければいけない $K$ の値はとても小さいことに気づきます。

 それに気付いて 30 分で実装をします。

ぼく「まさかこんなの通るワケないんだよナ～～・。・」

ジャッジ「AC」

ぼく「？」

となり、初の赤diff AC（当時は橙diffも一問も通していませんでした。）となったのでした。

その頃の感動は今でも覚えています。本当に嬉しかったので、3位となりました。

第 $2$ 位 ABC171-F Strivore

もしかしたら意外かもしれません。

この問題はですね、3回驚きました。

まず1回目の驚きは、サンプル2を見てです。

37564
whydidyoudesertme

いやー。いいですね。「どうして私を見捨てたの？」「皆殺し」

ゾクゾクしますね。

2回目の驚きは、どうしても自力で解けずに解説を見てです。

短い！！！

めちゃめちゃ状態数が多くなりそうな問題なのに、こんなに簡素に解説ができるほどの問題なのか…。と驚きました。

3回目の驚きは、解説を理解したときです。

「うっわこれすご…………！」

とリアルで言いました。鳥肌も立ちました。

あんな問題が、めちゃめちゃシンプルな式一つに落とし込むことができるのです…！！

数学は苦手ですが、これには非常に感動しました。なので 2 位とさせてもらいました。

本当にありがとうございました。

ところで、Strivore という問題文、問題中の文字列 $S$ を前から見て、最終的にそれが全て後の文字列に含まれる = 丸呑みされている ことが考察で条件として出てくるので、String + vore で 文字列丸呑みフェティシズム ということなんだろうなと思いました。丸呑みっていいですよね。作問者さんもどなたか分かったような気がしました。（ごめんなさい）

 第 $1$ 位 ABC135-E Golf

さあ栄えある第 1 位は、多くの人が聞いたことがあるであろう ABC-E のやべーやつ です。

ABC-E で橙diffって、何？？？？（本当に何）

こういう明らかにやべー問題って、解きたくなりますよね。

というわけで、頑張ってみました。

3日くらい考察を頑張った結果、怒涛の場合分けをすることで、何とか、何とか、実装も苦心しましたが、何とか 一発 AC することができました…！

AC が表示されたときはパソコンの前でガッツポーズをしました。喜びました。本当に嬉しかったです。Twitter で作問者の方が おめでとう してくれました。嬉しかったです。（小学生並みの感想か？）

 私の解法方針及びACコードを以下の記事にまとめているので是非どうぞ。場合分けがえぐいですが。

oxomisosiru.hatenablog.com

私の競プロ精進において、一問を数日単位で考察する ということはそれまでなかったのですが、（今もない）思い返してみると、どの場合分けや考察においても、無理があるものはありませんでした。一つ一つ着実に正しい考察を積み重ねられていけたので、モチベを保ったまま続けることができました。作問者の方、本当にありがとうございました。

• 今まで解いた問題の全問解説

 └(՞ةڼ◔)」< ﾙﾝｿﾞﾇｽﾍﾞﾐﾛﾝﾇﾛｨﾎﾞﾓｼﾞﾍﾞｯｿﾞｮﾓｼﾞｮﾐwwwwwwwwwｲﾋｰwwwｲﾋﾋﾋﾋﾋﾋwwwwwwww (訳: 人間限界がある)

• これからについて

 私の今のレーティンググラフはこんな感じです。急成長きてるな？

クソ長緑期間が嘘のようです。直近2連続青パフォでめちゃめちゃ温まっています。グラフくんがうなぎ上りです。うれしい！ちなみに中の人は変わっていません。同じ脳みそで闘っています。

私は今高2なので、JOI本選 に出場したいなーと思っています。JOI精進は難易度7をほとんど埋めて、難易度8に現在取り組んでいるところです。しかし中々手強い。頑張ります。今年こそは予選通過するぞ！！！！！！！！！！！

学業に関しても受験が待ち構えているので、頑張らないといけないなという気持ちです。そのせいか競プロの精進時間も減ってきています。言い訳です。

そんな感じでぼちぼち頑張っていこうと思っていますので、これからもよろしくお願いします～。

以上です。

以前、入水記事に何を書くかをフォロワーさんに募集したところ、「性癖」との提案がありましたが、さすがに私の性癖を公開するのはまずいので、やめました。ご了承を。

ちなみにそのようなヤバツイートは私の鍵雑垢 @urisosimoXo の方でやっておりますので、深淵(?)を覗いてみたい方はフォロリクどうぞです。通すかは人によりますが。

ABC211 参加記

ABC211 お疲れさまでした。

思考の流れなど適当に書いていこうと思います。続くかは未定です。

A 問題

double で $A,B,C$ を受け取って計算します。

fixed と setprecision(桁数) を使って小数点の出力を行います。

収縮期血圧と拡張期血圧の最大値 $300$ は、やばいだろ… （生命の維持的に）

提出 https://atcoder.jp/contests/abc211/submissions/24478783

ここまで 0:54 

B 問題

野球のサイクルヒットのことですね。

簡単な実装は、それぞれの文字列が一度だけ現れることを確かめる、つまり、二度現れる文字列があれば "No" 、なければ "Yes" という実装ですね。

コンテスト中はその解法に気付かずダル実装をしてしまいました… (3分かけた)

提出 https://atcoder.jp/contests/abc211/submissions/24485703

ここまで 4:05

C 問題

C問題でこれが出るのか…（困惑）

典型ぽい感じがします。$dp[Sの文字数][8]$ で 、今何文字目を見ていてc,h,o,k,u,d,a,iの内何文字目まで作ったかで DP をします。（累積和を取る？感じです）

これとほぼ同じ問題が 典型90 に出ていたようですね。（私も解いていたようですが、コンテスト中に思い出すことはなかったです。）

 提出 https://atcoder.jp/contests/abc211/submissions/24490976

 ここまで 8:23 良い調子

D 問題

 グラフ問題です。

私これ知ってる！トポソして DAG(Directed Acyclic Graph) 作って累積和ぽいDPして解けるやつでしょ！と思ってやります。無向グラフですが、$1→N$ で最短距離を計算して距離の差が $1$ の頂点同士は辺で結んでアヘることができて、これは DAG になります。よって、この DAG の上でトポソしながらDPをすればよいので、$O(N+M)$ で解けました。

実装で若干ミスったりして WA を出しましたが、無事 AC。

解説を見たところ、どうやらトポソいらないようですね。（13へぇ）

提出 https://atcoder.jp/contests/abc211/submissions/24501476

 ここまで 30:18(+5min)

E 問題

 ここからが本番です。解きたい！

サンプル3を見て最大ケースの答えの数が少ないことから、答え全探索ができそうだなと思います。

ここで、順列全探索ぽいことをして、始点を全探索して $K-1$ 回の上下左右の移動を全探索しようと考え、実装します。

サンプル1が合いません。このやり方だと、十字のような塗り方ができないのです…（気づけ矢）

完全に勝った気分でいたのでちょっと焦ります。

まだ30分あります。ググります。Redelmeierのアルゴリズム というのが見つかります。調べます。再帰ぽい！

実装します。バグらせます。ああああああああああああああああああああああああああああああああああああああああああああああああああああああああ直った！！！！！！！！！！！！！！！！！！！！いやサンプル合わねえ！！！！！！！！！！！！！！！！！！！！！！ああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああせめて実行時間だけでも（サンプル3を試してみる）………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………（10秒くらい経つ）

俺の解法では、実行が、終わらねェ！！！！！！！！！！（ドドン！）

悲しいね。

最終的には 1338位で、パフォは 1329 、温まりました。嬉しいね。

ABC135-E †Golf†を通した話

こんにちは。おぉ味噌汁。です。

2021 年 3 月 27 日、ABC-E最難関として名高い Golf を AC しました。

私のツイート↓（一部）

数日かけて数時間考察してようやく解けて、とても嬉しかったので、こうしてブログにしています。

問題概要はこんな感じです。

• 二次元格子上でゴルフをする。
• ボールは最初 $(0,0)$ にあり、一打毎に、マンハッタン距離が ぴったり $K$ の点にボールを動かせる。
•  ボールを $(X,Y)$ に動かすまでにかかる打数の最小値と、それを満たす適当な 過程 を求めなさい。（不可能な場合はそれを報告しなさい。）

はい。色々とツッコミどころはありますが、（ぴったり $K$ でゴルフやっていけると思いますか？僕は思いません。）とりあえず考えていきましょう。

• $[1]$ $(0,0) → (X,Y)$ が不可能な場合

これは、まだ簡単です。

例えば、$X = 1 , Y = 2 , K = 2$ の時、不可能です。

なぜなら、動かす距離は毎回 $K$ で、 その $K$ が偶数ならば、各打毎に動かした距離の和及び $(0,0)$ からの距離は偶数にしかなりえず、$(1,2)$ という $(0,0)$ からのマンハッタン距離が奇数の点には動かすことができないからです。

まとめると、$Kが偶数 かつ (|X|+|Y|)が奇数$ の時、不可能です。実装↓（コードをそのままコピペすると改行がおかしくなるので画像です。）

実は、それ以外の時は可能です。

これ以降、一打ごとにボールの座標を $(nx,ny)$ とし、

$$ dx = abs(X-nx) , dy = abs(Y-ny) $$ 

$$ dist = abs(X-nx)+abs(Y-ny)$$ とします。

また、便宜上、$X ≥ 0 , Y ≥ 0$ に変換しておきます。（例えば、$X$ が負なら、$-1$ を掛けるとできます。そうしたところで、途中の座標も同様に $-1$ を掛けてしまえばよいので、そこまで問題ではないです。）

• $[2]$ $dist \% K == 0$ の場合

これもまだ簡単です。

$dist \% K == 0$ より、$dist/K$ 打でちょうどゴールできます。

実装方針には色々あると思われますが、私は $x$座標をまず揃えて、そのあと $y$座標を揃えるという方針でやりました。（これ以降の実装方針もこんな感じです。）

実装↓（冗長です、すみません…）

さて、ここからが†本番†です。

Golfくん「おっしゃ本気出すで～～～～～！！！！＾＾」

• $[3]$ $dist \% K ≠ 0$ の場合

どうしましょう。困りました。

この場合、てきとーに動いて $dist / K$ 打でゴール、というのができません。

 なので、 $dist / K$ $+ a$ 打でゴールするとして、 $a$ が最小になるようにゴールしたいですね。

どうしましょう。

とりあえず、$dist \% 2 == 0$ の時を考えてみましょう。（Kの偶奇によらず、なんか良さそうじゃないですか？）

• $[3-1]$ $dist \% 2 == 0 かつ dist \% K ≠ 0 $ の場合

$dist \% K == 0$ の場合のように動いてしまうと、$ b = K- dist\%K > 0 $ だけ、オーバーしてしまいます。

 ここで、$b$ の偶奇に注目してみましょう。なんと $b \% 2 == 0$ です！

つまり「いい感じに」寄り道をするとゴールできます！

ちょっと希望の光が見えてきました。

ここで注意したいのは、その寄り道を始めるタイミングです。

$dx+dy < K$ の時やればいいではないかと思ってしまいますが、$K < dist < 2*K$ の時やった方が、1打少なくなります。

そのように考えると、次の図のように動きたくなります。

$K < dx+dy < 2*K$ の状態の $(nx,ny)$ を考えます。

赤部分で止まり、次の打で $(X,Y)$ に到達しようという算段です。

$$ dx+m+n = dy-n+m = K $$ を解いて、

$$ n = \frac{dy-dx}{2} , m = K-\frac{dy+dx}{2} $$

となります。この時、$dy≥dx$ ですから、$n,m$ は共に正となり、セーフです。

同様にして、 $dy ≤ dx$ の場合についても考えると、

$$ dy+m+n = dx-n+m = K $$ を解いて、

$$ n = \frac{dx-dy}{2} , m = K-\frac{dx+dy}{2} $$

よって、$K < dist < 2*K$ の状況に $(nx,ny)$ を動かしたとき、上のように動かせば、$+2$ 打でゴールできます。

実装↓（$K < dist < 2*K$ の実装がだるいのですが、汚いので載せません。（は？））

配列OUTPUTに、出力する $(nx,ny)$ を保存しています。

ふぅ…。疲れましたが、まだこの問題は終わっていません。

最後の場合分けです。

• $[3-2]$ $dist \% 2 == 1 かつ dist \% K ≠ 0 $ の場合

どうしましょう…。困りました。Golf くんが悪魔の笑みを浮かべています。

ちなみに、この時、$dist \% 2 == 1$ より、$K \% 2 == 1$ です。（$0$ なら不可能）

いやもう無理だろこれ

さっきみたいに動かそうと思っても変数多すぎるし

はいはい Golf くんの勝ちですよ

どうせ私はまた通せないんでｓあれ？

$dist \% 2 == 1 かつ K \% 2 == 1$ ということは $2*K < dist または dist < K $ の状態から1打を「いい感じ」に動かして $K < dist < 2*K$ に残り $2$ 打の状態にすれば $dist \% 2 == 0$ で $[3-1]$ に帰着できる…？いやできるわ！勝った！

というわけで、$2*K < dist$ の状態で止めて、そこから $+3$ 打でゴールすることが可能だということが分かりました。

ちょっと待って

$ 2*K < dist $ の状態から $K < dist < 2*K$ に必ずできるの？

…………

…………………

どうしよう…………………（おい）

またもや場合分けです。

• $[3-2-1]$ $dist < K $ の場合

これは簡単です。

$x$ または $y$ の負の方向に $K$ 動かせば $ K < dist < 2*K $ となり、OKです。（$X ≥ 0 , Y ≥ 0$ としているので、オーバーしていない限りゴール必ずは正の方向にある。）

実装↓

• $[3-2-2]$ $ 2*K < dist $ の場合

これもまだ簡単です。

$x$ または $y$ の正の方向に $K$ 動かします。すると、 $K < dist < 2*K$ となり、OKです。

しかし、注意すべきなのは、正の方向に $K$ 動かす際、$X,Y$ をそれぞれオーバーしないように動く必要があります。（オーバーすると $dist$ がその分増えてしまうため）

実装↓

• $[3-2-3]$ $ K < dist < 2*K $ の場合

ちょっと困りますが、ここも場合分けです。（場合分けの数が多すぎませんか？ごめんなさい………）

• $[3-2-3-1]$ $ dist == (2*K)-1 $ の場合

右端のケースです。この場合、$dist$ が 一打後に $+1$ または $-K$ されてしまうとダメです。

何とかして回避しましょう。

説明するのが面倒になってきました。（は？）

実装↓（+1しちゃダメ というコメントは、「一打後に $dist$ が+1以上されていてはダメ」という意味です。）

こんな感じにすると良いです。

結局は、$(正の方向に進む距離) > (負の方向に進む距離)$ になっている かつ $1$ 以上は負の方向に進む ことをすればよいです。

• $[3-2-3-2]$ $ dist == K+1 $ の場合

左端のケースです。これは、$$[3-2-3-1]$$ と反対な感じでやると良いです。つまり、

$(正の方向に進む距離) < (負の方向に進む距離)$ になっている かつ $1$ 以上は正の方向に進む ことをすればよいです。

実装↓

• $[3-2-3-3]$ $ dist ≠ K+1 かつ dist ≠ (2*K)-1 $ の場合

これは $[3-2-3-1],[3-2-3-2]$ に比べれば楽です。

$dx < dy$ の時、$dy > \frac{K}{2}+1$ なので、$y$ の正の方向に $\frac{K}{2}+1$ だけ動かしてもオーバーしません。よって、$y$の正の方向に $\frac{K}{2}+1$ 、$x$ の負の方向に  $\frac{K}{2}$ （$K$ は奇数なので割る2は切り捨てて考えます）動かすことで、1手動かした後でも $ K < dist < 2*K $ を保つことができます。

$dx > dy$ の時も同様にして、 $x$の正の方向に $\frac{K}{2}+1$ 、$y$ の負の方向に  $\frac{K}{2}$ 動かすことで、1手動かした後でも $ K < dist < 2*K $ を保つことができます。

実装↓

 これで1打調節が正常に終わりました！！！！！！！！！！

ふはは、ついにお前を倒す時が来たようだなぁ？ Golf クンよぉ！

これで $[3-1]$ に帰着できました！きちゃ！（きちゃく だけに）

あとは $[3-1]$ と同じことをやればよいです！

残りの実装↓

これで全ての場合を計算することができました！！！！

あとは $X,Y$ を負から正に直したなら出力時に $-1$ を掛けるのを忘れないようにします！

これでコードは完成しました。

渾身のコードを提出するときがやってきました。

うおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおおお

「ずいぶん..........苦しそうじゃねえか....？あ....？Golf め......!吐き出せっ...!そんなに苦しきゃ、吐き出せっ..........!おまえが喰らってきた...競プロer の........WAっ....!TLE..!時間っ....!苦しみ..!絶望..!そのすべて....吐き出せっ...!」

`＿　　　　　　　(三|
|ﾋ_)　／￣￣＼　　LﾆO
| | ／●) (●)＼ ｜｜
|_|(　(_人_)　　)∧亅
| ヽ＼　￣　＿／ ミﾉ
ヽﾉﾉ￣|ﾚ―-ｲ / ﾉ ／
　＼　ヽ＼ |/　イ
　／￣二二二二二二＼
`｜答｜　　AC　　｜｜
　＼＿二二二二二二／

完

自己満足な記事でしたがここまで読んでくれた方がいれば嬉しいです。

ありがとうございました。

提出したコード(AC) 

atcoder.jp

AC後に解説見ても天才すぎて意味が分からなかった話は黙っておきます

入水しました

皆さん初めましての方は初めまして。そうでない方はすでにこのブログのタイトルで察したかと思います。

私、おぉ味噌汁。は、2020 年 12月 13日のAtCoder Beginner Contest 185 にて、

入水しました！

いえ～～～～～～～～～～～～～～い！！！！！！！！！！！！（ﾄﾞﾝﾄﾞﾝﾊﾟﾌﾊﾟﾌ）

ちょうど1200ピッタリで入水なのも、なんかいいですね。

レートグラフからも分かるように、「長く」「苦しい」闘いでした。本当に。

でも競技プログラミング楽しいからここまで続けてこられたんですよね。

Twitter等のコミュニティで支えてくれた方々、解説等を書いてくれた方々には本当に感謝しています。ありがとうございます。（入水ツイートには32件のおめでとうリプがされて、普通に嬉しくて泣きそうになりました 本当にありがとうございました。）

さて、入水もしたことですし、自分の精進など、緑→水にかけての心がけとかについて話していこうといきたいところなのですが、

お わ か り い た だ け た だ ろ う か

この記事でいくつか疑問に思うところがありますね？

まず1つ目。ABC185は昨年の12月13日に開かれたにもかかわらず、このブログを投稿しているのが今年の2月3日だということです。

次に2つ目。レートグラフの右端が変なところで切り取られています。

……おや？右端に何やら違和感が…？

何やら緑色の "何か" が見えます。

実は、これは描画ミスではなく、この入水した次のコンテストで、緑落ちしてしまったんですね。

あの後、私は、 驚愕の 4連続灰・茶パフォ笑を出して入水した喜びも束の間、一気に緑中位、レート1028まで落ちてしまったのでした……。

本当に何？？？？？？？？？？？？？

まるで中の人が入れ替わったかのようですね。私以外私じゃないのでこれは正真正銘私なのですが。は？

本当にこの4回の激落ちはなかなかに精神にキました。

茶diffは解けないわ 周りはどんどん伸びていくわ 解ける問題が解けないわ

はぁ～…、クソデカため息^^♡

これじゃせっかく入水したのに入水したくなりますよ、ワラｗ（ガッハッハ）（冗談）

これから少しずつでもレート戻していけたらいいなーという感じです。精進も欠かさずに。

入水記事書こうと思ってたらいつの間にか色落ちして落ちるところまで落ちて 「あれ、え、あｗ、えｗ、あ、終わりでーすｗｗｗｗｗ」ってなったことを報告したかっただけです。

そんな感じでこの記事は終わりです。

ありがとうございました。