AGC編です。
A - Move and Win
前に進む限りは選択肢が広がるので、どちらが先に後退し始めるかを考える
A - Digits Sum
片方が決まればもう片方は一意に決まる構造なので、片方の値を全探索する
A - Colorful Slimes 2
連続している値ごとに処理をしたいので、groupbyで要素を束ねる
A - Poisonous Cookies
毒有りで美味しいものが一番制約が厳しいつまり最大化したいが多く選びにくいので、それから貪欲にとっていくとしてシミュレーションする
いわゆる私立文系から文系総合職としてキャリアをスタート。これではいけないと思い立ち独学でコンピュータサイエンス、データサイエンスの勉強をはじめました。独学をする中で考えたことや役になったことを書いていきます。
基本的には自分が見返して価値があるかを基準に整理しているので、似たようなことに取り組んでいる人に読んでいただければと思います。
それこそ小学校の算数からやり直す勢いで勉強を継続しています。
大学レベルのCS、DSの知識を「体系的に獲得する」ための方法として、moocsを活用しています。
プログラミングの基礎文法、アルゴリズムの基本を染み込ませるために、AtCoderのコンテストに参加しています。
コロナの環境でもあり、引越しもしたことをきっかけに作業環境に凝りはじめました。
一発で本の内容をそのまま記憶できるようなタイプではないので、効率の良い勉強法自体を定期的に勉強しています。
連日深夜まで働いて勉強もして、というほど身体が強くないので、毎日健康に過ごせるための方法を勉強しています。
これだけたくさんの情報がある時代、気を抜くとすぐに簡単な消費に走るので、本来やりたいことに集中するための方法を勉強しています。
ARC編です。
A - センター採点
要素の個数が知りたいので、それぞれ文字列としてcountをかける
A - うるう年
条件が複数あるので、制約の厳しいものから先にチェックする
A - 2点間距離の最大値
調べる点の数が少ないので、全部の点の組み合わせを試す
A - 大好き高橋君
ピリオドだけが例外なので、先に消してから単語ごとに処理をする
A - 帰ってきた器物損壊！高橋君
対象の文字すべての置換なので、replaceでまとめて変える
A - たこ焼き買えるかな？
商とあまり両方とも利用したいので、divmodを活用する
A - 元気にお使い！高橋君
全て同じ消費税なので、先に本体価格の合計を求めて最後に税の処理をする
A - 名刺交換
1日の中で先に枚数チェックがあるので、繰り返しの処理の中の最初に入れる
A - 週末
曜日と日数対応の辞書を書くのがめんどくさいので、リストにしてインデクスで対応させる
B - アキレスと亀
1回あたりに亀が進むのは人間との速度比の分だけなので、試行ごとに速度比分距離が縮む（もしくは開く）
A - Celsius と Fahrenheit
計算式が与えられているので、当てはめて処理する
A - クイズゲーム
正解以外ならどんな値でも良いので、1つに値を固定して考える
A - BMI
単位を揃えるために、cmをmにしてから計算する
A - 石を滑らせるゲーム
原点からの距離が論点なので、絶対値をとって比較する
A - DEAD END
例外なく4方向の判定がしたいので、盤面の外側にダミーを入れて4方向全て確認する
A - 経過日数
ガウス記号がある割り算なので、整数除算で式を表現する
A - ダイナミックなポーズ
b<aが確定しているので、最小化のためには小さいbから貪欲に使う
A - 門限
単位が時と分二つあるので、現在の分をどちらに入れて処理するかを決めて計算する
A - 名前
文字列を裏返したいので、[::-1]を活用する
A - 隠れた言葉
n文字は1つn-1文字は2つと数えられるので、1~nまでの総和を出す
A - 高橋くんと回文
の時は相手がなんでもよいので、反転させた文字列と比較してどちらかがか同じならokとする
A - ぐっすり
３日間の合計が知りたいので、3日目から以前3日間の合計を取っていく
A - カードと兄妹
最大値からとっていくのが最善手なので、ソートして大きい方から1つ飛ばしにとる
A - 床塗り
フィールド全体の文字の個数が知りたいので、1つの文字列に連結して処理をする
A - コインの反転
できるだけ表はそのままにしたいので、裏から順番に裏返す
A - タブの開きすぎ
タブの数に応じて対応が変わるので、タブの数を変数保存しつつシミュレーションする
A - 階段の下
1の一つ下が-1なので、通常の整数計算にならすために負の値は+1する
A - "強調"
元の文字列を変更するとインデクスがずれるので、別で解答文字列を作りそこに格納していく
A - 大文字と小文字
大文字小文字を揃えたいのでlowerで調整する
A - 数え上げ
同じ数を何度もかけるので、累乗を使う
ABCのような統一された名前ではない、企業コンなどです。
A - Accepted...?
要素の個数が知りたいので、文字列として扱ってカウントする
A - Measure
長さ次第で処理が異なるので、lenで長さを調べる
B - Exchange
高々100回のシミュレーションなので、実際に操作をする
A - On the Way
abどちらが大きいケースもあるので、両方判定条件に入れる
B - e e *ee *e
1文字ごとの判定が必要なので、1文字単位でループを回す
A - 算盤の書
今月増えるのは2ヶ月前に生まれていた個体数分なので、フィボナッチ数列を作る
A - 与えられた数より小さい素数の個数について
素数の列挙をしたいので、エラトステネスのふるいを使う
A - 天下一株式会社採用情報
ループを止めるタイミングが判定で処理できるので、whileで記述する
B - 天下一難易度設定
行ごとの合計値が独立しているので、都合合計を出して判定をする
A - 天下一人力比較
複数行にわたる文字列を一気に入力してリスト化したいので、３連引用符を使う
A - Subscribers
積集合の範囲を考えるので、極端な内包関係と、離れている場合とを考える
B - Touitsu
先頭からの文字数が同じ要素同士を比べたいので、zipでまとめてループにかける
B - とても長い文字列
文字aの長さごとに最初に戻るので、bを文字列の長さで割ったあまり分で考える
B - 暗算ゲーム
1桁飛ばしに数字を扱いたいので、文字列として保有しスライスのステップ幅で調整する
A - CODEFESTIVAL 2016
文字列を分割するので、スライスを利用する
A - CF
文字が複数ある可能性があるので、Fをrfindで検索し、一番右側で確認する
A - Where's Snuke?
行方向と列方向両方チェックが必要なので、行をループさせて列をメソッドで探索する
A - Snuke's favorite YAKINIKU
接頭辞を判定したいので、startswithを使う
A - XXFESTIVAL
最後の文字列だけを切り取りたいので、replaceではなくスライスで対応する
A - Can you get AC?
特定の文字列が含まれるかが知りたいので、inで探索する
A - 掛け算の筆算
論点は値ではなく桁数なので、文字列として扱って長さを調べる
B - Indeedなう！
アナグラムが作れるかどうかは結局同じ文字が同じ回数あるかが論点なので、ソートして一致を確かめる。
A - 高橋くんとマンハッタン
軸ごとに差分を取ると曲がるところの１カ所分余るので、最後に+1で調整をする
A - Hitachi String
hi以外にないは言い換えるとhiを全て取り除くと空文字になることなので、全てのhiをreplaceして判定する
B - Nice Shopping
結局割引を使うか使わないかの2通りなので、最初に使わない場合の最小値を求めて基準にする
A - ドーナツの体積
計算式が与えられているので、それに沿って式を立てる
A - Sum of Interior Angles
多角形の内角の和は公式があるので、当てはめて記述する
B - Sumo
可能性が論点なので、残りの試合数は全部勝ちとして計算する
A - Takahashi Calendar
月と日がわかれば判定ができるので、可能性を全探索する
回転させることはできないので、縦横それぞれで大きさを比較する
A - Bulletin Board
縦横は独立して位置を考えられるので、それぞれ計算して組み合わせをかける
B - Contests
それぞれの種類1つ必要なので、種類別で最も数が少ないものを求める
B - An Odd Problem
配列のうち奇数番目だけが判定対象なので、スライスを使って判定箇所を奇数番目に絞る
A - Sum of Two Integers
ペアを作った時の最後の残りが偶奇で違うので、偶奇で場合わけして求める
A - Consecutive Integers
何回横にずらせるかを考えるので、1にn-k個を加える
A - Ball Distribution
一人の時だけ差をつけられないので、例外で差を0にする
A - Beginning
アナグラムと同じで要素が一致していれば作れるので、ソートをして一致の判定をする
A - 12/22
桁ごとにカウントがしたいので、文字列として操作する
A - Falling Asleep
指定された場所以降の合計を出したいので、フラグ管理をして対象箇所のみ足しあげる
A - Study Scheduling
時と分で単位がわかれているところを分での時間差に直したいので、分単位で0時から何分経ったかを考える
B - Postdocs
Dは単体で1つとしてカウントできるので、前後によらず?を全てDに変える方針にして損をしないと判断する
A - DDCC Finals
一位の時だけ加点があるので、その条件の時だけは個別で判定を入れる
A - Regular Triangle
正三角形の条件は３辺の長さが同じであることなので、同値かどうかをチェックする
B - Red or Blue
要素が2種類なので、片方の数をカウントして半数以上かを判定する
A - November 30
月末は言い換えると次の日が翌月の日なので、月が異なっているかを判定する
A - F
条件が3つに分かれるので、elifの構造を使う
B - Acrostic
n文字飛ばしで文字列から抽出したいので、スライスのステップ幅を使う
A - サイコロ
足して7になるので、7から入力値をひく
A - CODE FESTIVAL 2015
文字列の置き換えが必要なので、replaceを使う
A - ダブル文字列
入力に同じ種類がないことは確定しているので、文字列を2倍する
A - MUJIN
右側の方が選択肢が少ないので、右側以外は左側と判定する
A - あるピアニスト
大きい方を出力するので、maxを使う
A - Anti-Adjacency
少なくともk個作れるかなので、最大どれだけ作れるかのみ比較すれば良い
A - HAGIXILE
文字列の置換なので、replaceを使う
A - 立方数
立方数は急激に大きくなるので、全探索して調べ上げる
B - Tag
最適に動くケースなので、子供が離れる方向に動くとしてt秒間でどれだけ縮められるかを考える
ABC編です。
A - 積雪深差
差なので、値の引き算をする
A - AtCoder社の給料
1からnまでの合計がわかれば良いので、公式どおり足しあげる
A - 流行
2倍なので、掛け算を使う
A - おいしいたこ焼きの作り方
足りない部分は作れないので、整数除算を使う
B - おいしいたこ焼きの食べ方
一番0に近い数字なので、最小値を取る
A - 世界のFizzBuzz
条件が和集合なので、orで和をとる
B - トリボナッチ数列
漸化式をコードに落としたいので、前の結果をメモしながら値を大きくしていく
A - 植木算
要素数に対して要素間の個数は1少ないので、引く
B - 辞書式順序
小さい文字を1つ出力すれば良いので、'a'のケースだけ考える。
A - アルバム
離散値なので、右端-（左端-1）の-1をつける
A - 引越し作業
あまりがあってはいけないので、+1を先にしておく
B - 心配性な富豪、ファミリーレストランに行く。
要素ごとの個数は無視したいので、集合を使って要素を整理する
A - ハンドルネーム
末尾に文字列を足すので、文字列の足し算をする
B - 花占い
値によって加算する量が異なるので、条件にあるまでループを回しデクリメントを続ける
A - 来月は何月？
12の時だけ動作が違うので、条件分岐を使う
B - 名前の確認
先頭だけ大文字なので、capitalizeをする
A - スワップ
数字を同時に複数個入力するので、splitでスペースの分割を行う
B - 入浴時間
単位の大きい方から決まるので、602、60で順に割って時間分秒の順に求める
A - A
文字列の順番が知りたいので、ordを使う
B - 錠
どちらにしても増やすのと減らすの2通りなので、両方試す
A - けんしょう先生のお菓子配り
あまりがない時だけ別処理なので、条件分岐を使う
A - 高橋くんの研修
長さが知りたいので、lenを使う
B - 高橋くんの集計
分母にゼロを含められないので、ゼロのカウントをとり個数からひく
A - 12月6日
割り切れるかどうかが知りたいので、あまりが0になるかをチェックする
B - A±B Problem
+-それぞれの整合性チェックが必要なので、条件分岐をネストさせる
A - プロコン
同じ処理を何度も行いたいので、繰り返しを使う
A - 高橋くんと年齢
要素ごとに扱うと比較が何度も走るので、リストとして扱ってソートする
A - クイズ
入力によって処理が変わるので、条件分岐を使う
B - 足し算
連結は文字列としての操作なので、先に文字列として連結した後に整数にもどす
A - 足し算
同じ数を何回でも使えるので、1をn回使う
B - 嘘つきの高橋くん
同じところを2回通ったかが知りたいので、配列と集合の差をとる
A - Best Body
体重が変化するので、毎回体重を更新して判定をする
A - 加算王
桁ごとの和を取りたいので、文字列として扱ってそれぞれ足す
A - 動物園
K人を超えているかが論点なので、合計人数で条件分岐させる
B - 自動ドア
毎回ドアの開く時間はリセットされるので、要素ごとに次までの時間との比較をする
B - 双子とスイカ割り
方角の情報を持ちたいので、東西をプラスマイナスと対応させる
A - 掛け算の最大値
面積が最大になる組み合わせを出力したいので、正方形を考える
A - 長方形
1つしかないものを選択したいので、リストとして受け取って要素のカウントをする
A - テスト評価
分岐が3つ以上になるので、elifを活用する
B - 文字数カウント
文字列の長さが高々100なので、すべての文字をカウントする
A - 複数形
末尾に文字を足したいので、文字列の足し算をする
B - カキ
個別に含まれているかのチェックをしたいので、ループを回す
A - 勝率計算
小数は誤差が怖いので、積の形に直して判定をする
A - ゲーム
条件が分かれるので、条件分岐を使用する
B - 運動管理
条件が複数になるので、elifを活用する
A - 高橋君と青木君の好きな数
どちらでも割り切れる数なので、最小公倍数を最小単位として考える
A - 暗証番号
論点が種類数なので、各桁を集合にして扱う
C - 数式の書き換え
足し算ごとに区切って判定をしたいので、+でsplitをかける
A - テスト
大小関係が知りたいので、比較を行う
B - ペア
前にいるか後ろにいるかが知りたいので、偶奇の判定をする
A - テレビ
比のままだと判定しにくいので、掛け算の形に式変形する
A - お茶
足りない状態ではいけないので、切り上げをする
A - 饅頭
種類は問わずとにかく量を増やしたいので、価格の安いものを貪欲にとる
A - お茶
文字数によらず最後の1文字が知りたいので、添字に-1を使う
B - ディスプレイ
2つの配列の共通要素があるかが知りたいので、積集合を利用する
A - 高橋直体
同じ面積が２面あるので、それぞれ求めて２倍する
B - エージェント高橋君
4乗してその数になる数が知りたいので、1/4乗をする
A - 赤赤赤赤青
前か後ろ2つの選択肢があるので、どちらも計算してminをとる
B - 直方体
あまりを出したいので、%を活用する
A - 和風いろはちゃんイージー 順番は関係なく個数のみが論点なので、必要な要素をカウントする
B - 文字列大好きいろはちゃんイージー
あえりえる組み合わせが多いので、最も小さいものを固定できないかを考える
A - キャンディーとN人の子供イージー
総和なので、整数の総和の公式を書く
B - バイナリハックイージー
末尾に対して操作をするので、スタック的なデータの持ち方、操作をする
A - 高橋君とホテルイージー
nがk以上かどうかが論点なので、そこで条件分岐をとる
B - 美しい文字列
全てに当てはまるかが論点なので、1つでも奇数であればfalse扱いにする
A - 台形
台形の面積に必要な情報が揃っているので、公式に当てはめて記述する
A - AtCoDeerくんとペンキ
種類数だけが知りたいので、集合型を使う
B - AtCoDeerくんとボール色塗り
隣の色によって選べる色が決まるので、最初に端を1つ決めることであとの選択肢は決まると考える
A - キャンディーと2人の子供
一番大きいものが他と等しいかということなので、ソートを使って計算する
B - すぬけ君の塗り絵 2 イージー
4パターンあることがややこしさを招くので、上下左右の4つに分けて変数を管理する
B - Between a and b ...
a~bの区間だと考えにくいので、~bと~a-1の区間の差を考える
A - Addition and Subtraction Easy
文字列の並びを数式として処理したいので、evalで計算する
A - Haiku
文字列に対して同じ操作を何度もするので、一度に置換できるメソッドを使用する
A - Two Rectangles
大きい方を使うので、maxを使用する
B - Increment Decrement
計算の累積が最大になる点が知りたいので、累積和をとっておいて最大値を取る
A - ABC/ARC
大小関係が知りたいので、比較を行う
A - One Card Poker
1の時だけは強いので、例外として条件に入れる
B - Training Camp
値がすぐ大きくなるのでmodは取れる時に取る
A - HonestOrDishonest
答えが2値あるので、片方になる場合だけを考えて残りはそれ以外とする
A - ι⊥l
条件が分かれているので、条件分岐を行う
B - ∵∴∵
奇数偶数で長さが異なる可能性があるので、奇数側にダミーの空文字を入れて整える
B - Comparison
条件が3つに分岐するので、elifを使う
A - Restricted
条件が2つに分岐しているので、条件分岐を使う
A - Expired?
条件が3つに分岐するので、elifを活用する
A - K-City
線の間の数が知りたいので、本数-1をする
B - i18n
文字列を分解して受け取る必要があるので、アンパックを使用する
A - Palindromic Number
数字を桁ごとに処理したいので、文字列として扱う
A - Sandglass2
正になる時のみ処理を行うので、max(0,) を使用する
B - Theater
席は離散値なので、右端-（左端-1）の-1をつける
A - Bichrome Cells
同じ数同士をかけるので、累乗の処理を使う
A - One out of Three
選択肢が3つなので、それぞれ同じ値があるかをチェックする
A - Rating Goal
問題文の逆の操作が必要なので、求めたいものを変数と見て式を整える
B - Around Square
制約の桁数が大きいので、ルートをとって全探索をする
A - HEX
文字列の大小関係が知りたいので、数字と同じように比較をする
B - ISU
端と人の個数がずれているとまとめて考えにくいので、先に端1つ分取り除く
A - Good Integer
数字を桁ごとに処理したいので、文字列として扱う
A - Round Up the Mean
切り上げが必要なので、ceilを使う
B - Two Anagrams
可能かどうかを判定したいので、操作できる最大ケースのソートをする
A - New Year
後どれだけかなので、引き算をする
B - Kagami Mochi
同じサイズのものは2つ複数使えないので、要素の種類数を求める
C - Otoshidama
O(n3)から1つ次元を落としたいので、変数2つを固定すると残り1つは自明になることを使う
B - 1 21
直接的に平方数か判定しにくいので、可能性を全探索する
A - Buying Sweets
bの塊を引けるだけ引きたいので、bで割った余りを対応させる
B - Two Colors Card Game
種類ごとの要素数の差が知りたいことなので、得する可能性のある種類を全探索する
A - Traveling Budget
電車とバスは別の問題なので、個別に独立して処理をする
A - Cats and Dogs
具体的な値はわからないので、範囲の最小と最大を考える
A - Day of Takahashi
確認した月が含まれるかが論点なので、日が月より小さいか否かで条件分岐させる
A - Colorful Transceivers
条件が2パターンあるので、論理和をとる
B - Exponential
値が極端に大きくなることで遅くなるので、探索中に条件を超えたらループを切る
A - Happy Birthday!
連続してはいけないので、差が1以下になる状況を考える
A - Task Scheduling Problem
途中で折り返して無駄な距離歩きたくないので、ソートして一直線に並べる
A - Rated for Me
条件が複数あるので、制約が厳しく先に捕捉される方から分岐させる
A - AtCoder Crackers
あまりが出るかどうかが知りたいので、あまりが0かで条件分岐をする
A - Garden
縦と横の長さがわかる状態にしたいので、使わない部分を端に寄せる
A - Maximize the Formula
大きい桁の値が和への寄与が大きいので、最も大きな位に大きな数を入れる
A - Right Triangle
整数で出力する必要があるので、制約から//で除算を行う
A - Still TBD
月が4月以前かが知りたいので、スライスで抜き出す
B - Five Dishes
整数の繰り上がりを表現したいので、10で割ったあまりで分類して作る
A - Rounding
大小関係が論点なので、比較を行う
C - Rectangle Cutting
長方形の面積を半分にしたいので、重心を通るケースを考える
A - Security
数字を桁ごとに処理したいので、文字列として扱う
C - Remainder Minimization 2019
全探索は難しいので、明らかにmodの結果がゼロになる長さでループを切る
A - Dodecagon
同じ数同士を掛けたいので、累乗を使う
B - Golden Apple
できるだけ広く監視させたいので、被りがないように長さを割る
B - Resistors in Parallel
式が一瞬ややこしく感じるので、分母部分の処理と分数全体を分けて考える
C - Alchemist
後から処理する数字の影響力が大きいので、小さい順に処理をする
A - Password
桁ごとに独立に選ぶので、重複順列を使う
A - Circle
何倍かの部分が知りたいだけなので、何倍かを変数において式を立てる
B - ROT N
文字列を辞書順で動かしたいので、辞書順の基準になるA~Zまでの文字列を用意する。
A - Strings
2つの文字を同時に複数個入力するので、splitで分割する
B - Greedy Takahashi
マイナスにはできないので、できるだけ引いたら0で止める
B - Papers, Please
全ての要素が条件を満たすかが知りたいので、条件分岐にallを使用する
A - Duplex Printing
足りない状態ではいけないので、切り上げを行う
界隈では「たくさん問題数をこなす」勉強の仕方が一大勢力だと思いますが、1回で解いて理解ができるタイプではないので、同じくらい「同じ問題を理解できるまで何度も解く」ことをしています。
特に最近は、理解度を深くする方法としてchokudaiさんも言及されていたような、問題の本質的な部分を咀嚼して人に伝えるようにする方法を試しています。何となく解けた、解けなかった境目のレベルの問題を明確に解けるようになるための訓練として有効な感じがあるので、しばらく続けてみます。
以下のリンク先には、各問題で自分が咀嚼できた上で回答が書けるものを、一行要点で「何がこの問題の難しさで、何が必要なのか」をまとめていきます。
解いた問題ではなく、完全に理解できた問題から書いていくので、進みはゆっくりかと思いますが。。
競プロの先輩方のブログにはいつも助けてもらっています。
一方で、この手のチートシートはまとめる過程自体が勉強になることが多いので、自分でも思考の整理を兼ねて整理していきます。
9時からと遅めなので、まずはよく睡眠をとっておく。当日は時間があったら精進より睡眠。
書き殴りながら整理するための用意。２次元のグラフやら数直線やらを書くのに、方眼紙があると特に考えなくても綺麗に書けるので良い。
制約も含めて、問題の意図を理解してからアプローチを考え始める
視覚化することで情報が整理できたり、そもそも自明だったりする。一度紙に落として図示する。
だいたい最初はこれ。簡単な問題ならだいたいこれなのでこの思考過程は絶対通ると固定してしまっても無駄になるよりも特になる機会の方が多いと思う。
これで直接的に解けるパターンとしては答えとしてあり得る状態が106程度まで。ただそれ以外のケースでもどこの変数を軽くしないといけないかが明確になるなど、次の方針が立てやすくなるのでどっちにしろ損にはならない。
特に、英語はa-zの26パターンしかない、格子点を全部チェックするなど、一見ややこしそうでも大して選択肢ないじゃん、となることは結構ある。
全探索の可能性を考えた後に、落とすべき計算量を考える。
O(n3)を変数1つ固定してO(n2)にする、O(n2)をO(nlogn)にする（この時点で二分探索っぽいなー）など
ソートしても問題ないものであればソート済みとして扱う。複数の文字列を1つとしてみても問題がないなら先に変換をかけてしまう、など扱いやすい形にデータを整形する。
全探索→貪欲→動的計画法の思考の流れは、基本問題の多くがこれを使うんじゃ無いかというくらい汎用性が高い。
全探索→貪欲→動的計画法の順序で書いたのは初めてだけど、これはこれで良いのよね。
— chokudai(高橋 直大)🍆 (@chokudai) February 21, 2020
全探索→動的計画法がアルゴリズム的には繋がりが良いのだけど、貪欲を挟む事で、「自明な改善が出来ないケースでDPが有効」ってストーリー性を持たせやすくなる。
よくあるのが上下左右の処理を、それぞれ上、下、左、右の4つに分けるみたいなやつ。２次元のデータを一旦1次元の配列として見るとかも。
三角形の内角の和はπ、a,bが互いに素ならax+by=1を満たす(x,y)が存在する、など問題文には書かれていないけど暗黙に条件として与えられているものがないかを考える。
n2やn3のループから1つ次元を落としたい時に使う。合計金額が分かっていて、xの金額が決まれば、残りのyの金額は探索するまでもないじゃん、ってやつ。
最終的にどうなったら終わるのかがわかると、それがそのまま最後の状態になる。
ゲーム理論のように、最終状態はそれまでの判断が全て決定しているので大体一位に判断が決まる。そこで最終的な状態から遡っていくと芋づる式で解ける場合はまあまあ多い。
一度使ったカードはまた使えるのか一度きりなのか、切り離したり連結したら端はどうなっているか、並び替えた時にインデクスはどうなっているか？など変化するところ（逆にしないところ）に注目する
桁ごとの合計や回文を作るなど、1塊の数字としてではなく、桁ごとの値を独立して扱いたい時は、文字列として扱っておくと桁を指定して処理がしやすい。
問題を解いているとテストケースがあっていれば良いという意味で、何となく解けてしまうこともある。。
一方で、再現性を持って対応ができるためには明確に指針を持って解ける状態にしておく必要がある。そのために必ず「ここが本質的に難しいポイントでここを考えると見える」って部分を捉えるまで考える。
自分の場合具体的な運用は、過去問の進捗と使ったアルゴリズムをまとめているシートに、上記部分を実際に書いてみる。
ちなみにこの考え方は、chokudaiさんも言及しています。
しいて言うなら、問題を解いた後に「この問題の肝はどこだったか？」というのをしっかり考えることは大切です。一色下の人に対して、30文字ぐらいで伝えようとしたときのヒントが、この問題の肝だと思います。
AtCoder社に行ってchokudaiさんと話したお話 - ひゅ～Menの雑記帳
解法を丸暗記してもそのまま次に出るわけではないので、何が原因で解けなかったのかを振り返る。「何らかの前提知識が足りなかった」「持っている知識が使えることに気づかなかった」「方針はたったが、何らかの実装がついてこなかった」あたりになるかな。
良い数学のテキストはアプローチの説明が丁寧
数学ガールシリーズが好きなのですが、その著者が参考にしていると聞き。何度も読み返す本です。
