t6o_o6tのAtCoder記録
分散していて逆に確認しにくいのではないか、と思い書く
振り返りが重要だが、システムで解決する方法を考えていないのでこうする
何も読まずにできる問題をやる必要はない。
できない問題はできるようになってもやる必要がある。
BはAで割り切れる = BをAで割った余りは0
code:init_var.cpp
int f() {
int ans, i;
for (i = 0; i < 5; i++) {
ans += i;
}
return ans;
}
コメント
$ 10^8までの値は intでも大丈夫だと思う
足し算、比較は問題なく行えると思う
「もし〇〇でなかったら」の脳のバグ
書きたかった処理
FizzBuzzにおいて、「ある数値に対応するのが数値でなかったら（=FizzやBuzzでないなら）」次のループに移る 実際に書いてしまったもの
code:invalid.cpp
for (i = 1; i <= N; i++) {
if (i % 3 || i % 5) continue;
total += i;
}
コメント
これでは、3や5の倍数でないときを弾いてしまう
3や5の倍数でないときに処理したいのに
このレベルが難しいラインっぽい
✅ 解説AC
解説ACが、最も個人の経験をよく表すのではないか。
解説なしACは、元々解けていた可能性がある
解説あってもACできなけれれば、レベルが高すぎた
解説ACは、本人が一定の知識を学び取った証である
難しかったポイント
AtCoderでは、しばしば入力値が1始まりで、そのまま配列のインデックスに使ってはならない データ構造
スマートにいくケースがある
%06dで6桁でゼロ埋めできた
string()
難しい問題来た
✅ 解説なしAC
自分で問題点を探せたから解説なしでAC
ただ何回かテストした
ミスした点
部分文字列の書き方は？
今回は、s.length() - 3 文字分であることを、例を用いて確かめた
ABCDEFG → CDEF（7 - 3 = 4）
Cが部分文字列に1個だけ存在する
楽しく書けた
しかしバグはあった
1. 文字列長が同じであることを示す
2. 先頭から順番に、文字が同じであることをたしかめる
命名は大文字より小文字
命名は短いほうが読みやすい
難しいロジックを書く場合には、命名が長いほうが良いのかもしれないが
競技プログラミングは、（現時点では）長くて100行という感じ
読みにくければ関数に切り出すだけであり、変数名を短く保ったほうが読み書きしやすい
分からなかった
非負整数 a, b, c をどこまで探索して良いのかが
だが、これはsを条件に指定するだけでうまくいく
熟練者は勘と計算量で分かるが、今はまだ分かっていないはず
後から最適化していく方が良い
t を条件に使ってはいけない理由
a, b, c のいずれかが 0 のとき、必ず積が0になってしまい、本来探索されるべきだった組み合わせも打ち切ってしまうから。
ちょっとムズカシイ
考えさせられた
Tに対してすべての文字を検証しなければならないというのがポイント
✅解説AC
[0][2]、[1][1]、[2][0]などとなっていて気づいた
[2 - x][2 - x]ではなく[x][2 - x]だ
rowは単純に増やせばよいが、columnは右から左へ減らしていく必要がある
盲点
一番消耗した
AtCoderは必ず1始まりの値を入力してくるので、添字として取り扱ってはならない
この場合も、AtCoderの入力値を添字に使ってはならない。
怖いので 1 引くのをくせにしたい。
H、W、X、Yという4つの入力は、Hが高さ、Wが幅で、Xは横の座標、Yは縦の座標だと思っていた ーーー
違った
Xが縦の座標（1次元目）で、Yは横の座標（2次元目）という関係だった
今まで書いてきたものが全くおかしかったことがわかった
解説なしAC... だけど、学び（？）の多かった時間だった
本当の学びとは、学び（？）なのかもしれない
自分の中で学びと呼ぶには少しモヤッとするもの
この記事の内容を忠実に実行するというのが重要
自分は、VSCodeが補完してきた launch.json の値を使って失敗していた
gdb(起動)というタスク
記事の内容を元にやり直したら上手く行ったという経緯
解説なしAC
もう、B問題とか関係ない
良い問題は、番号に関係なく良い問題である
盤面系の問題は全体的に体力を使う
ただ、今後も様々な問題を解いたら、安定させられそうである
初級編をとりあえず終わる
解説AC.icon
問題認識❌
❌N枚以下でY円になる組み合わせ
◯ N枚でちょうどY円になる組み合わせ
文章を正しく読めるのが前提になっている
今の強化ポイントはそこ
3重ループだと間に合わないけど
N枚ちょうどなら、3種のうち1種の枚数は一意に定まるよね、というのを
覚えていた...
悪いことではない、学んだということ
解説なしAC / 解説を読んでなるほど
解説
初めに書いたコードは、bとp、2つの変数でループし、powで累乗を計算していた
現在の値に、底を掛けて、ついでに他の処理も行うようにすると良い
解説なしAC
いまいちWAが腑に落ちない
code:ac.cpp
if (z < 0 || k < z)
continue;
breakしてはいけない理由は何か？
k < zを考慮する必要があるのはなぜか？
z = 15となるパターンがあった
理由
$ z = s-x-y から、$ z\le3kが導かれた
解説なしAC
昨日の解説と今日の典型問題です。標準的な難易度となっています。（入力形式・入出力例は GitHub を参照のこと）
なお、解説の都合上、本日に限り Python の想定解も GitHub に掲載しております。 #競プロ典型90問 https://pbs.twimg.com/media/E21MVj5VEAEVr3l.jpghttps://pbs.twimg.com/media/E21MXDmUcAEnTjK.jpg
計算量が、$ O(N^5)と大きくても、定数倍を見積もることで間に合う解答であると判断できるのは盲点だった。 解説AC✅
そのかわり、デバッグ機能を上手く設定できたので楽になった
解説なしAC
ここまで同じような問題を解いて、典型が「視えた」
解説なしAC
テストケースに不備があるのではないか
$ A_iの範囲は本来 int だとオーバーフローする
今回は、オーバーフローした際の数値が重複するテストケースがなかったと思われる
int で入力値を取ったり、mapのキーにしても通ってしまった
解説なしAC
Poll
教育的
キーが文字列なら辞書順になっているということ
解説ありAC
とても時間がかかった
Difficulty 680
AtCoder茶に相当？
当たった問題
削除したいキーのリストを作って、イテレーションが終わったあとにeraseした
方針は途中で無理なく立った
実装力が少し付いた気がする。良かった
大量の問題をいきなりすべて覚える必要はない
できるなら、やったほうがよいが
問題カテゴリへの入り口が明示されている
入り口の内容を熟読して、段階的に慣れていくことが可能
ただ無作為に並べられたAtCoderの問題ではこれはできない
Qiitaの記事も「段階的」に出来なかった
ブラウザだとすべてが視えてしまう
ゲームのように、「これが出来たら次のステージ」が出来たら良かったのか
でもある程度自由度も欲しいかな？
自然に、一つの点に集中できる感じが欲しい
ABC315 C
感想
今回は美味しさを最大にしたいのだからまずはソートすることを考える。
Nの大きさから$ N^2のアルゴリズムは書けない。
味の相違によって美味しさの値が異なりうるから、2つのパターンで両方探索する
味が同じパターン
味が異なるパターン
感想の感想
当たり前のものは存在しない
自分にとって当たり前のことが、当たり前ではない
当たり前だと思えなかった人に、どう伝えればいいのか考える
〇〇するだけの問題、みたいな言い方はかなりNGに感じる
比べれば良いというものではない
したいというのを常に大切に
理詰めになるのは悪い兆候
思い詰めていないか
視野狭窄
対面コミュニケーションの重要性
入力もなるべくすぐにしたほうが良い
code:NG.cpp
using namespace std;
int main(void) {
int N = 0;
vector<int> l(N);
cin >> N;
}
code:NG.cpp
// いぇーい
vectorの要素数は N + 1
for文でイテレーションする場合、1 ～ N + 1になる
<= Nでも可
解説AC
AC自体は解説なしでも出来たが、実装が間違っていた
この実装を弾くケースはなかったのかな
解説AC
削除した行と削除した列の情報があれば直に探索してOK
この発想は、計算量を計算しているから出てくる
t6o_o6t.iconは、行や列を除いた新しいvectorを作ったほうが探索回数が減って良いのではないか？と思っていた
それは計算量的に必要ない
管理する必要のある情報
行、列に含まれる色の数
書けなかった部分
「行の中に、1種類しか色が存在しない」条件の表現
これは言い換えると、「行の長さと色の出現回数が等しい」
行を削除したら、各列における、その行の色の出現回数を1個減らす
削除対象行と、削除対象の色は1対1である
なぜならその行には1個しか色がないことが分かっているから
1対1なので、pairで保存するのが速い
実際に削除処理をするときに、色情報を使って出現回数を減算すれば良い
解説AC
substrが示す範囲
$ \mathrm{substr}(i, j)は、[i], [i + 1], ..., [i + j - 1]と考えると良い。
例
substr(3, 4)は、[3, 4, 5, 6]
ただし、アクセス範囲が文字列長を超えた場合にはその時点でアクセスを打ち切ってくれる。
この考え方のもと、substrの引数を修正したところ文字列の分割はうまく出来た。
isupper(s[i + j]) == trueを満たすi、jについて、substr(i, j)としていた。
しかし、大文字の部分を含めて切り取りたかった
これだとi + j - 1（大文字の1個前）までしか切り出せない
substr(i, j + 1)に修正した
これなら i + j（大文字）まで切り出してくれる
書けなかった部分
大文字を小文字に変換するには？
今回は特殊で、各文字列の先頭と末尾のみが大文字であることが保証できる
先頭と末尾のみを小文字に変換してソートし、出力時には先頭と末尾のみを大文字にすれば良い
解説なしAC
最初に1匹のスライムがいて、2匹目から見ていったときに、1つ前のスライムと異なったらカウントを増やす
なのでカウントの初期値は1
ABC139 C
正しいと思う
問題が間違っていると思うほどに、自分の実装に誤っている点が見つからない。なのに正しく動かない
このような考えにいたったときは、おそらく認識できていない挙動が存在する
デバッグ機能は悪ではないと思う
原因を考察するという目的の上では、悪ではない
ただ、改善を加えなければいつまでもデバッグ機能を使わないといけなくて、非効率的だ
code:NG.cpp
for (int i = 1; i < n; i++)
{
cin >> b;
if (b <= a)
{
cnt++;
}
else
{
max_cnt = max(max_cnt, cnt);
cnt = 0;
}
a = b;
}
cout << max_cnt << endl;
この実装だと、最後までマスを移動できるような入力のとき、最後のイテレーションでmax_cntが更新されない
どうするのが良いのか？
毎回更新するように実装できるなら、そのほうが良い
今回の場合、max_cntを毎回取る実装にすれば簡単である
1回分例外的に処理を行う
カウント変数などを更新する処理の場合場合、初期値を工夫する
例
最初にスライムが1匹存在すると考えると、例外的処理が不要。
条件分岐の中で値を更新しなければならないときに、必ず「最終イテレーションで値更新処理が含まれていないケースに到達したときに値更新をする必要があるのか」を考える
例
最後の文字も出力に含めたい
最後の文字の処理では、1個前の文字と処理対象の文字が異なるかどうかに関わらず、出力したい
解説なしAC✅
mainスコープで定義したcntを加算していると思ったら、実際にはループ内で定義したcntを加算していた。
レベル0にするための水やりは必要ない
盲点だった
出力がすべて1多かった
レベル0の範囲は1つなので、その分が加算されていた
ansの初期値は1ではない
水やりの総数だから初期値は0
対して、各レベルの水やり範囲の数は、一番最初の要素を考慮すると、初期値を1にすると
一番最初の要素すら存在しないレベルは無視してよい
このことから、cntの初期値は1で、ループごとにansに足しあわせる実装が良い
AtCoder、提出にギャンブルみたいな緊張がつきまとうと良くない
比例してストレスが大きくなるから続かない
こういうときは、やめる
能動的学習から受動的学習に切り替える
治ったので再開
方針を間違えた
前に見た典型だと思って解こうとしたら違った
これ
この問題で重要なのは、<が連続する場所と>が連続する場所は独立した区間として考えられるということ
<<>なら、 << と > で区切って考えれば、0, 1, 2 と 0, -1(=1, 0) になる
この考え方が非効率的なのか？
いずれの区間も、1ずつ増減していくことに違いはないので、0, 2 1, 0
<<>
<2 >1
<<>>>>
0 1 2 - 4 3 2 1 0
0 1 4 3 2 1 0
つまり区間端の処理が重要
ある区間について、
右が閉じているなら、原則 $ \frac{n(n+1)}2
右が開いているなら、$ \frac{n(n - 1)}2
この場合、$ \frac{2×1}2 + \frac{4×5}2 = 1 + 10 = 11
<>>
この場合、3
<>>><<><<<<<>>><
0 + 3 + 1 + 0 + 10 + 3 + 1 = 18
ではない
左が閉じているなら、上記の通りか？
なんか色々違うと思う
解説を読みたいけど、理解できない
どうしてこういうふうなコードになる？
liveだから展開できない
表現の幅が増えた
意味はわかったが、これで必要十分になる理由がさっぱり分からない
保留
実装
解説のまま実装する
解説AC.icon？
解説を理解できていないACを、解説ACと呼んで良いのか？
新しい知見は見つかった
また、配列のインデックスに入力値を使ってしまった
一度は回避できた
もう1個あるとは思わなかった
多分これを回避する方法で書く必要がある
もう1個あった
今回は直接配列のインデックスに使っているわけではなかった
G[u - 1].push_back(v - 1)
解説なしAC✅
課題感の残るsolutionだった
原則0始まり。
機能別に整理するということ
受験勉強などでも同じことが言えるかもしれない
問題演習に習熟していることの要件として、各知識が機能・振る舞い別に整理されているということがあるのではないか
string.at はこういう動きをしたな → 使えばこの問題は問題なさそう（方針が立つ瞬間）
方針が立つためには、それを構成する要素を機能、振る舞いで連想検索できていなければならない 連想検索
連想して関係性を考え続けること
Scrapboxはちょっと足りないかな
脳の検索はもっと圧倒的なスピードで行われる
Linksを眺めて考えるのはこれに近いと思う
機能や振る舞い（=ページの内容）を抽象的に理解していることが条件
Scrapboxであれば、「このページはたしかああいう内容だったから、今考えている話に使えるな」という考え方ができる状態
解説なしAC✅
解説なしAC✅
同様。
解説なしAC✅
以前にも起こしたことがある。
8日前だった
1週間って意外と長い
配列に対してループを行う場合、その配列に対して要素の追加や削除をループ内で行っていないか注意深く観察する
昨日出来なかった、ABC317のCは、この問題の類題だ
一筆書き問題、といえるかな
どうやって管理すれば良いのかわからない。アイデアをください
↑ 解説ありAC？
深さ優先探索が難しい。
なぜ、次の探索先のseenがtrueだと、探索しなくても良いのだろうか..
seenは毎回コピーするのではなく、常に同じものを使うらしい
既に探索したものをseenで管理している？
なぜそれで良い？
分かった。もし、seenを、ある頂点についての
基本的な方針は、検出 → 探索
ただ、検出するたびに探索が行われてしまうと、ループに陥る可能性がある。
ある枝の探索中は、たどってきた道や検出
解説ありAC？
seenを用いたDFSは少し手が慣れてきた
普通のseenを用いたDFSの意味も分かってきた
これで通る理由が分からない
デバッガで実行してみようかな？
なぜseenをfalseにしないのか
多分、seenをfalseにすると、一度探索した道に迷い込んでしまうから
seenがtrueになっている場所は、少なくともDFSでは一度探索した場所
今回の要件では、一度探索した道に迷い込んでしまうとcntが増えて困る
なのでseenをfalseにしてはならない
結論
一度探索したことのある道（部分的）をもう一度たどるような道も探索に含めたい場合はseenをfalseにせよ。
seenをfalseにしてはならない場合
ある点からある点への到達可能性さえ知れればよい場合
例
すべての点について、到達できる点の数を知りたい。
もし一度到達した点を含む経路の情報が失われると、複数回同じ点を数えてしまう。
？
code:bad.cpp
using namespace std;
vector<pair<int, int>> paths(50);
int main(void) {
for (int i = 0; i < m; i++ ) {
int a = 0, b = 0;
cin >> a >> b;
a--;
b--;
paths.push_back({a, b});
cout << pathsi.first << " " << pathsi.second << endl; // 全部 0 0
}
return 0;
}
ChatGPTに聞いたら納得の答え
明日考える。
push_backと、要素数指定初期化は、組み合わせると想定しない動きを起こす。
たぶん基本的に初期化を優先したほうがいい。
原則初期化 or assign。push_backするときは、要素数指定を禁止する。
1日経った
要素数の制約が強い場合と弱い場合で立ち回りを変えよう
制約が強い
基本的に配列を使う
push_backが存在しないのでこの問題は根本的に回避できる
制約が弱い
vectorを使う
push_backは以下のときのみ許可する
グラフの辺情報を格納
解説なしAC
自分で書けてとてもうれしい！！
自分で考えて、解けると、良い問題であったと感じる
考えるのを諦めて、問題のヒントを読むと、だいたい「そんなの分かるわけないじゃん..」という感想
50%以上の割合で解けるレベル帯という考えが重要
そんなの分かるわけない癖が付くと、自分で考えたくなくなる
鹿本が良かったのは、先頭から進めたことで、自分にも解ける問題をいくつも楽しめたから
DFSを理解できたかは分からないが..
DFSのテンプレの流れを上手く捉えられるようになったと思う
seenを上手く利用できて良かった！
ラムダ式で書いたDFSをラムダ式内で呼び出すには？
自動型指定子で宣言された変数は独自の初期化子では指定できません
2つの方法がある
諦めた
dfs関数自体を引数に追加する。
自分で書けた！✅
DFSの世界が見えてきた
この問題では、ある点に到達できるかを調べたい。
seenを一度trueにすれば十分と分かる。
複数回見るとTLE
もう一度、先週のABCのC問題を確認してみよう
重み付け
例のケースは全部通せた！
今まで書いてきたグラフについて、辺のもう一方の端点に加え、辺の重みも保持するようにする
pairで
こうすると、辺の重みと、辺そのものを同時に扱えて良い
一度提出してみる
dfsだから、メモ化を要求される気も。。
その前に、計算量を検証すべき
今回は、$ O(N(N+M))
間に合うような？
ACした！
メモ化するともっと早そう
動的計画法で書ける人もいるんだろうか？
なぜWAなのか？
区間和のindexの扱いを考察する
以下は入力値を0始まりにしたものとして考える。
半開区間$ [l, r)
そのままテンプレートを適用するだけで良い。
$ S_{i+1} = S_i + v_iなので、
$ S_{n} = v_{n-1} + v_{n-2}+...+v_0
$ S_r-S_l = v_{r-1} + v_{r-2}+...+v_l
区間和を利用するときの添字について考察する
制約を見る
$ l, r\le nというふうに制約されているなら、コード中のs[l + 1]、s[r + 1]はエラーにならないはずだ
l、rは0始まりに補正しているから
解説なしAC
手動テストあるある
Inputをコピー・ペーストせず、Outputをコピー・ペーストしてしまう
間違っているのは入力値なのに、ロジックを疑ってしまって収拾がつきにくい
解説なしAC
変数kは、N以下である
区間の長さが任意の区間和問題では、部分和sの添字はn+1までOKであることを意識する
他の人のコードを読んでAC.icon
考察
求めるものは、すべての移動における、「S[宿場町番号の大きい方] - S[宿場町番号の小さい方]」の和
例を使ってこれが正しいことを確かめた
移動距離は、絶対値を考えれば良い
したがって、入力される、宿場町間の距離の部分和を計算する
思いつく可能性をすべて検証した状態。成長の機会
自分の修正後の提出
参考にした正答
code:bad.cpp
// bad
ans += abs((sk + p % 100000) - (sk % 100000)); // good
余りを取ってから差を取ると、答えが変わる？？
いや、多分そうではない
以下は同じ値になる
余りを取る → 差を取って余りを取る
差を取って余りを取る
証明
今回は、計算結果をansに足している
ans も 100000 で余りを取っているからなんとなく良いと思った 例
西向きの人の数の累積和
配列
西を向いていれば1を、そうでなければ0を足したい
部分和の表現
code:partial_sum.cpp
// good
vector<int> ve(n + 1);
vector<int> vw(n + 1);
for (int i = 0; i < n; i++) {
}
xが1の場合は、 == の返値を足すと綺麗
xが1以外の場合は、?
やってはいけないのは、以下のような書き方
code:paritla_sum.cpp
for (int i = 0; i < n; i++) {
// ...
}
この方法だと、要素が条件を満たさないとき、対応する部分和の要素が0になる
以降の累積和が正しく足し合わされなくなる
解説なしAC（1ペナ）
多くの問題で、Nの制約は$ N \le 10^5
$ O(N^2)の提出を弾く効果がある
初めの方の提出でWA.iconだったので、流石にそれだけが原因ではないだろう..と思っていた
実際はこれを直してAC.iconだった
正直、最大値の定義はコード中で一度しかしないので、
解説なしAC
素数判定に使うのは？
方法を知らない
$ \sqrt Nまで探索
素数だったものを順番に割っていく
もしすべて余りが0ならば、素数のリストに追加
みたいな感じで良いかな？
素数判定に時間がかかった
本来の条件である、$ Nと$ \frac{N+1} 2が両方素数というのを忘れていた
ちなみに、$ N \ge 3においては、
$ \frac{2N-(N+1)} 2 = \frac{N-1} 2\gt 0より、$ N\gt \frac{N+1} 2
区間和を考えるときは必ず0始まりにする
素数判定は1始まりのほうが楽
素数判定部分と区間和処理部分を分けると、上手く行く
解説AC
変遷
WA.icon 6ケース
WA.icon 3ケース
float型をdouble型に変更
AC.icon
感想
出力は精度よく行うべき。
printf("%.10f\n")はテンプレートにしておｋ
精度で悩まされないためにこの選択を固定する
僕自身、累積和を用いる問題に対して、毎回添字の扱いに神経を尖らせながら頑張っていたのですが、一度実装テンプレートを決め込んでしまえば何も考えなくても書けるようになりました。そうなってからは累積和を実装することにストレスが無くなりました。
とてもわかる。
フレームワーク上で各問題を思考すると、スムーズに結論が出る。
解説なしAC
二次元累積和を使う必要がありそう。
最大で$ 10^8回程度のループなので、この処理では間に合わない
を読みながら直しているけど、二次元累積和が何を意味しているのか..
デバッガで、生成した二次元配列を読むと、少し理解できた
配列の作り方も分かった
配列の造りが分かったら、使い方も分かった
解説AC
table:hoge
k 1 2 3 4 5 2n 2n+1
A B + C C + A + A + B (2A + B + C) 2A + 3B + 3C 6A + 5B + 5C 10A + 11B + 11C
B C + A A + B + B + C (A + 2B + C) 3A + 2B + 3C 5A + 6B + 5C 11A + 10B + 11C
C A + B B + C + C + A (A + B + 2C) 3A + 3B + 2C 5A + 5B + 6C 11A + 11B + 10C
1, 2, 3, 6, 11, 22, 42
table:hoge
k A B C
5 10A+11B+11C 11A+10B+11C 11A+11B+10C
6 22A+21B+21C 21A+22B+21C 21A+21B+22C
$ a_{n+1} = b_n+c_n
$ b_{n+1} = a_n + c_n
$ c_{n+1} = a_n + b_n
$ a_{n+2} = b_{n+1}+c_{n+1}=2a_n+b_n+c_n=a_{n+1} + 2a_n
$ a_{n+2}-a_{n+1}-2a_n =0
特性方程式 $ x^2 -x-2 =(x+1)(x-2)=0を解いて、$ x=-1, 2
ゆえに、$ a_{n+2} a_{n+1} = a_{n+1}-a_{n}
解き方思い出せない
もう1回、高校数学をやる必要があるかもしれない
こういう根本的な部分でつまずいてしまうから、世間一般的に、大学受験で失敗している人間は扱いにくいのだろう
★ 「A - Bの推移」を、「具体的な数字を使って」、把握する
A - Bの推移
= 問題文で問われていることに注目して
具体的な数字を使って
= 文字だけを使うことに執着せずに、具体例を活用する
試してみよう
試せた ↓ いい感じ
table:hoge
k 0 1 2 3 4
A 2 5 9 19 37
B 1 6 8 20 36
C 4 3 11 17 39
A-B 1 -1 1 -1 1
このように、$ (A_0 - B_0)(-1)^kとなる。
kが偶数のときは A - B。
kが奇数のときは B - A。
鹿本に学びを得た。
以下のような方針で問題ないのか。
次に光るボタンのvectorを用意する。
ボタン1（添字0）からvectorをたどっていく。
ループ判定？
ボタン1からのボタンのたどり方はただ一通りである。
ただ一通りであることを示す。
もしただ一通りでないとしたら、
https://scrapbox.io/files/64eec9be7a197c001c853a5d.png
こうなる
これがおかしい
枝分かれが存在するはずである。
すべてのボタンについて、そのボタンを押したあとに光るボタンは一種類しか存在しない。
ゆえに、あるボタンから押し始めたとき、以降の押す順番は一通りしか存在しない。
ボタンnを押すと光るボタンは、ボタンn+1しか存在せず、ボタンn+1を押すと光るボタンは...
したがって、以下のような構造以外は存在し得ない。
https://scrapbox.io/files/64eecb6edc3c3e001cfc5726.png
ループ判定をすればよいと分かる
ループ判定は、「次に光るボタンが1である」かどうかを見れば良い
先に述べた通り、ボタンを押す順番は一通りしか存在しないから、ループするならいずれ1にも戻ってくる
方針が立った
vectorに入力する
1からたどる
次に光るボタンが1か？
seen配列を更新するのを忘れた
色々更新しなければならない
ボタンを押した回数
既にたどったノードのリスト（seen配列）
現在見ているボタンのindex
2021年に何か解いていた
2021
1511ms
2023
17ms
早くて良いね。
解説（人のコード）AC✅
任意の面を置いて..
この時点で、6が側面に来るようにしなければならない
1だと反対の面に来るのでいけない
2 ~ 5
2から始める場合
nに対して、nと7 - n以外で最大の整数を取れば良い
1. 2に対して、2と5以外で最大の整数は6
2. 6に対して、6と1以外で最大の整数は5
3. 5に対して、5と2以外で最大の整数は6
4. 6に対して、6と1以外で最大の整数は5
このように、2から始めると、そのとき取るべき戦略は一意に定まる
2n - 1回目の最大得点は、6(2n - 1) + 5(2n - 2) = 22n - 16？
ここで式を表すことが苦手な模様
分かった
n = 2m のとき、11m
n = 2m + 1のとき、11m + 5
パターン化したい
数学Ⅰに戻りたい..
基礎的能力の低さ
5から始める場合
1. 5に対して、2と5以外で最大の整数は6
同じことになった
ここでは、n回目の時点で取りうる最大値$ h_nについて、$ h_{n-1} \lt x \le h_n (n\ge 2)
この条件を満たすなら、n+1回目の操作が不要となる
条件を言い換えるには、場合分けが必要
$ n = 2mのとき、$ n-1 = 2m-1より、
$ 11m-6\lt x\le 11m
$ \frac x {11} \le m \lt \frac{x+6}{11}
この条件を満たすmを見つけたら、2mが求めるべき値。
$ \frac x {11}を切り上げた数
$ n = 2m+1のとき、$ n - 1 =2mより、
$ 11m\lt x \le 11m+5
$ \frac {x-5}{11}\le m\lt\frac x {11}
この条件を満たすmを見つけたら、2m+1が求めるべき値。
方針が出来た
答えが合わない原因が分からない
6を入力したときには、2と出力
$ n\ge 2という成立条件を満たしていないから不正入力
分からない
149696127901への出力が27217477802
これは1多い
code: NG.cpp
using namespace std;
int main(void)
{
double x = 0;
cin >> x;
cout << (long long)min(2 * ceil(x / 11), 2 * ceil(x - 5 / 11) + 1) << endl;
return 0;
}
他の人の解答を読んだ
解説を読んでいないが、おそらく次のように考えている人が多い
https://scrapbox.io/files/64f8980364775c001bdf73a7.png
1引いて11で割って切り捨てて、2をかける
1引いて11で割って、余りが5以下（6未満）だったら1足す
余りが6以上だったら2足す
感想
式を表して不等式を作り、条件をプログラム可能にするのが難しかった
共通テスト、数Ⅰ、選択問題5
これは複雑なので、手法の1つ程度に考えておくべき
シンプルにできる捉え方があるなら、覚えておこう
解説AC
これは、数学的に考察できることが1個ありそう（未来透視）
$ p =\mathrm{floor}(\frac{Ax}B),q =A\cdot\mathrm{floor}(\frac x B)
$ \frac{Ax} B\le p \lt \frac{Ax} B + 1
$ A\frac x B \le q \lt A(\frac x B + 1)
$ -A\lt p - q\lt 1
このように考えたが、間違っているのか？
床関数なのに、天井関数になっている
これだと全部1になってしまうが..
数学的に考察できることが1個ありそう（Take 2）
$ \frac{Ax} B-1\lt p \le \frac{Ax} B
$ A(\frac x B - 1) \lt q \le A\frac x B
$ -1\lt p-q\lt A
最大値はAなのか？
でもAだったら、そういう問題にはならないはずだ
解説を読む
xによっては、A - 1にならないことがある
それを調べるべきだった
でも、たしかに$ 0\le p-q \le A-1は常に満たしている
数式を使った方法は意味が分からなかった
理解できてきた
次に同じことを考えられるようにするには、以下のようなことを思い出す必要がある
あまり$ rと割る数$ aの関係は、$ r\lt aである
例えば、5で割ったなら余りは当然5未満になる
床関数にあまりと割る数を用いた数を渡すとき、$ \lfloor \frac r a \rfloor = 0
上述の大小関係を、$ rの定義時に書き添えておくことで、この事実に気づけるはず
整数$ nについて、$ \lfloor n\rfloor =nである
ガウス記号の中に整数を見出す
割られる数$ xとあまり$ rの関係は、$ r\le xである
例えば、8を割ったなら余りは8以下
加えて、以下のことを思い出せるとなおよい
$ \lfloor x \rfloor \lfloor y \rfloor \le \lfloor xy \rfloor
補助的に、今後以下のように定める
あまりは$ rとおく。
OK導けた！
$ \lfloor \frac {Ar} B \rfloor
$ 0\le r \le N
$ 0\le r \le B-1
後は、$ \min(N,B-1)を取るだけ
自分で導けて楽しかった！！
AC.icon！
解説なしAC
https://scrapbox.io/files/64f9e584498c38001ce4ea8a.png
j回目に訪れた町indexを保存する
これを行う根拠
2回以上同じ町indexが現れた（seenがtrue）だったときに、何回の周期でその町が現れるかが分かる
とりあえず、書いた
今は完璧だと思っている
1つめのケースに対する問題
AC.icon
3年前にはWAしているし、遅かったから今は成長した
2つめのケース
デバッグをし始めてから非常に時間がかかった
「現在いる町」を、初期値（0）にセットすると上手く動くが、そうでない場合は上手く動かない
これは安定しないので、つねに0で良い
単純な文法ミス
k - p / tではなく(k - p) / tだった
自分で導いたindexの計算式は間違っていないことがわかったので、一安心
実装も、以前リンク先の問題を解いたときと同じ seen を用意する方針から考えていった
seenと現在地のほかに、もう1つや2つ情報の更新があるので、忘れないように
テンプレートを持っておいても良い
区間和やグラフDFSのように、indexに困らずに済むはず
解説AC
7, 77, 777
第n項は、$ \sum^{n}_{i=1}7\cdot10^{n-1}=7\cdot\frac {10^n-1} 9
良さそう！
この数がKの倍数 → Kで割って余りが0
この問題は、数Bが必須
AtCoderにおける数学の位置づけを思い知ったかもしれない
では、ないと思う
具体的にどこまで探索すれば良いのか？
ここが自分の数学的な考察の限界
この次は、手を動かして探索する
Kが7の倍数の場合、Kを7で割った数に対して考えると良さそう
$ \frac {10^n - 1} 9について考える
素因数分解に法則性を見出したかったが、無理だった
解説をちょっとだけ読んだ
教育的な問題だ
「第n項までのn個の数に、Kで割った余りが0になる数が少なくとも1つ存在する」
これは、鳩の巣原理から、余りが0にならないことを確認しながら第K項まで順番に見ていけば確実にどこかで見つかる
最悪$ 10^6桁になると思う。100000桁を扱える型とは？
この考え方では詰まった
余りの性質を使う
$ 10^{100000}のような値に対する対処は、解説PDFにあった
解説動画を見た
漸化式に余りを適用していく際のグラフは、有向
枝分かれがなく、同じところを二度通ったら、以降は巡回する
説明
この問題は、各数に余りを計算しなくてもよくなっている
modで計算し続け0になったら、元の式でも対応する数をKで割った余りは0になる
一度ループが発生すれば（=第n項と第m項でmodが一致）、それ以上異なるmodは出現しなくなる
第K項まで、余りが0になるかを見ていって、もし一度も0にならなければ必然的にループが発生している
一度でも0になったらその時点でループを打ち切ればよい
コンテスト中は方針がまったく立たなかった
注：ACできていない
答えの書き方を間違えた
x = ((x % 10) * (x % 10)) % 10
これだと、同じ数を掛けられない
累乗でもmodの性質が成り立つことを見つけた
ここで改めて、数Ⅰが必要
loopの省略方法は？
型を決めこみたい
今のところ、その数をいつ見たのか？を格納している
もう一度発見したら、以下のように計算できる
周期：今のカウント変数 - 前回いつ見たのか
https://scrapbox.io/files/64fd7dec8bea44001ba75b43.png
Teleporterの解説は、もう少し単純だったかも？
図において緑色の部分だけ調べれば良くなる
1. 周期を見つける
2. 周期が始まったタイミングを思い出す
3. 一番最後の周期が終わる場所を計算する
4. それ以降を順番に見ていく（あるいは、index指定で過去の結果を呼び出す）
過去の結果を呼び出したほうが早いから、過去に現れた順番を配列に保存するべきだろう（）
配列の要素数は、たかだか10個でいい。
0123456789という10種類が最大で存在し、11個目を見るときには必ず被っているから
https://scrapbox.io/files/64fd82b0c82d78001ce375cc.png
$ k - p - \lfloor \frac {k -p } t \rfloor tは、そこから消し去るべき要素の数なんだ
省略した要素を「なかったことにして」考える必要がある
なので、1個戻って、新しくカウントを始めよう
上図では、「1」から1個戻って「0」からカウントを始める
周期内の領域において、1個目の要素は「7」となる
https://scrapbox.io/files/64fd86c8a53e8c001bc6f868.png
1 1の場合は？
つまり、同じ数が連続する場合
図（誤り）
https://scrapbox.io/files/650117e6a6d1f8001cffb6ef.png
図（正しい）
https://scrapbox.io/files/650118fc4f8e8f001b6dc70a.png
この図を見て、kの定義がおかしいと気づいた
今回はindexの計算をしたい
indexの範囲が必要
値の個数は必要ない
まとめ
k を個数として考えない。範囲という考え方も持つと良くなると思う
一部ケースでWA.iconになることもあるが、そのときはまず制約を疑う
型ごとの初期値
intは0、boolは..
関数内では初期化されない？
今後は配列にも初期化を行うように（{}とすれば、補完してくれる）
初期化しないという選択肢はない。
解説なしAC
何度かWA、REを出している。注意が必要かもしれない
解説ありAC
面白い問題
未AC