1000文字書いたら寝る1

今日は1000文字書いたら寝ようと思う。また思いついたことから書いていくので、オチつかなかったりするけれど、流れるように思考を吐き出すことが目的なのだから、許されて欲しい。

早速筆が止まる。どうして止まったかというと、流石に変な表現だなとか、この文章意味が分からないなとか、そういうのもあるけれど、何より大きいのが、これって、人に伝わったら良くないよねという、コンプライアンス的なサムシングだと思う。サムシングってなんだよ、いくつかの何かって言えよと思うかもしれないが、頭の中に最初に出てきた言葉を発すると時々こういうことも起きるのである。

どうしようかな。あ、そういえば町をあるいているときに、時々人がN人いて、彼らの軌跡が～みたいなよく分からん独り言をぼやきたくなるのだけれど、そういう雑談にならない雑談を話せる人ってこの世に何人いるのだろうか。もしいたら交流したいなと思いつつ、そういうのって自分の頭の中でやったらよくない？とも思うので、思うだけにしておく。

あ、本当に話題が無くなっちゃった。中身が何も出てこないとき、存在しないということが存在するみたいなメタな話に持って行きがちなんだけど、人々とお話しているときは大抵日常的な体験、アニメやゲームなど共通の趣味の共有などが多いと考えられるため、なかなか大衆とはひどく個性的なものだと思うことがある。というのは嘘で、僕はズレているんだなあと感じやすい。

そういえばこの前は才能について悲観していない（むしろ頑張っていないことに対して後ろめたさがある）という類のことを書いていたようないなかったような気がするけれども、それについては「幼少期にできないことが多すぎて、周りの普通と呼ばれる人たち95%を天才だと思い続けてきたので、今更突出している人を見ても驚かない」という答えが正確かもしれない。驚き慣れているというか、悲観を通り越して諦めに近い。しかしながら、人生であれ才能であれ、諦めたものに情けはやってこないものである。いや、正しくはそういう風に自分を責めてしまうのである。

まあネガティブなことばかり言っていても仕方がないような気もしてきたので…ふと思いついた。そうそう、こういう風に思っていた方がいいよと分かっていても、僕は自分自身の抱いた気持ちを無かったことにはしたくない、後ろの足跡もしっかり認めたいと思うタイプだと思う。それを人に発することは滅多にないけれど、ふと思った「なんとなくいい、悪い」の感覚というのは、隠れた目的を引き出す重要なキーだったりする。だから、それに対して「良い・悪い」と考えるよりも、事実として一旦「そういうこともあるんだなあ」と受け入れておけばいい。そうすると、数年後に「あ！あのとき自分が思っていたのはこういうことだったのか」って思う時が来る。

今までそうやって「自分なりの正解」を辿ってきたように思う。今はできないことが多すぎて、迷惑をかけまくっている感じがして、しんどいときもあるけど、それは「僕も人並みに苦しいという感情や、プレッシャーという感情を体験することができたな。」と思って、内心知見を深められたという喜びさえ感じていたりする。まあ現状をそのままにしておくと行きつく先は堕落なので、そうならない程度には漕いで過ごしたいと思う。

ああ眠くなってきたな。もういつの間にか1400文字になろうとしている。おやすみなさい。また明日。

眠れない夜には条件反射で駄弁ってみることにした1

僕は文章を書いている。筆を止めずに書いている。思いついたまま駄弁っているので、ほとんど手は止まらずに書けている。何か考えているようで何も考えていない。そうやって生きてきた。本当は頭の中だったらカッコいいセリフとかもスラスラッとそれっぽく出てくる。しかしながらパソコンでタイピングをしていると、あるいは口に出すと、急に出てこなくなるのだ。夢を朝起きたら忘れているように、想像したことをアウトプットしようとするとなんか形にならないのだ。それがもどかしい。

実はすごいものを考えているんだぜと思ったりもするけれど、具体的に形にできないことで、それは幻想だったことが判明する。実はモヤモヤッと誤魔化して想像していることに、頭のなかで描いているうちは気が付かないのだ。思いつくだけなら誰だってできるという言葉は僕にとっては背中を押す言葉ではなくて、行動しなさいという戒めのように聞こえる。

さて次は何について語ろうか。いや、語っているのだろうかこれは。よく分からないツイート群である。さて今僕はとてもしんどい。心臓がドキドキするような、呼吸が浅くなるような気持ちである。それは他者のせいではない。本当に。むしろ助けて頂いているにも関わらず、タスクを全然こなせない、散らかってしまう自分にイライラするのである。困ったどうしよう、時間が足りない、いやどこから手をつけたらいいか分からない。

手先は不器用だけど算数とかはちょっと得意だからエンジニアとして食っていこう、というかそれ以外に自分がまともに生きていける道が見えないのだからそうするしかない。と思っていた。苦手なことが沢山ある以上、人並みかそれ以上にできることをメインウェポンとして食いつなぐしか方法はないように思う。いや、厳密に言えば工場勤務や清掃など、あるかもしれない。頑張れば食いつなぐことは可能だろう。だが、今強みが無い状態でぷかぷか浮いていると、将来の選択肢を狭めてしまうことになるかもしれない。それに快適とは程遠い、辛うじて生活できるような状態になってしまうのも少し怖い。ならば多少つらくても、向いてなくても、今生活に困らない程度のお賃金が得られて、少しでも得意なことと社会的価値に相関があるところで、頑張っていくのが現実的ではないだろうか。

ビジョンというのだろうか、やりたいことであって誰かに貢献できるようなものは特に思い当たらない。そりゃあ一人だけ楽しめればいいのだとしたら、僕はずっと算数パズルや音楽ゲームにふけって、黙々と取り組むことで安心したり、いつもより少し成長したり、何か法則を発見したりして、ああこれが楽しくて安心する気持ちなんだというのを再認識したい。そこから感じたことに対して哲学的にアレコレ考えたい。なんで生きるのかとか、どうして子孫を残そうとするのかとか、そういう話題の手がかりとして、自分の趣味とか経験が存在するのだと思う。

ああまた意味分からないことを呟いてしまった。そういえば職業としてアレコレするとしたら、必ずと言っていいほどコミュニケーションや管理能力といったものが必要になってくるように思うが、どうしても適応できるビジョンが見えなくて困っている。どうしたものだろうか。いや、タスクが溜まっていて、かつそのタスクのうち進め方に不安があるもの、止まっているものがあって、どのタスクも計画通りに終わらせられる自信を持てないと、パニックになるのだなあと思った。計画を立てられないのではなく、予定通りに実行できない、ずるずる後ろにズレてしまうことが多いのだ。これはマルチタスクが苦手だからだと思っていたけれども、この日はこの仕事だけやると決めたとしても、例えば仕様が頭の中でまとまらなくて１日を浪費してしまうような漢字である。どこから片付けたらいいか分からず途方に暮れ、数時間のやる気が徒労に終わるときに、自分自身に対する信用がどんどん損なわれていくのだ。

継続的な努力は継続的な内的報酬があってこそ成り立つものなんだと思う。例えば音ゲーだったらトリルと縦連、そのスピードと精度に拘りをもっているから、そこに夢中になるだけで勝手に内的報酬が生じるし、それによって自ずと継続する。いや、継続するというよりは、おうちでくつろぐ感覚にも近いのかもしれない。

短期的かつやることがハッキリしている場合の努力であれば不安を煽ることで可能だけれども、それだけでは長続きしない。少なくとも僕は根性のあるほうではないので、このやり方だけでは難しい。（ただやりたくなくてダラダラしているだけと言われたらそうかもしれないが、それをすぐ改めるくらいなら、こうして夜更かしをして文章を書いていることはありえない。）

そういえば真面目ってどういう動機によって発生するのだろうか。実現したいことがあるからそうなるのだろうか、あるいは嫌なことを避けるためにそうなるのだろうか。自分の場合は、衝突や争いがとても怖く、平穏を維持するために真面目に適応していた気がする。例えばトモダチが部活をサボろうと言ってきたとする。自分は頑張りたくてもそう言われたら反論することはできない。できたとしても少し強く押されれば、恐らくシタガウ。不真面目に見せかけた真面目である。バカ笑いも意識的にやっているので、そういうところが真面目である。しかしボロがでる。自分自身がやりたいことではない以上、どこか大根役者感があるのである。元々器用な方ではないから尚更である。

そういえば、自分の才能を悲観したり、他者に対して「器用な奴だ」みたいに別人と決めつけたりする行為に対して、罪悪感がある。と同時に、自分は怠けているだけではないだろうか、頑張っていないだけではないだろうか、そんな人はいつかみんなから嫌われて、将来の選択肢がゼロになるだろうという謎の不安がある。自分は才能ではなくて、努力や熱意、あるいは普通になれないことに対してコンプレックスを抱いているかもしれない。

だからといって何かのせいにするのも嫌である。だからよりどころの無い悲観は、全て自分に向ける。自分さえ悪ければいい、自分だけ不幸になって他の人が幸せならそれでいい、という独りよがりな考え方に陥りがちだ。

感謝も多い。自分がどうあれ、仕事上必要なことを率先して助けてくれる仲間も多く、人間関係については理想的だと思う。いい人たちすぎてしんどいくらいである。この恩は仕事で返すしかない。

当然利益を上げる必要がある以上、効率を考える必要がある。効率とは何時間かけたらいくら儲かったかである。それ以上でもそれ以下でもないと僕は考える。そこに「今反映される効率」と「長期的に反映される効率」があるのは確かだが、人間関係とか、仕事上の支援とか、管理とかそういったものも、「プロジェクトを成功させること」「生産性をあげて、その対価として、自身やメンバーの生活、投資家へのリターン、次なる成長のために必要なお金を回収すること」が狙いなのだと思う。そして会社としての夢を実現するための、船員である。船員は船長から搾取される関係でもなければ、泥棒でもなくて、協力関係である必要がある。つまり、メリットを提供し合えるし、そうすることに合理性がある必要がある。

そういう意識高いことを考えているつもりでも、脳内お花畑の自分は、やはりかなり霞んで見えている概念である。そもそも自分自身の「ただ手を動かせばいいレベルの仕事」さえも適切な判断ができず、適切な成果物を作ることができていない状況なのだから、まずは手を動かしていけるだけのスキルが必要なのである。

しかし努力云々はさておき、現状、純粋に「頭が悪いな俺」って凄く思う。例えば、エクセルに入出力の仕様をまとめますと言っても、どこから説明したらいいか分からず、１時間経っても白紙のまま、もしくは複雑な文章が生成されて困惑させてしまうことが多い。頭の中では、画面があって、そこにユーザがこういう情報を入力すると、このデータ群からこういう情報を検索してきて、こういう計算をして、こんな風に出して、こういう風に保管するよ、みたいな流れが見えていても、それを実際に形にすることが困難である。技術的な地力が足りない。

僕が唯一客観的に得意と言えるのは競プロだと思う。音ゲーは弐寺８段、周りより上手くないレベル。に対して競プロはAtCoder黄色レベル。５年以上やっているだけあって安定感もついているけど、音ゲーよりも頻度も歴も少ないし、大きく地力が伸びたのは情報オリンピックの問題を解いていた半年くらいであるから、努力して伸ばしたというよりは、センスと典型力と、惰性で毎回コンテストに参加し続けたことが要因として上げられると思う。

そういえば成長曲線というのは、僕はlog(time)に定数を掛けたもののようなイメージを持っている。定数はセンスに相当するものなのかなあって思う。ｙ軸はトリルの速度とか、問題を解くスピードとか、まあスピードに関する項で考えるのが分かりやすいかなって思う。イメージとして、最初は速いが、徐々に伸び悩む感覚を持っている。ただ、正確には階段のようなジャンプがあって、ある部分でのつまづきというのが解消されると、飛躍的に伸びる瞬間というのがある。練習によってある程度の地力が備わった状態で、コツに気づいたときという感じだ。

ああまた夜更かしをしてしまった。明日も仕事なのになあ。謎の余裕ってあるよね。あまりにもどうしようもなくなると、諦めがついて、かえって落ち着くような。あれって生物学的にはどういう仕組みなんだろう。ちょっと気になる。

ところで気になると思ったとき、本気で気になって調べるというよりは、会話のたたき台を作成しているような気分であって、これが僕にとって「誰かに展開して欲しい、話のタネ」になっているのである。特に目的があるわけでもなく、強いて言えば親睦を深めるため・あるいは自身の体験を共有していい気持ちに浸るため、日常的な話題を話すことってあると思うが、それに近い感覚である。

僕には友達は少ないけれども、どちらかというとみんな友好的に接してくれていると思う。成果を出すために必要であれば、あるいはその人自身の価値に牴触するのであれば、多少手厳しいときがあったっていいのだが、幸いにも平穏な関係性と言えるであろう。周りの人々にはやはり感謝してもし足りないくらい、良くしてもらっている。

一方で自身のカオスを共有できる人がいないというのには少しばかり寂しさを覚える。面白みもあるわけではないし、とっかかりになり得るものはどこにもないのだから、遠慮しても仕方がないと思う。いや、「いない」「仕方がない」といって、全て受動的な行動に走ってしまっていないだろうか。「決めつけることで素直になりたい、現状をはっきり口にすることで安心したい」という気持ちがある一方で、「それって努力を放棄することになるのではないか」という気持ちもあって、その中で葛藤が生じているのである。

そんなこんなで思ったことを文章で書いてみた。深く考えているなんてとんでもない。まるでAIが作成した文章のように、それっぽい言葉を連ねているにすぎない。連想ゲームの断片なのである。AIに謝った方がいいかもしれない。最近のアルゴリズムと学習の仕組みは優秀だから、人間と遜色ない文章を出せるものだって沢山ある。そういえば不自然な文章には、コンピュータらしさがあったりもするけれど、コンピュータがおこなう一つ一つの演算って規則的だから、統一感という意味では自然になりやすいのではないかと思ってしまいがちである。どちらかといえば、統一感のない気分で書いた「人間らしいもの」こそが不規則で、不自然なのではないかとさえ思う。でも人間らしいものは人間にとって自然である。ここら辺のさじ加減は今一つ分かっていない。

自然かどうかを判定する上で重要なものは、想定されるルールと一致しているかどうかと、物理的な規則性があるかどうかの２点であると思う。人間にも本当は物理的な規則性があって、その暗黙の規則と不一致な挙動をしめせば不自然とみなすのであろう。ところで、人工的な自然って面白いと思う。手を加えている緑なのだけれども、自然とは手を加えていない状態なのだから、このちょっとした矛盾感が好奇心をそそる。

なんかどうでもいいところに考えが飛んでしまったなあ。「そういえば」「ふと思ったけど」を頼りに、一貫性とは程遠く、ちょっと関連するようなしないような話題をドンドン展開していく思考が向いているかもしれない。謎解きやパズルだったら、部屋をめちゃくちゃに散らかして、一つ本質を見つけたら、最低限の論証をして通すことが多い気がするので、こういうのは得意寄りだと思う。一方で、一貫性や無矛盾・網羅性を要求される思考は苦手だと思う。詰将棋は苦手だし、システム開発も苦手意識がある。理系のイメージとして真っ先に浮かぶのは後者なので、その部分において期待値と実情に対して誤解が生じやすい部分なのかなと思う。

そこにしか行けないと思うから、他にどうしたらいいか全く分からないから、とりあえず居座るための努力をしてしまうのを変えたい。本当は自分が好きなこと・心が満たされることがしたいけれども、何をしたら満たされるのか、満たされながら最低限の生活が担保されるのか僕には分からない。最低限の生活には自分だけではなく、親や兄弟の生活もかかっているのだから、自分さえ生活できれば十分とは限らないというのも、念頭に置いておく必要がある。

僕は何にも縛られたくない。何にも不安を感じたくない。できれば木陰でずっと寝ていたい。だけどそれは現実的には不可能なので、どこかで頑張る必要がある。やりたくないからやらないみたいなことは毛頭言うつもりはないけど、集中力を維持するのが難しいという問題は昔からあるので、興味か能力どちらかでマッチするものを選ぶ必要がある。

同じでしょって思われている文化のなかでも、空気感や求められているものが全然異なるケースはある。競プロ界隈とエンジニア界隈では全然違う感じがする。でもそれを言語化できなくてモヤモヤしている。僕は開発の人がパズルで苦戦してあれ？と思うように、開発で苦戦してあれ？となっているのである。

とりあえず今日は寝ることにして、明日また考えることにする。できないことはできないのだから、無理な計画を立てすぎないようにする。

なんか一つも物事が進まない考え方をしてしまっている気がする。表面をなんどもなぞる不毛なループ思考をやめて、一つでもタスクを減らしたい…。だからといって適当にやるのもダメだし、放置もダメなので、うー。

僕がモチベーション低いと、周りにも影響が出ると思うのよね。やっぱり楽しそうに働いているのが一番嬉しいだろうから、楽しみたいと思うのだけれども、なかなか思うようにいかないなあ。僕自身が一番楽だと思っている立場でこれなのだから、将来思いやられます。

競プロだけで食っていくこと（お金を回収すること）は現状ほとんど難しそう（少なくとも僕にとっては無謀）に見えるし、正直に言えば「好きだけれども、一途になれるほど情熱的でもない」からうーんだよね。強みにすることは出来ると思うけど、現状は全くと言っていいほどできていないよね。むしろ「あー黄色コーダーでも、仕事出来ないやつは全然できんのか」というのを見せてしまっていて、競プロerの「信頼性」を僕が落としてしまっているんじゃないかと不安になる。

とりあえず好きなことがそれで良かったなとも思う。好きになるものが、社会的に認知されているかそうでないかで、将来の道や世間体が変わってしまうことが、僕は正直嫌だと思っているけど、現実逃避するよりかは、社会的に認知させる方向に持って行くか、そういうのを一切気にせずに楽しむ時間を作るために普段一定以上の頑張りを見せるのが一番いいんだろうなあって思う。

思ったことがある。全部自分ができないからダメなんだと自分のせいにしているように見えて、本当は批判されないために予防線を張っているだけなんじゃないかと。ごめんなさいと先に言っておけば、謝っておけば、相手からは手を出しづらい、それを前意識的に利用しているのではないかと。

もちろん意図してやっているつもりはないし、危機感は持っているけれども、行動できていないので、もし上記のように捉えているのだろうと思われても致し方ないだろうし、自分だって本当はそうなんじゃないかと思ったりもしている。

まあ一理あるのではないかと思う。もっと感情的な部分ではなくて、自分が出した結果や起こした行動を率直に捉えて、非効率的な部分や曖昧な部分があったら解決しにいく心構えが必要かなと思う。問題はそれを見つけることはできても、収拾がつかなくなって不安が増えるだけという状態にあるのだが。1日あれば、1時間あればできる改善案を8個実行することができるので、そのくらいのスパンで実践していけるのが一番いいけど、実際には小さいことでも1か月かけてしまうことがザラにある。

スピードを気にしがちである。とはいえスピードというのは「明確な理解」があれば出すことはできて、落ちてしまうのは「分からない・決められないこと」があって「頭がこんがらがっているから」だと思う。ということは品質も低い。クオリティを上げれば自ずと中長期的なスピードは上がると思う。理路整然としていれば、手も加えやすい。

だから品質を上げればいいのだが、陥りやすい罠として「～にまとめよう」がある。そもそも、それが難しい状態なことが多いので、まずは気になることを箇条書きで列挙していくのが重要なんじゃないかと思う。そして罠としては「箇条書きするときに、トップダウンにならず、細かいところばかりを気にしすぎてしまう」がある。最初からトップダウンである必要はないのだが、目的や動作がハッキリしている書き方が出来ると良いねと思う。

大抵は綺麗に物事は進まなくて、足りないものがあるから、どこかで妥協する必要があるのだけれども、「その妥協は重要な決定かどうか」「じゃあどういう流れで目的を達成するように、ルートを変更しているのかどうか」は常に気にした方がいいのかもしれない。それをする合言葉「そもそも」がある。前提については意識して、なるべく一人で思い込んでいそうなところは洗い出したい。

うーん、疲れたから寝よう。無思考で書いているだけあって、あんまり良くないことも書いていると思うので、あとでこっそり直そう。（そう言ったものが直されたこと、なし）

ARC 094 D. Worst Case

問題

atcoder.jp

考えたこと

まず条件を整理

• 順位付けとは「全単射」
• 1回目i位の人が、2回目でp(i)位を取ったとする。
• i×p(i) < ABになるiの個数を最大化。
• ただし、p(i)は相異なり、p(A) = B.

貪欲法に帰着 → 実験

• p(i)の値域を考えると、
• S(i) = {j | j: int, j >= 1, i×j < AB, j≠B} if i≠A
• S(A) = {B} if i = A として
• p(i) in S(i)なるiの個数を最大化。

• i < jについて、S(i)はS(j)を包含。iが大きいほど選択肢は狭い。

• 厳密なことはさておき、iが大きい方から見て、「S(i)から選べるなら選ぶ（＆最も小さいのを選ぶ）」 としてよさそう。

• ここまで分かれば、とりあえず実験できますね。

  • うーん、分からん。

    

    A=4, B=5の実験

対称性

忘れてたけど、対称性よりA <= Bを仮定して良いですね。
以降は、A <= Bを仮定します。

重要そうな条件を式で表してみる

A = 5, B = 5, 6, 7, …などで
貪欲法の実験をしていると、iがある値以下ならp(i) in S(i)が常に成立していそう（多分i <= A - 1？）に思えた。
これを示したい気持ちになると、
「S(i)がB + 1を含む条件 (Bが邪魔にならない）」
「S(i)の大きさが狭義単調増加な条件（p(i+1)が邪魔にならない）」
を知りたくなる。

まず、ij < AB ⇔ j < AB / i ⇔ j <= [(AB - 1) / i]
ここでは、[]で小数点以下切捨てを表します。

定式化：
+ i: int, i >= 1
+ [(AB - 1) / i] > B
+ [(AB - 1) / i] > [(AB - 1) / (i + 1)]
(箇条書きにならない。help！）

[(AB - 1) / i] > B

(AB - 1) / i >= B + 1
AB - 1 >= i(B + 1)

i = Aのとき
A(B + 1) > AB - 1よりNG.

i = A - 1のとき
(A - 1)(B + 1) = AB + A - B - 1
A <= Bを仮定すると
AB + (A - B) - 1 <= AB - 1
よりOK.
A <= Bを仮定すると、1つ目の条件は単に「i < A」と言える。

[(AB - 1) / i] > [(AB - 1) / (i + 1)]

AB - 1 = pi + r (p, r: int, 0 <= r < i)
AB - 1 = q(i + 1) + s (q, s: int, 0 <= s < i + 1)
として、p > qになる条件を探せばよい。
まず、p = [AB / i] >= [AB / (i + 1)] = qなので、p >= q.

pi + r = q(i + 1) + s
pi + r = qi + (q + s)
より、p = qならば、r = q + s. つまり, q + s >= iが条件.

i < Aのとき、i + 1 <= A.
q = [(AB - 1) / (i + 1)] >= [(AB - 1) / A] >= B - 1.
A <= Bを仮定すると、q >= A - 1.
よって、「i < A」のときは常に成立

中間まとめ

以上より、i < Aのときは、p(i) > Bかつp(1), …, p(A-1)を相異なるように構成できる。
i > Aのときの取れる個数が本質になった。

i > Aのとき

そもそも[(AB - 1) / i] < Bなので、「Bを取っちゃダメ」という条件を無視して考えられる。
あと、「段差が1以下」が成り立っていると都合が良いな～って思っているので、
それが成り立つ十分条件を定式化してみる。

定式化：
・(AB - 1) / i - (AB - 1) / (i + 1) <= 1
(AB - 1) * (i + 1) - (AB - 1) * i <= i(i + 1)
(AB - 1) <= i(i + 1)
これは、i > Aで常に成立…しません！！！（一敗）
でもこれが成り立つ最小のiは2分探索で求められる。
i >= i0で成立するような最小のi0 (i0: int) を取ると、(i0 <- max(A + 1, i0)をしておく）
・i >= i0までで、1 ～ [(AB - 1) / i0]まで取られる。
・A + 1 <= i < i0では、異なる値がしっかり取られる。

まとめ

• 対称性より、A<=Bとする（重要）
• i<Aとi>Aを別々に最大化できる
• i<Aでは常にp(i) in S(i)にできる
• i>Aでは、(AB - 1) <= i(i + 1), i>=A+1なる最小のiをi0とおくと
  • i>=i0までで、1～[(AB-1)/i0]まで取られる
  • i<i0では、相異なる値がしっかり取られる
  • i0は2分探索で求められる. Aではダメ、ある値からOKで、B+1ではOK.
    • A = Bのとき、i0 <= Bを仮定できないことに注意（一敗）

よって、i0を求め、[(AB-1) / i0] - (i0 - 2)を出力すればよい。
（i0 - 2はi in {1,2,…,i0-1} - {A} なるiの個数）

ソースコード

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

signed main() {
    int q, a, b;
    cin >> q;
    while (q--) {
        cin >> a >> b;
        if (a > b) swap(a, b);
        int ng = a, ok = max(a + 1, b);
        while (ok - ng >= 2) {
            int mid = (ng + ok) / 2;
            if (mid * (mid + 1) >= a * b - 1) ok = mid;
            else ng = mid;
        }
        cout << ((a * b - 1) / ok) + ok - 2 << endl;
    }
    return 0;
}

感想

これ、難しくないですか？
条件を定式化する力を求められているように感じました。

式変形をしてから気付いたけど、貪欲法に帰着するパートで「最小順位」ではなくて「最大順位」を取るように すると（そのようにしてもOK）、解法と同じ構成になっているから、もっと分かりやすかったかもしれない。
これに気付くには、「逆に〇〇したらどうだろうか」をするか、「(AB - 1) / iのグラフの性質を活かすには、最小（途中）を取るよりも、 最大（一番上）を取る方がよさそう」をすると良いのかなあと思った。

難しいことを目指してしまう原因について（自己分析、反省）

注意

(2020/11/19)

> これ、久しぶりに振り返ってみたんだけど、思考回路の黒歴史っぽさがありますねぇ。まあ当時はごちゃごちゃ考えすぎていたということで…（今もだけど）

 > 自分が自分のために書いたメモが元になっているので「指示的な」言葉が多くなっています。「人に読んでもらうため」という文脈ではあまりなくて、「あとで自分が振り返るための日記」という感じです。とはいえ、強い言葉が目立つので反省。

これは自己反省の記事です。

「今の自分」を基準に書いた記事ですので、他の人、あるいは「未来の自分」には全く当てはまらないかもしれません。

また、科学的根拠は全くなく、あくまで「思ったこと」をつらつら書いているだけなので、間違いも数多くあるかもしれません。

ということを念のため書いておきます。

燃えたくないので。

難しいことをしようとしすぎていませんか？

難しいことを目指すこと自体は良いことですが、最初から完璧にしようとして手が止まるのは、勿体ないです。

本当に些細なことでいいから、進捗を出しましょう。

進捗が出れば、モチベーション上がりますし、理解も深まります。

…と頭では思っているものの、難しいことをついつい目指してしまいます。それはなぜでしょうか。

また、それぞれの原因に対しては、どうアプローチしたら良いでしょうか。

ちょっと考えてみました。

難しいことを目指してしまう原因

１．怠惰（面倒くさいのは嫌だ。一発でドカーンと解決できないか？）

怠惰からエレガントな解法が生えることもあるので、一概に悪いとは言えません。
しかし、一発でドカーンと解決することは、一般に凄く難しいです。
一つ一つ分けてコツコツ解決した方が、大抵楽だったりすることは、頭に入れておきたいところです。

例えるなら、崖を1回で登るか、100段の階段を使って確実に上がるかの違いですね。階段登りたくなくて辺りをうろついていたら、エレベーターを見つけちゃうこともありますが。そんなときはラッキー！

２．焦り（こんな悠長にやっていては間に合わない！など）

こちらの方が深刻です。
焦りから自分に難しい課題（例えば、1日8時間勉強する！など）を課してしまうことは多いものです。

しかし、それは「頑張ろうとしすぎてしまい」、それが重圧となって手が動かないことが多いです。結局、何やったらいいか分からないというのもありますし、すぐできることではないから手を動かす気力が起きないのです。

しかし、「もっと頑張らなきゃいけないのに、何もやってない」という思いは募るので、段々重たい気持ちになっていきます。

要は、ハードルを自ら高くしてしまって、跳び越えられなくなっている状態です。

もっと軽く始められる仕組みを考えましょう。

経験的には、すぐに達成できる目標を立てるとよさそうです。

目標の高さよりも、目標の軽さを意識しましょう。

ぱっと手が動くとよく、PDCAサイクルを素早く回すのがコツです。

最初は「え？こんな簡単なことでいいの？」という目標で良いです。
目標が低くとも、素早く達成してしまうことの方が大事。

また、疲れすぎると、次やりたくなくなってしまうので、疲れを取れるときは、しっかり休みましょう。

３．ソースコードが汚くなるかも～みたいな懸念から手が動かない

一度書いたソースコードを修正するとき、1日で書けないプログラムを作るときは、勇気がいります。あとでぐちゃぐちゃにならないか、という不安が漠然とあり、手が動かないことがあるようです。  

原因として、  

- シングルタスク。整理整頓が苦手  

があるような気がしています。  

大きなプログラムを書くには「構造を切り分けること」が大事になってきます。

これは、ものを整理するときと似ていて、「これはどのタンスにしまっておこうか」

といった思考をよくします。  

これが苦手だと、けっこう辛い。  

振り返ってみた点として

- 頭だけで考えている。

がありました。

考えすぎている、というよりは、考えたことを記録していないことで何度も考え直しが発生していることが問題な気がします。 

自分の記憶力は信用できない。   

「記録をつけよう。一枚でいいから設計書を書こう！  」

あとは、バージョン管理ですね。「元に戻せる」という安心感があるだけで、だいぶ違います。

- Gitを使おう（僕はprivate repositoryというのを使っています）

ただ、Gitにpushし忘れたり、commitのときのコメントで何を書くべきか分からなかったりしがち。  

これは、お困りです。  

４．そもそも問題をどう分解したら良いか分からない、問題を論理的に整理できない

論理的に整理できない。これはしばしば起きることです。漠然としていて、全然話が進まない…といった場合です。

これは、論理的に考えるのが比較的得意であるなら、改善できます。

いくつか方針があって、例えば

・なぜその問題を解決したいのかを探ること、

 ・大事な要素を列挙→抽出すること

・具体例を挙げること

・フォーマルな形で示すこと

などがあります。

また、長いプログラムを書く場合など、長期的な取り組みの場合は、たとえアルゴリズムが自明（やるだけ）に見えたとしても

・設計書

を書いた方が良いと思います。ラフでも良いです。

これによって、イメージが鮮明になります。

複数人に指示を出すとき…これは大の苦手なので何とも言えませんが、

1つコツとして挙げるならば

・マルチスレッドプログラミング

だと思って設計することです（は？）。例えば

・ダイアグラム（時刻と人の表）

を書いてみるなど。（それはそう）

５．根本的に分からないところがあって、手が止まっている

例えば、AtCoderの過去の順位表を100倍速でアニメーションするWebアプリを作りたいとします。

AtCoderの提出履歴からアレコレ集計して、表示して…って、あれ？AtCoderの提出履歴ってどうやって取ってくるんだっけ？

API？httpリクエスト？なんじゃそりゃ？

色々調べてみたが、思ったようにコード（ほぼサンプル）が動かない。Webの仕組み、どう頑張っても理解できないし、サンプルコードも転がってないんだけど、どうしたらいいんだ（絶望）
　
あるいは、「運動向けの音質の良いイヤホンを調べて欲しい」という要求に対して、「イヤホン」の音質の違いがどうしても分からないといったことがあったとします。
　
つまり、問題は分解できているものの、「分からない」ことがある場合です。

この場合、詳しい方が近くにいたら、多少申し訳ないですが「素直に聞いてみる」のが良いと思います。このとき、「何がしたくて、そのために何をしようとしているのか、どこまでできてて、どこが分からないのか」あたりは明確にしておくと良いかもしれません。
　
詳しい方が近くにいない場合は、とりあえず分かるところ、できるところを何らかの形で作ってしまいましょう。

そうすれば、イメージが湧くと思います。

やはり、何もない状態で考えるというのはしんどいです。しんどいことはしたくありません。では、何かある状態にしてしまいませんか？
「あとこれさえあればできるのにー」という状態にしておけば、調べる気力も湧いてきます。人にも相談しやすいです。
　
ここでポイントとして、作るものは「ラフイメージ」の方が良いということです。

労力が小さいというのもありますが、なんというか、作り込みすぎると
「分からないところ」の内容によっては、作りを変えなければいけないことがあります。その場合に、手直しがしづらくなってしまいます。

手戻りという奴です。

また、質問は早めにできたほうが嬉しいです。
だから、頑張って作り込もう！とはしなくて良いです。いいですね！

６．ムキになりすぎている

真面目な人にありがちです。僕もそういう傾向があります。
いくら試しても上手くいかない、頑張ってスライドを作ったらかえって分かりづらくなった。

そんな経験、ありませんか？

ありますよね。

そう、あるんです。

こんなとき、真面目な人はムキになって、今のやり方をもっと頑張ろうとしてしまいがちなのですが、それはかえって悪手なこともあります。癖がつくとか、そもそもやり方が間違っていたとかです。
　
・こんなときは、落ち着いてください。
ゆっくり落ち着いて、まずは深呼吸をするなどしましょう。
そのあと、今とは別のやり方を試してみましょう。
別のやり方を考えるコツは、そうですねぇ…、問題に目を向ける、簡単なやり方から試す…とかですか。
ここら辺色々分かっていると良いですが。

・あるいは、外に出て散歩してみる、お風呂に入るのも手です。

リラックスできます。

・他人に意見を求めるのもアリです。
自分には見えなかったものがあっさり見えます。

・目的と関係ないことでも、遊び心は消さずに、膨らませましょう。
半分ふざけた意見が重要なアイデアになることもあります。
　
・楽をしてみましょう。
楽をする、というと「怠惰」なイメージがつきものですが、
もっと簡単にできないか、あるいは、今のやり方は「ここ」がしんどい、
と思ってみることで、「工夫」ができます。工夫チョー大事。
　
・目的に戻って考えてみましょう。
今やるべきことを「どうやったらいいか」に固執して、「なぜそれをやるか」「それをやると何が嬉しいのか」が抜けちゃうことがあります。
もしかすると、もっと良い手段があるかもしれない。これは本当に重要なのか？
たまに目的に立ち戻って、根っこから考えてみましょう。
　
・たまに面倒くさがる
面倒くさいから「やめておこう」「今考えるのはやめよう」
これを「常に」やっていると、ただの怠け者ですが、たまに実行してみることは大事です。思考の枝刈りになります。
何かをやること以上に、何かをやらない判断は大事。
見通しの悪いやり方はどんどん切っていきましょう。
　
・一番大事なことは何かを念頭に置く、要約を意識する
真面目な人間、あるいは、よく知っている人ほど「何でもかんでも」言いたくなります。しかし、それでは人に伝わりません。

自分でさえ、何が重要な話なのか分かりません。
これが「指示」だった場合、全部は無茶だよ～ってなって、よく分からない方向に行ってしまうこともあります。
船頭多くして船山に上る、ですね。
　
沢山のことを言えるというのは素晴らしいことですが、一番大事なことは何なのかを意識しましょう。部屋が散らかっていては見栄えが良くないのと同様、主張が散らかっていては頭も冴えません。この記事も、だいぶ散らかっていますが（ア
　
執着しすぎない
　一つのやり方に執着するのは、精神的にも、局所解に陥るという点でも、一般に良くないです。

深く追求できることが強みな方にありがちですが、たまに幅を利かせましょう。
　
頭が冴える行動を取る
運動をする、早く寝てみる、お風呂に入る、など

JOI本選2018

JOI本選2018(オープン)

参加しました。252点でした。3問目の全探索が通らず。
備忘録のため、コードを貼ります。

1問目

問題：1次元上に$N$個の点が与えられます。$K$個の区間で, 全ての点を覆います。「各区間のmax - min」の和を最小化してください。(最小値 + Kを出力します)
解法：$K=1$の答えからいくつ減らせるかを考えます. これは「隣接する2点の距離」を大きい方から$K-1$個取ったときの和と同じです。$O(NlogN)$

#include 
#include 
#include 
using namespace std;

int n, k;
int t[100000];
int kt[100000];

int main() {
	int i;
	
	cin >> n >> k;
	for (i = 0; i < n; i++) cin >> t[i];
	
	for (i = 0; i < n - 1; i++) {
		kt[i] = t[i + 1] - t[i];
	}
	sort(kt, kt + n - 1, greater());
	
	int ans = t[n - 1] - t[0];
	for (i = 0; i < k - 1; i++) {
		ans -= kt[i];
	}
	ans += k;
	cout << ans << endl;
	return 0;
}

2問目

問題：大きさと価値がある商品がN個あります。いくつか選んで、価値の和 - (大きさの最大値 - 大きさの最小値)を最大化してください。
解法：
・$O(N^3)$：大きさの最大値と最小値の組み合わせは$O(N^2)$あります。これを固定すると、取ることができる商品が定まります。
・$O(N^2)$：商品を大きさ昇順でソートしておくと、取ることができる商品は一つの区間で表せます。よって、価値の累積和を用いると、先ほどの解法が$O(N^2)$に落ちます。
・$O(NlogN)$：上記の解法を改善します。商品L～Rを取る場合のスコアf(L, R)は、g(L) + h(R)の形に変形できるので、Rを動かしながらg(L)の最大値を求める感じでできます。

#include 
#include 
#include 
#define int long long
using namespace std;
typedef pair<int, int> P;

int n;
P p[500000];
int a[500000], b[500000];
int rb[500001];
int fl[500001];	//fl[l] = a[l] - rb[l]
int fr[500001];	//fr[r] = rb[r + 1] - a[r]
				//fr[r] + fl[l] = 区間[l, r]を選んだときのスコア

signed main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
	sort(p, p + n);
	for (i = 0; i < n; i++) { a[i] = p[i].first; b[i] = p[i].second; }
	for (i = 1; i <= n; i++) { rb[i] = rb[i - 1] + b[i - 1]; }
	for (i = 0; i < n; i++) fl[i] = a[i] - rb[i];
	for (i = 0; i < n; i++) fr[i] = rb[i + 1] - a[i];
	
	int maxL = fl[0];
	int ans = -1;
	for (i = 0; i < n; i++) {
		maxL = max(maxL, fl[i]);
		ans = max(ans, fr[i] + maxL);
	}
	cout << ans << endl;
	return 0;
}

3問目

一言：これはリーディングハードです。誤読しなかった方はプロですね。
問題(間違いの可能性があります)：
n行m列のR,G,Bからなる文字列が与えられます。連続する3行または3列を, 互いに重ならないように, かつ上または右から読んだときに"RGB"の順になるように取ります。最大で何組取れるでしょうか。
解法(n,m≦4)：取り方を全探索します。なぜか通りませんでした(0点) . 残念.
解法以前の問題ですね。全探索の練習をしてきます。

//縦3マス, または, 横3マスでペアを作る
//上から読んだとき or 左から読んだときに、"RGW"になっているペアの個数を最大化せよ -> ではなくて、"RGW"の順で刺さないとダメらしい。
//という問題。ペアが交差したらNG, 内側から刺してもOKな点に注意.（この誤読で1時間以上溶かした）
#include 
#include 
#include 
#include 
using namespace std;

int h, w;
string s[10];

int dfs(int used) {
	int r, c, res, ret = 0;
	
	for (r = 0; r < h; r++) {
		for (c = 0; c + 2 < w; c++) { 
			if ((used >> (r * w + c)) % 8) continue;
			if (s[r][c] != 'R' || s[r][c + 1] != 'G' || s[r][c + 2] != 'W') continue;
			res = dfs(used + (7 << (r * w + c)));
			ret = max(res + 1, ret);
		}
	}
	
	for (c = 0; c < w; c++) {
		for (r = 0; r + 2 < h; r++) {
			if ((used >> (r * w + c)) & 1) continue;
			if ((used >> ((r + 1) * w + c)) & 1) continue;
			if ((used >> ((r + 2) * w + c)) & 1) continue;
			if (s[r][c] != 'R' || s[r + 1][c] != 'G' || s[r + 2][c] != 'W') continue;
			res = dfs(used + (1 << (r * w + c)) + (1 << ((r + 1) * w + c)) + (1 << ((r + 2) * w + c)));
			ret = max(res + 1, ret);
		}
	}
	return ret;
}

int main() {
	int i;
	cin >> h >> w;
//	if (h > 4 || w > 4) return 0;
	for (i = 0; i < h; i++) cin >> s[i];
	cout << dfs(0) << endl;
	return 0;
}

4問目

問題：N頂点M辺の連結で自己ループや多重辺がない無向グラフが与えられます. $S$->$T$最短路を一つ選び, 経路上の辺のコストを全て0にできるとき, $U$->$V$最短路の長さの最小値を求めてください.
解法(S = U)：S = Uの場合, S->V->TがS->Tの最短経路の一つであれば0, そうでなければS->Vの距離が答えです。
解法(M = N - 1)：S->T間の最短路が1通りなので, S->T最短路に含まれる辺のコストを0にして, U->V最短路を求めればよいです。
自分の解法(31点)：S->T最短路に使われうる辺の集合について, 辺のコストを0にし, U->V最短路を求めました。嘘解法なので、満点は取れません。

//S->T最短経路に使われうる辺をコスト0に置き換えたのち, U->V最短路を求める.
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
typedef pair<int, int> P;

int INF = 1e+15;
int n, m, s, t, u, v;
int a[200000], b[200000], c[200000];
vector et[100000];
vector ec[100000];
int minCost[3][100000];

priority_queue<P, vector, greater

> que; void dijkstra(int minCost[], int start) { int i; for (i = 0; i < n; i++) minCost[i] = INF; que.push(P(0, start)); minCost[start] = 0; while (!que.empty()) { P now = que.top(); que.pop(); int cst = now.first; int pos = now.second; for (i = 0; i < et[pos].size(); i++) { int npos = et[pos][i]; int ncst = cst + ec[pos][i]; if (minCost[npos] > ncst) { minCost[npos] = ncst; que.push(P(ncst, npos)); } } } } signed main() { int i; cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--; for (i = 0; i < m; i++) { cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--; et[a[i]].push_back(b[i]); et[b[i]].push_back(a[i]); ec[a[i]].push_back(c[i]); ec[b[i]].push_back(c[i]); } dijkstra(minCost[0], s); dijkstra(minCost[1], t); for (i = 0; i < m; i++) { if (minCost[0][a[i]] + c[i] + minCost[1][b[i]] == minCost[0][t]) { c[i] = 0; } else if (minCost[0][b[i]] + c[i] + minCost[1][a[i]] == minCost[0][t]) { c[i] = 0; } } for (i = 0; i < n; i++) { ec[i].clear(); } for (i = 0; i < m; i++) { ec[a[i]].push_back(c[i]); ec[b[i]].push_back(c[i]); } dijkstra(minCost[2], u); cout << minCost[2][v] << endl; return 0; }

5問目

問題：長さ2^Lの配列と, Q個の質問が与えられます. 各質問では0,1,?を用いて該当する要素の番号を指定しています. 該当する要素の和を各質問について答えてください.
制約：L≦20 , Q ≦ 10^6
解法(22点)：
「先頭が0の質問, 1の質問, ?の質問」を順に処理することを考えると、?の質問以降では、配列を真ん中で分けて前半i番目と後半i番目を足したものをi番目の要素とした配列に縮約して処理できることが分かります.
よって、これを再帰的に実装します。（計算量は$O(3^L + QL)$くらい）
75点狙えると思いきや、意外とメモリ計算量が多いらしく、通せませんでした。

#include 
#include 
#include 
#include 
using namespace std;
typedef pair<string, int> P;

int l, q;
string s;
vector pre;

void dfs(int cnt, vector v) {
	if (cnt == 0) {
		//cout << v[0] << endl;
		pre.push_back(v[0]);
		return;
	}
	
	int i;
	
	//0
	vector nv;
	for (i = 0; i < v.size() / 2; i++) {
		nv.push_back(v[i]);
	}
	dfs(cnt - 1, nv);
	nv.clear();
	
	//1
	for (i = v.size() / 2; i < v.size(); i++) {
		nv.push_back(v[i]);
	}
	dfs(cnt - 1, nv);
	nv.clear();
	
	//?
	for (i = 0; i < v.size() / 2; i++) {
		nv.push_back(v[i] + v[i + v.size() / 2]);
	}
	dfs(cnt - 1, nv);
	nv.clear();
}

int getId(string query) {
	int i, ret = 0;
	for (i = 0; i < query.size(); i++) {
		ret *= 3;
		
		int val;
		if (query[i] == '0') val = 0;
		else if (query[i] == '1') val = 1;
		else val = 2;
		ret += val;
	}
	return ret;
}

int main() {
	int i;
	
	cin >> l >> q;
	cin >> s;
	
	vector v;
	for (i = 0; i < (1 << l); i++) v.push_back(s[i] - '0');
	dfs(l, v);
	
	for (i = 0; i < q; i++) {
		string query;
		cin >> query;
		cout << pre[getId(query)] << endl;
	}
	return 0;
} 

感想

3問目で嵌ってしまいました. 全探索は書けるようにしたいですね.
最近は, 些細なミス（誤読、変数名間違えなど）が目立っているので, 注意力を鍛えたい.

AOJ 1169. 最強の呪文

問題文

問題文

考えたこと(箇条書き)

start --(S1, S2) --> v --T--> goalと行く場合を考える（vは注目した1頂点. S1,S2,Tは文字列）。
まず、S1 < S2 ⇒ S1 + T < S2 + Tは偽なので、各頂点で辞書順最小を作る方法では「最強の呪文」を作ることができない。（反例：S1 = "a", S2 = "ab", T = "c")
しかし|S1| = |S2|なら上の命題が真になるので、dp[文字数][頂点] = 辞書順最小とすることができる。（今いる頂点と文字数が同じなら, 辞書順最小が良い。）
よって、このDPをする。

最強の呪文が定まる場合、最強の呪文がなす経路はパス（同じ頂点を2度通らない）になることが示せる。(1つのサイクルを含む場合について証明すればよい）
よって, 最強の呪文（dp[--][goal]）がサイクルを1つ以上含んでしまった時点で"NO"が確定する。
サイクルを1つ以上含むことで, パスの場合よりも強い呪文を作れるとすると、同じサイクルをn個含む「パスの場合よりも強い呪文」が任意の正整数nについて存在する。すなわち、
パスの場合よりも強い呪文が存在する ⇔ 経路長n未満の場合よりも強い, 経路長n以上2n以下の呪文が存在する
が成り立つ。よって、経路長2n以下まで, すなわち文字数12n以下まで調べれば十分である。
(もう少し考えると、パスの場合よりも強い呪文が存在する ⇔ 文字数6n未満の場合よりも強い, 文字数6n以上12n以下の呪文が存在する. も成り立つことが分かる)

はまった点

・dp[頂点] = 辞書順最小, を立てようとして嵌った。
・dp[枝を通った回数][頂点][長さ] = 辞書順最小, としてMLEした。
・dp[今までの文字数][今いる頂点] = 辞書順最小, としたが, 長さ昇順にループを回さないせいでTLEした。
・文字数 ≦ 6 * nまでしか考えていなくて、WAした。

…考察を詰める集中力がほしい。

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, s, g;
vector<int> et[40];
vector<string> ec[40];
string dp[481][40];

int main() {
    int i, j, k;
    
    while (cin >> n >> m >> s >> g) {
        if (!n) break;
        for (i = 0; i < n; i++) { et[i].clear(); ec[i].clear(); }
        for (i = 0; i <= 12 * n; i++) { for (j = 0; j < n; j++) { dp[i][j] = "{"; } }
        for (i = 0; i < m; i++) {
            int a, b; string spell;
            cin >> a >> b >> spell;
            et[a].push_back(b);
            ec[a].push_back(spell);
        }
        
        dp[0][s] = "";
        for (i = 0; i < 12 * n; i++) {
            for (j = 0; j < n; j++) {
                for (k = 0; k < et[j].size(); k++) {
                    int v = et[j][k];
                    int len = ec[j][k].length();
                    if (i + len > 12 * n) continue;
                    dp[i + len][v] = min(dp[i + len][v], dp[i][j] + ec[j][k]);
                }
            }
        }
        
        int id = 0;
        for (i = 1; i <= 12 * n; i++) {
            if (dp[id][g] > dp[i][g]) id = i;
        }
        if (id >= 6 * n || dp[id][g] == "{") { cout << "NO" << endl; }
        else { cout << dp[id][g] << endl; }
    }
    return 0;
}

感想

複雑な問題設定だと思っていたが、いざ実装してみるととても簡潔に書けたので、良問だなあと思った。
発想というよりは、典型テク（知識, 発想・証明法）を上手く使いこなす系の問題な印象。

AOJ 2708 ABC Gene

問題概要

文字列sについて, 以下の置き換え操作ができる。

• ‘A’ -> “ABC”
• ‘B’ -> “ABC”
• ‘C’ -> “ABC”

‘A’, ‘B’, ‘C'のみから構成される文字列S(|S|≦5000)が与えられるので, “ABC"を何回か操作することで文字列Sにできるか判定せよ。

解法1

逆手順を考える。
最後に操作「x -> “ABC"」をして, 文字列Sを作ったとする。（xは'A', ‘B’, ‘C'のどれか)
このとき、Sに含まれる"ABC"は、操作前は「x」になっている必要がある。

• 証明：(xを含まない文字列) -> “ABC"と変化することはない。また, x -> "ABC"と変化するので、(xを含む文字列) -> "ABC"と変化する ⇒ 変化前の文字列長 = 1が成り立つ。
• もちろん, (文字)(文字) -> 「～AB」「C～」といった変化をすることはない。また, “ABC” -> 操作 -> “ABC"と, そのままになることもあり得ない。

よって, 「x -> “ABC"」の逆元は「"ABC” -> x」となる。
（文字列Sに「x -> “ABC"」を適用したあと、「"ABC” -> x」を適用すると、文字列Sが得られる。）

あとは, xを求めればよい。実は、「"ABC"に何回か操作した文字列は必ず、'A'で始まり'C'で終わる」ことから, xは（必要条件で）一意に定まる。

具体的には、以下の場合分けにより, x(の候補)を特定できる。

1. S = “ABC～"のとき

   • “ABC"に何回か操作した文字列は必ず、'A'で始まり'C'で終わる。よって, x = ‘A'である。

2. S = “～ABC"のとき

   • 同様の理由で, x = ‘C'である。

3. それ以外

   • もしx = ‘A'またはx = 'C'のときは, 操作「x -> “ABC"」をしたときに, 先頭または末尾に"ABC"ができてしまう。これは仮定より文字列Sではないので, x = 'B'である。

ここで, 「x = ～である」という文は、正確には「x = ～である必要がある」となる。
すなわち、「"ABC" -> x -> “ABC"」をしたときに、元の文字列が得られることを確かめる必要がある。
(ちなみに, 文字列Sに現れる文字の種類数が2以下の場合は, 解が存在しない。)

あとは頑張るとO(N²)くらいになる。

解法2

「x -> “ABC"」の逆元が「"ABC” -> x」であることを求めてしまえば、あとは適当に逆再生できる。
（文字種が2種類以下⇒No, 「"ABC" -> x -> “ABC"」をしてSが得られる -> 「"ABC” -> x」をSに適用する, を繰り返すだけ）
こちらもO(N²)くらいである。ただし, 計算量の証明には解法1が用いられている。今回はこちらを実装した。

コード

#include <iostream>
#include <string>
using namespace std;

//x -> "ABC"
string operate(string s, char x) {
    string t;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == x) { t += "ABC"; }
        else { t += s[i]; }
    }
    return t;
}

//"ABC" -> x
string inverse(string &s, char x) {
    string t;
    for (int i = 0; i < s.length(); ) {
        if (i + 2 < s.length() && s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
            t += x;
            i += 3;
        }
        else {
            t += s[i];
            i++;
        }
    }
    return t;
}

//is all char appeared?
bool check(string &s) {
    int cnt[3] = {0};
    for (int i = 0; i < s.length(); i++) {
        cnt[s[i] - 'A']++;
    }
    return (cnt[0] > 0 && cnt[1] > 0 && cnt[2] > 0);
}

int main() {
    string s;
    cin >> s;
    
    while (true) {
        if (!check(s)) { break; }
        if (s == "ABC") { cout << "Yes" << endl; return 0; }
        
        char last = 'z';
        for (char x = 'A'; x <= 'C'; x++) {
            if (operate(inverse(s, x), x) == s) {
                last = x;
                break;
            }
        }
        if (last == 'z') break;
        
        s = inverse(s, last);
    }
    
    cout << "No" << endl;
    return 0;
}