せっかくだし入緑記録を書こう
う
折角緑コーダーになれたので、記念記事でも書いていこうと思います。
▼入茶記事
AtCoder 入茶記念として勉強法を改める - volcano-tofu’s blog
入茶記事の最後の方に「緑になるときはD問題100問解く！」とか書いてあるんですが、実際はD問題76問で済みました。
自分にとって無理のある目標を作るというのは向かないな、と今は反省しています。
現実味のある、今の自分が背伸びして届きそうな目標を立てて今後は頑張りたい。
そういえば、入緑にかけてですが、A問題とB問題は基本的に解いていないです。C もほとんど解いていない。(C はあくまで復習ぐらいしかしていないかも)
↓これは入茶時の記録
A, B, C 問題が各々 +30 ぐらいで、D は +40, E は + 15 ほど。
バチャコンに出たり、解いていないABCを埋めたりで A~C が増えているだけで、実際は D をメインに解いていました。
・やったこと
sano192さんという、とある緑python勢の方がいるのですが、そのsano192さんが出版している本やqiitaの記事を参考に勉強をしました。
本は以下のもので、茶コーダーの人が使うには丁度よい難易度だと思います。
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf ： 精選50問詳細解説
https://www.amazon.co.jp/dp/B0BBB7RKTP ： 最速で緑になる本
ぼくは灰のときから購入しましたが、「自分はこんなものですらわからないのか」と挫折をして、その後半年程やめてしまいました。（今思えば半年間辞めてた人が急に参加し始めて、文法知識は灰レベルなのによく1ヵ月半で入緑できたなと思ってる）
あと、sano192さんはqiitaの記事でABCの緑diffまでの問題を解説していらっしゃるので、そちらの方を参考にしたりで色々お世話になりました。
python勢 かつ 緑コーダー以下の人は検討してみてはいかがでしょうか。動画も投稿されていて、BFSやDFSはsano192さんのを参考にして実装できるようにもなりました。
もう本当に頭が上がらないです。
あと他にやったことといえば、バチャコンと緑diff, D問題埋めぐらい？
と、気付いたら自然と緑パフォが出てるような感じでした。
水パフォのABC271は水diffのDP問題を解けたため、跳ね上がっています。
その後はほぼ安定して緑パフォを出せているように見えます。
――――と、いい感じに見えるんですが、この水パフォを叩き出すのが非常に大変なんですよね……。
今後はただでさえ伸びづらいのがわかっているから、生半可な気持ちで取り組まないよう尚更問題の質を高めて苦しまないといけないのか……と、消極的に考えてしまいます。(笑)
水diff普通に難しすぎるのが嫌すぎるし、青diff以降とかもうレベチすぎて……。
まぁ、緑にかけてやったことはsano192さんの本を読んで、今の自分にはちょっと難しい問題を沢山解いたことぐらいですね……。
佐野さんの本が優秀すぎたというか、ぼくとの相性が良すぎたのがあるかもしれません。
例えばセグ木を勉強したところで、高度な問題が解けなければ履修したところで使えないアルゴリズムに分類されたりするので、”アルゴリズムを勉強する”というよりかは沢山問題を解いてどういう思考・アルゴリズムが使われているのか？を問いながら学習を進める方が良いような気もする。
あと、ぼくはこどふぉとかそのほかのやつやったことないです。あとこーだーしか興味なかったのでずっとあとこーだーの問題を解いてました。
・今後したいこと
AtCoder Problems の機能にある Recommendation をやろうかなーと考えています。
つよい人の記事を拝見すると大抵の方がやっていらっしゃるんですよねー。
なので、新たにれこめんでーしょんと水diff、E問題埋めをしたいかな。
あとEDPCも解いておきたい。
何か特別なやり方とか、近道があるだろう！とか全く思っていないし、何よりもぼく自身が人より倍以上努力しないとできない人間であることを重々承知しているので、上記の通り、今の自分がやるには少し難しい水diff問題やE問題を埋めていこうと思います。
(あとEDPCは解説している人が少なすぎる！！強い人の記事は強い人向けに書いてあるような簡素な説明が多かったりで、もう少し詳細に書いて欲しいなーと思ってます。クソ雑魚コーダーなので許してくださいよ)
・最後に
写経についてちょっと書こうかな。
勉強法に困っている人っていっぱいいると思います。なんならぼくも困っているので気持ちはわかります。
数ある勉強法の中でも写経が話題になることがあるのですが、解けない問題があったら写経してもしなくてもどっちでもいいと思います。(解説ACするのもしなくてもどっちでもいいと思います)
初めの頃はBFSやDFSの書き方が全くわからなかったので、何度も何度も写経を繰り返してそのコードを覚えて、書き方を覚えたら他の問題でBFSとかDFSを書いて書いてを繰り返していくうちにそのアルゴリズムの理解度が深まって、次第に自分の力だけでそのアルゴリズムを組めるようになって――――の繰り返しなので、一概にダメとは言えないと思います。
ただ、これは書き方のわからないアルゴリズムを習得するためだけに写経をしていて、最終的に書き方がわかるようになったからダメではない、と結論付けることが可能なだけで、書き方がわからなければダメだよね、になると思います。
その問題、アルゴリズムの書き方や考え方がわからないから写経をする、の最終目標はその問題のみならず他の問題に対しても書き方や考え方がわかるようになり、問題が解けるようになる。ということだと思います。応用できるやり方じゃないと伸びるわけないよって話です。
あと強い人をちらちら見ていると写経したことないとかえぐい発言をしてる人をたまに見掛けますが、流石に真に受けない方がいいと思います。自分自身はめっちゃ強い人なんです！と胸を張って主張できる人以外は色んな勉強法を何回もかじってみて、何回も咀嚼して、十分味わった方が良いと思います。
ただ参考になる部分は参考になりますので、真似できるところから始めてみるのがいいんじゃないのでしょうか……。(ぼくは Recommendation から始めてみることにします。)
う
迫真競プロ部・復習の裏技 【無限精進編】
・バチャコンに参加したのでその復習
実装力かな。苦手。
目処がついても実装力が皆無すぎて TLE ばっかりする。
典型 of 典型問題。重みなし最短経路問題なのでBFS。
以下の佐野太郎さんの動画がたいへんわかりやすいです。
Dsrxq でも理解できる。
包除原理。包除原理の問題の中でも最も簡単な部類に入る。
pow(i, j, mod) と使いこなせるととてもらく。
考察力？不足している分を補う、という考え方で解いた。
典型 of 典型問題。深さ優先探索。
以下の佐野太郎さんの動画がたいへんわかりやすいです。
Dsrxq でも理解できる。
DP。これがわからなくなったらナップサック DP に戻るとよい。
dp[i][x][y] := 弁当を i 個目まで見て、たこ焼きの個数が x, たい焼きの個数が y になるときの弁当の最小購入数 (買っても買わなくてもよく、X や Y を超えたら X, Y としてみなす)
と定義するとよい。
考察力。3 つ目の条件がキーとなる。
解説を見て目にした「5 で割った余りが等しいもので揃えればよい」で発狂しました。
当たり前のことをどうして気付けなかったんですかね……。
これは難しすぎた。解説動画を 2, 3 回ほど見てやっと理解したのだが、実装しようとしたら TLE になりそうだったので諦めた。
以下、数列 A を {a1, a2, a3, ..., aN} である。
「A の全要素の最大公約数が X である個数」を求めるのはたいへんむずかしい。
だが、「A の全要素が X の倍数である個数」を求めるのはうんちをするほど簡単である。（これはまくどうんち大学の国語で出題された慣用句のひとつなので、覚えておこう。）
A の全要素が X の倍数であるとは、例えば X = 2 の倍数であるなら A の全要素が 2, 4, 6, ..., のいずれかであればよいから、その個数は K // 2 が N 個より (K // 2) ** N であることがわかる。
しかし、全て 4 だとすると 2 の倍数でもあるのだが、4 の倍数でもある。
そう、余分な個数まで数えてしまっているのだ。
したがって、余分な個数を減らせばよく、これは
d_i = A の全要素の最大公約数が i である個数
D_i = A の全要素が i の倍数である個数
とすると、d_i = D_i - d_(2×i) - d_(3×i) - ...
である。... の部分は K 以下まで行う。
提出コードはつよつよコーダーのしょぼうんちの ACコードを参考にさせて頂きました！
ケツから考えるタイプ。実はグラフとしてみることができ、BFS で解ける。
最短経路問題。BFS だが、この手の迷路みたいな二次元問題を解いたことがないと厳しい印象。
見方によってはグラフ問題。貪欲法に近い考え方で解ける。
結局、その座標の最も大きい位置と最も小さい位置の 2 つだけ選択すればよい。
これは……bit 全探索か！？と思わせるような文意だが、残念ながら制約がとても大きい。
でも「左の頂点を選択する」 or 「右の頂点を選択する」というのは応用して DP で解くことができる。
しかし本問はそこまでする必要はなく、
１．「今左の頂点にいて」「次左の頂点に移る(その後右の頂点に移る)」か「次右の頂点に移る(その後左の頂点に移る)」
もしくは
２．「今右の頂点にいて」「次左の頂点に移る(その後右の頂点に移る)」か「次右の頂点に移る(その後左の頂点に移る)」
とし、値が最小なのを常に選択することで最適解を得ることができる。
▼ かつっぱ氏の動画を参考にしたので、気になる人は見てみよう！
BFS 問題。「訪問していないなら訪問する」、という設定はいつも通り。
問題なのは訪問済の場合の設定。単に「訪問済の所に訪問するから + 1 増える」とは考えてはいけない(戒め)
なぜなら、それが最短経路である保証がなされていないからである。
したがって、その設定を設ければよく、(次行く頂点の最短歩数) - (今いる頂点の最短歩数) == 1 なら最短経路である保証がなされるためAC！
D にしてはやさしいが、茶にしては難易度は高いかも。2 WA しました……。
DP。実験するとわかるかもしれない。
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ... として考えるとよい。
dp0 = 0
dp1 = 0
dp2 = 0
dp3 = 1
dp4 = 1
dp5 = 1
dp6 = 2
dp7 = 3
dp8 = 4
dp9 = 6
...
となる。
dp6 は dp3 の結果が使える。
dp7 は dp3, dp4 の結果が使える。
dp8 は dp3, dp4, dp5 の結果が使える。
dp9 は dp3, dp4, dp5, dp6 の結果が使える。
...
dpi は dp3, dp4, ..., dp(i - 3) の結果が使える。(i >= 3)
数学問題。
A1B1 = A2B2 = ... = ANBN が成り立つから、なにか 1 つの値がわかれば全ての値がわかりそうだ。
本問が要求している Bi の求め方は A の全要素の LCM がわかればよい。
つかれた。
典型 of 典型問題。DFS。
以下の佐野太郎さんの動画がたいへんわかりやすいです。
Dsrxq でも理解できる。
累積 GCD っぽいなにか。
left : A の左側 (0, 1, 2, ... N - 2 インデックス) における GCD
right : A の右側 ( N - 1, N - 2, ... ,1 インデックス) における GCD
をつくる。
好きな数字に置き換えてよい、というのは他の数字に置き換えたりしてもよいので、なかったことにできるということ。
O(N²) で解けるが間に合わない。無駄な計算をせずに高速化を図るために累積 GCD を作る。難しいのは左右から作るというところ……。
ただの面倒くさい実装。
あまり復習したくない類の問題。
１．1 から 10⁵ まで素数の一覧表をつくる。
２．3, 5 ,7 ,... が素数かつ 2017 に似た数なら累積和のカウント +1
３．クエリから範囲を取得して出力して終わり。
めんどくさい……めんどくさくない？
うんちぶうううううううううううううううううううううううう
a1, a2, a3, b1, b2, b3 のいずれかの値がわかれば ok
あとは c と一致するかどうかを判定すればおわり
実験しまくった。O(√N) でなんとかして解きたいから、N = 100 の場合を考えた時に
100 // 1 = 100
100 // 2 = 50
100 // 3 = 33
100 // 4 = 25
100 // 5 = 20
100 // 6 = 16
100 // 7 = 14
100 // 8 = 12
100 // 9 = 11
100 // 10 = 10
これだけで答えがわかるという。……は？そんなことできる……？？？
なんでか知らんけど、割った数と商の関係性に注目すると、
100 // 1 = 100 だが、100 // 100 = 1
100 // 2 = 50 だが、 100 // 50 = 2
100 // 3 = 33 だが 100 // 33 = 3
...
であることに気付いた！
したがって、
100 // 50 = 2
100 // 51 = 1
100 // 52 = 1
100 // 53 = 1
...
100 // 100 = 1
であることがわかる！
割った数と商には何かしらの関係性があったようだ。
ここでいくつかの疑問が生じる。
１．いくつまで割ればよいのか？√N まで続ければいい？
２．その関係性はもっと明白にならないのか？
などなど。
１について、割った数 i とその商 j が i >= j となったらよさそうだ。
ex) N = 8 のときがそうで、√N とすると i = 2 までなのだが、i >= j とすることで i = 3 まで深堀することができた！
２について、商の値の前後がまさに個数で、それに着目すればよいだろう。配列を用意するか、他にデータを保つ方法をとればよい。
しかし、ここには欠点があり、１の i >= j は気を付けるべき点が存在した。
それは 1 個重複する可能性があるということ。i = j なら重複はしないのだが、i > j は重複してしまう。
これに気を付けて実装しなければならない。
■
- import sys
sys.setrecursionlimit(10**7)
input_grid = [[0, 0, 8, 7, 0, 0, 0, 1, 0],
[0, 5, 0, 0, 0, 3, 0, 0, 0],
[0, 0, 0, 2, 4, 8, 0, 0, 0],
[0, 9, 0, 0, 0, 0, 0, 2, 4],
[0, 3, 6, 0, 0, 0, 0, 0, 1],
[4, 0, 0, 0, 0, 0, 5, 0, 0],
[0, 0, 0, 3, 8, 7, 0, 0, 0],
[0, 0, 0, 9, 0, 0, 0, 0, 2],
[0, 0, 7, 0, 0, 6, 0, 5, 0]]
def find_next_cell(grid):
for y in range(9):
for x in range(9):
if grid[y][x] == 0:
# 埋まっていない座標を返す
return y, x
# すべてのマスに数字が入っている状態
return -1, -1
# 条件を満たすかの判定
def is_valid(grid, y, x, value):
# 横のチェック
is_row = value not in grid[y]
# 縦のチェック
is_column = value not in [i[x] for i in grid]
# ブロックを取り出す
blk_x, blk_y = (x//3) * 3, (y//3) * 3
blk_grid = [i[blk_x:blk_x + 3] for i in input_grid[blk_y:blk_y + 3]]
# ブロックのチェック
is_block = value not in sum(blk_grid, )
# 有効チェック
return all([is_row, is_column, is_block])
# すべてのマスを調べて数字が最大で何個入りそうなのかを確認する
def possibility(grid, y, x):
# インデックス番号
idx = 0
# 今考えているマスにどれだけの数字が入りそうなのか
mass2 =
# 今考えているマスに
number2 =
tmp =
if grid[y][x] != 0:
return True
else:
cnt = 0
for value in range(1, 10):
# もし今考えている数字が入りそうなら
if is_valid(grid, y, x, value):
# 最大で入る可能性数を足す
cnt += 1
tmp.append(value)
# そのマスには cnt の数だけ入りそう
mass2.append([cnt, y, x])
number2.append(tmp)
return *mass2, *number2
mass=
number=
mass_num=[]
for i in range(9):
for j in range(9):
if possibility(input_grid, j, i) != True:
mass.append(possibility(input_grid, j, i)[0])
number.append(possibility(input_grid, j, i)[1])
for i in range(len(mass)):
mass_num.append([mass[i], number[i]])
mass_num.sort()
y = mass_num[0][0][1]
x = mass_num[0][0][2]
idx = 0
#print(mass_num[0][0][3]) インデックス番号は 0 0 3 だ！()
# 実際に数字を再帰的に入れてみる
def solve_sudoku(grid, idx):
#[print(i) for i in input_grid]
Y, X = find_next_cell(grid)
if Y == X == -1:
return True
for value in mass_num[idx][1]:
if is_valid(grid, mass_num[idx][0][1], mass_num[idx][0][2], value):
grid[mass_num[idx][0][1]][mass_num[idx][0][2]] = value
# 次へ
idx += 1
if solve_sudoku(grid, idx):
return True
grid[mass_num[idx][0][1]][mass_num[idx][0][2]] = 0
idx -= 1
return False
print(solve_sudoku(input_grid, idx))
[print(i) for i in input_grid]
AtCoder 入茶記念として勉強法を改める
！注意！
これはよわよわコーダーの独り言です。
この記事を読むより効果があるものを紹介します。
以下のものを見たらこの記事は読む価値がないものだとわかりますので……
（気付いたら AKITO 氏しか貼っていないけど、勉強系だったらこの御方がダントツに信用できるので……）
※追記でこちらも貼らさせて頂きます
俺が1位だ #ウマ娘 pic.twitter.com/KGHt4yvt1V
— かえで㌨㌨ (@youzyo_Kaede13) 2022年3月17日
キタサンおすすめサポカをメモしました。
— かえで㌨㌨ (@youzyo_Kaede13) 2022年3月18日
組み合わせと
僅かながら参考になれば幸いです#ウマ娘 pic.twitter.com/n8tnEpwuMt
皆育成方法って言うけど正直''無い''
— かえで㌨㌨ (@youzyo_Kaede13) 2022年3月18日
基本的なレースも、サポカも出した。
あとはその時の運と自分自身の考えなんだよ。自分で考えてくれ
ピスケス杯確定枠
— かえで㌨㌨ (@youzyo_Kaede13) 2022年3月17日
100%負けません。当たったら発狂してください#ウマ娘 pic.twitter.com/FuGpFxCaVg
・やっていたこと
１．写経
２．問題解きまくる
３．アルゴリズム習得
４．復習
・やらなかったこと
５．バチャコン
・おまけ
６．音楽を聴きながら作業することについて
７．今後について
・意識したこと、注意するべきことについて
覚えるべきことは覚えて、理解することは徹底的に理解する、という二点だけ。
あとはその質を維持したまま物量を熟す。何れ少しずつ質を上げることができるようになるため、なるべく質は上げつつ下げないことを意識する。
これは……勉強の基本的なことではないだろうか？
裏技なんてものは存在しなかったんだ……
残念ながら、我々は当たり前のことを当たり前にやっていくしかない。それもじっくりと時間を掛けて、じっくり苦しむ必要がある。
・１の写経について
これはあまりやる必要がなかったかもしれない。コードを丸々書いたからと言って理解できることが少なかったから。
ただ、初歩的なアルゴリズム習得時には役立ったと思う。
例えば BFS とかは最初のうちはどう書けばいいのかわからなかったので、何度も写経し、覚えては今度はそのコードを思い出しながら書き、忘れるのでまた写経したり覚えなおす。
何回か書いていくうちに自然と覚えていき、その問題だけでも一時的に解けるようになっていく。
そこから違う BFS の問題を解こうとすると、多分解けないんだけど「こういう風に実装すればいいのか！」とか色んなことを吸収できる。
そうして何度も何度も違う問題を解いていく際にまた BFS の問題が来ると
１．「どう考えればよいのか」
２．「求めたいのはこれ」
３．「こういうのができたら嬉しいな」
４．「全探索したいけど、どう探索すればいいか」
５．「ひとつひとつ見ていけば良さそうだ」
６．「BFS で解けそうだな」
というプロセスが生まれ、やっと初めて BFS を実装できる。
ここまで考え抜くことで差が生まれるんだと思う。
今までやってきたことは単なる "問題集を虱潰す" だけであって、実践では "考え抜いて実装する力" が求められる。
ぼく自身は大した勉強もしたつもりもなく、アルゴリズム力もその知識も皆無なのだが、このお陰で何とか ARC 137 を A,B 2 完できたんだと思う。
・２の問題を解きまくるについて
所謂 "精進" ってヤツ。かんたんに、凡人だと思う人程、よわいと思っている人程、常日頃から問題に触れていないとそりゃ伸びないよねって話。
問題を沢山捌くことで、要求される知識や実装をアウトプットできるので、問題を沢山解きまくることはいいことだと思う。
ただ、上にも記載させて頂いたが、あくまでこれは "質を維持したまま問題を解きまくる" ということを示唆しているので、A 問題を沢山解く！というよりかは C を安定させるために沢山解く！とか、D を解けるようになるために解いてみる！ということである。
残念ながら、当たり前といえば当たり前ですね……
▼ C 問題を沢山解いた結果の図
・３のアルゴリズム習得について
必須。覚えるべきもの。なので覚える。
DP とかは最近の C でも頻繁に出題されるし、汎用性が高いので入茶する人は覚えるべきものなんだろうなぁと思う。
覚えておいて損はないのだが、その問題しか解けないレベルの理解力や実装力は論外なので、沢山の問題に触れるべき。
問題集でアルゴリズム習得を促し、実践で「こういうのを実装したい」「あのアルゴリズムを使えばいけそうだ」という流れを作れるまで理解し、実装力を高めよう。
・４の復習について
どうして復習をするのか。についてはどうしても忘れてしまうからとしか言いようがない。
理解できていない部分、見えなかった部分が見えるようになるかもしれないので、なるべく復習はしておくとよい。
当たり前だと思ったかもしれないが、情弱狩りや全く勉強しない人向けの動画とかでもよく言われていることである。
それはつまり……？何を意味しているのか。
・５のバチャコンについて
これはやった方がよかったかもしれない。
AtCoder は土日にしかコンテストが開かれないので、ABC しか出ない人はほぼほぼ週１しか実践日がない。
しかしこれだと "週に 1 回しか超苦しんで実装をする日" しかなく、初心者の人であるほど週一は効果が薄すぎると思う。
とにかく緑までは物量が大事だと思うので、最低でも週２で バチャコン＋ABC をした方がいい。
問題を沢山解くのが悪い事ではないが、適度に、適切に実践を挟んだ方がいいのは間違いない。
最近伸び悩んでいるのでバチャコンを挟んでみようと思う。
・６の音楽を聴きながら作業することについて
ぼく自身はあまり集中できなかったので聴いていない。
音楽を聴きながら作業することが多かったのだが、ABC は思考力も実装力も求められるレベルがとにかく高いので、音楽を聴くと集中力が下がってむしろ逆効果が多かった。
ASMR はよく聴く方なのだが、その ASMR の音すらも集中を妨げてしまう程。
なので集中できる人は聴けばいいし、ぼくみたいに集中できない人は聴かなければいい。
一応、以下の動画は集中力を妨げることはなく、むしろ高めてくれるから音楽を聴きたいけど聴けない！という人は試してみては如何だろう。
※休憩あり
・７の今後について
現時点で目指しているのは緑で、できれば青に行きたいなーなんて思っている。
「D 問題 100 題ちょっと解けば緑行けるっしょ！ｗ」と生意気ぶってるので、今は D を沢山解く方針に変えていこうと思う。
あと、茶色になったのは C を 100 題ちょっと解いたのも結構大きいと思う。
物量を熟すのは正義！ｗ（ただし質を維持した上である）
以上。
AtCoder 復習 1
参考：【解説 実況】ABC240 AからD【かつっぱ】 - YouTube
A,B は簡単すぎるので飛ばします。
ジャンプ問題。真偽値を持つ DP で解ける。
スタックを用いる。整数の個数を扱う際に [整数, 個数] と配列で管理する方法が賢すぎた。
pop() とかも忘れないようにしたい。(deque とかも似た操作だよね)
先頭に a を入れたり入れなかったりして文字列 S が回文なれば Yes
コーナーケース (only a) も考慮する必要があって実装がちょっと面倒。
おしりから考えるタイプの問題。文字追加を沢山行うため、リストを用いるよりかは deque を使うのがよい。
BFS練習
DP練習。部分和？というらしい。ガバガバコードでも通った。
B 問題だがやや難しい。
N 個みかんを選んだときに条件を満たすかどうかを全探索で調べていく。
while 文を使うと全探索がらくにできる。
解法はすぐ浮かぶが、実装を丁寧に行う必要がある。かも。
リストのおべんきょうが深まってるとらく。isupper とか islower を初めて知った。
def で無双しよう！
D問題は二分探索っぽいですが、実装が大変そうなので解きませんでした。水色diffだし無理して解く必要はないかなーと。
bit全探索！Cのbit全探索にしては実装がやや大変？
数学問題の中の整数問題。抽象的な等差数列を具体的に考えていく必要がある！
整数問題は (整数)×(整数)=整数 の形に持ち込めると強い。
数学力が要求される。包除原理を知ってるかどうか。
あと pow の使い方を知ってるかどうか。
DP問題。小さい順に実験していくと、過去の結果を利用できる。というわけでDPを実行。
包除原理
恐らく貪欲法
単品
itertools 練習
クエリによる文字列操作の典型問題に慣れよう。
数学問題？なのかよくわからん
2重ループで解けるが、どう実装するか問題
余事象を考えるタイプ
消すのは 0,1,2 個のいずれかになる。if 文のゴリ押しで解ける。が、きれいじゃない。
数学問題。N 個の点から 3 点選び、それが同一直線状に存在するかどうかを調べよ、というもの。
C - Sum of product of pairs ACコード(新) ACコード(旧)
数学問題？ΣΣAiAj を求める問題。ACコードが 2 つあるが、やっていることは同じ。
因みに解説は社長が行ったみたいです。
for 文と配列の超基本問題。B問題でもいい。
数学問題。座標 0 に到達できるかどうかを考えてから方針を分岐する。
越えられないならその座標を、越えられるのなら偶奇で分けて出力する。
bit全探索。だがちょっと難しい。二次元配列で考えるbit全探索なので、今まで一次元しか扱っていない人だと少し躓くかも。
基本的には考えられる全探索を行い、その各々のループについて全てのマスを全探索で調べればよい。
したがって、一次元は
for文(bit全探索開始！) → for文(条件を満たすか全探索開始！)
の二重だったが、本問は二次元配列なので
for文(行についてbit全探索開始！) → for文(列についてbit全探索開始！) → for文(行について条件を満たすか全探索開始！) → for文(列について条件を満たすか全探索開始！)
という四重ループを実装する必要がある。
実装力が要求される、気がする。小数点以下をどう処理するかが難しい。そこで replace() を使うという変態的発想で解ける。
bit全探索の超基本！やったことない人は本問を使うとよい。
D - I hate Factorization ACコード
A⁵－B⁵=X を満たす A,B∈ℤ をひとつでも求めればよい！
数学問題に見せかけて全探索で解ける、実装力要求タイプである。
クエリによる文字列操作に慣れよう！文字を追加する操作があるので、配列よりも deque を用いる方がよい。
数学問題？サイコロの期待値を求め、累積和を求める問題。慣れておきたい。
分裂した敵にも同じ行動を繰り返すので 2 倍して +1 する必要がある！
難易度は低いが、考察力が要求される。
最小公倍数 LCM を求める問題。
長さが与えられて三角形ができる個数を求める問題。
bisect を使うとよい。
D - Powerful Discount Tickets ACコード
heapq を使う。
BFS練習
bit全探索。やや難しいかも。
今まで解いた問題を列挙しただけで満足してしまった。定期的に復習しつつ、DPの理解度を深めつつ、様々なアルゴリズムを習得したい。
ACコードの殆どがきたなかったり、余計な部分を迂回していたり、簡略化できる部分もあると思いますが、温かい目で見守ってください（）
AtCoder 復習 1
参考：【解説 実況】ABC240 AからD【かつっぱ】 - YouTube
A,B は簡単すぎるので飛ばします。
ジャンプ問題。真偽値を持つ DP で解ける。
スタックを用いる。整数の個数を扱う際に [整数, 個数] と配列で管理する方法が賢すぎた。
pop() とかも忘れないようにしたい。(deque とかも似た操作だよね)
先頭に a を入れたり入れなかったりして文字列 S が回文なれば Yes
コーナーケース (only a) も考慮する必要があって実装がちょっと面倒。
おしりから考えるタイプの問題。文字追加を沢山行うため、リストを用いるよりかは deque を使うのがよい。
BFS練習
DP練習。部分和？というらしい。ガバガバコードでも通った。
B 問題だがやや難しい。
N 個みかんを選んだときに条件を満たすかどうかを全探索で調べていく。
while 文を使うと全探索がらくにできる。
解法はすぐ浮かぶが、実装を丁寧に行う必要がある。かも。
リストのおべんきょうが深まってるとらく。isupper とか islower を初めて知った。
def で無双しよう！
D問題は二分探索っぽいですが、実装が大変そうなので解きませんでした。水色diffだし無理して解く必要はないかなーと。
bit全探索！Cのbit全探索にしては実装がやや大変？
数学問題の中の整数問題。抽象的な等差数列を具体的に考えていく必要がある！
整数問題は (整数)×(整数)=整数 の形に持ち込めると強い。
数学力が要求される。包除原理を知ってるかどうか。
あと pow の使い方を知ってるかどうか。
DP問題。小さい順に実験していくと、過去の結果を利用できる。というわけでDPを実行。
包除原理
恐らく貪欲法
単品
itertools 練習
クエリによる文字列操作の典型問題に慣れよう。
数学問題？なのかよくわからん
2重ループで解けるが、どう実装するか問題
余事象を考えるタイプ
消すのは 0,1,2 個のいずれかになる。if 文のゴリ押しで解ける。が、きれいじゃない。
数学問題。N 個の点から 3 点選び、それが同一直線状に存在するかどうかを調べよ、というもの。
C - Sum of product of pairs ACコード(新) ACコード(旧)
数学問題？ΣΣAiAj を求める問題。ACコードが 2 つあるが、やっていることは同じ。
因みに解説は社長が行ったみたいです。
for 文と配列の超基本問題。B問題でもいい。
数学問題。座標 0 に到達できるかどうかを考えてから方針を分岐する。
越えられないならその座標を、越えられるのなら偶奇で分けて出力する。
bit全探索。だがちょっと難しい。二次元配列で考えるbit全探索なので、今まで一次元しか扱っていない人だと少し躓くかも。
基本的には考えられる全探索を行い、その各々のループについて全てのマスを全探索で調べればよい。
したがって、一次元は
for文(bit全探索開始！) → for文(条件を満たすか全探索開始！)
の二重だったが、本問は二次元配列なので
for文(行についてbit全探索開始！) → for文(列についてbit全探索開始！) → for文(行について条件を満たすか全探索開始！) → for文(列について条件を満たすか全探索開始！)
という四重ループを実装する必要がある。
実装力が要求される、気がする。小数点以下をどう処理するかが難しい。そこで replace() を使うという変態的発想で解ける。
bit全探索の超基本！やったことない人は本問を使うとよい。
D - I hate Factorization ACコード
A⁵－B⁵=X を満たす A,B∈ℤ をひとつでも求めればよい！
数学問題に見せかけて全探索で解ける、実装力要求タイプである。
クエリによる文字列操作に慣れよう！文字を追加する操作があるので、配列よりも deque を用いる方がよい。
数学問題？サイコロの期待値を求め、累積和を求める問題。慣れておきたい。
分裂した敵にも同じ行動を繰り返すので 2 倍して +1 する必要がある！
難易度は低いが、考察力が要求される。
最小公倍数 LCM を求める問題。
長さが与えられて三角形ができる個数を求める問題。
bisect を使うとよい。
D - Powerful Discount Tickets ACコード
heapq を使う。
BFS練習
bit全探索。やや難しいかも。
今まで解いた問題を列挙しただけで満足してしまった。定期的に復習しつつ、DPの理解度を深めつつ、様々なアルゴリズムを習得したい。
ACコードの殆どがきたなかったり、余計な部分を迂回していたり、簡略化できる部分もあると思いますが、温かい目で見守ってください（）
AtCoder 復習 1
参考：【解説 実況】ABC240 AからD【かつっぱ】 - YouTube
A,B は簡単すぎるので飛ばします。
ジャンプ問題。真偽値を持つ DP で解ける。
スタックを用いる。整数の個数を扱う際に [整数, 個数] と配列で管理する方法が賢すぎた。
pop() とかも忘れないようにしたい。(deque とかも似た操作だよね)
先頭に a を入れたり入れなかったりして文字列 S が回文なれば Yes
コーナーケース (only a) も考慮する必要があって実装がちょっと面倒。
おしりから考えるタイプの問題。文字追加を沢山行うため、リストを用いるよりかは deque を使うのがよい。
BFS練習
DP練習。部分和？というらしい。ガバガバコードでも通った。
B 問題だがやや難しい。
N 個みかんを選んだときに条件を満たすかどうかを全探索で調べていく。
while 文を使うと全探索がらくにできる。
解法はすぐ浮かぶが、実装を丁寧に行う必要がある。かも。
リストのおべんきょうが深まってるとらく。isupper とか islower を初めて知った。
def で無双しよう！
D問題は二分探索っぽいですが、実装が大変そうなので解きませんでした。水色diffだし無理して解く必要はないかなーと。
bit全探索！Cのbit全探索にしては実装がやや大変？
数学問題の中の整数問題。抽象的な等差数列を具体的に考えていく必要がある！
整数問題は (整数)×(整数)=整数 の形に持ち込めると強い。
数学力が要求される。包除原理を知ってるかどうか。
あと pow の使い方を知ってるかどうか。
DP問題。小さい順に実験していくと、過去の結果を利用できる。というわけでDPを実行。
包除原理
恐らく貪欲法
単品
itertools 練習
クエリによる文字列操作の典型問題に慣れよう。
数学問題？なのかよくわからん
2重ループで解けるが、どう実装するか問題
余事象を考えるタイプ
消すのは 0,1,2 個のいずれかになる。if 文のゴリ押しで解ける。が、きれいじゃない。
数学問題。N 個の点から 3 点選び、それが同一直線状に存在するかどうかを調べよ、というもの。
C - Sum of product of pairs ACコード(新) ACコード(旧)
数学問題？ΣΣAiAj を求める問題。ACコードが 2 つあるが、やっていることは同じ。
因みに解説は社長が行ったみたいです。
for 文と配列の超基本問題。B問題でもいい。
数学問題。座標 0 に到達できるかどうかを考えてから方針を分岐する。
越えられないならその座標を、越えられるのなら偶奇で分けて出力する。
bit全探索。だがちょっと難しい。二次元配列で考えるbit全探索なので、今まで一次元しか扱っていない人だと少し躓くかも。
基本的には考えられる全探索を行い、その各々のループについて全てのマスを全探索で調べればよい。
したがって、一次元は
for文(bit全探索開始！) → for文(条件を満たすか全探索開始！)
の二重だったが、本問は二次元配列なので
for文(行についてbit全探索開始！) → for文(列についてbit全探索開始！) → for文(行について条件を満たすか全探索開始！) → for文(列について条件を満たすか全探索開始！)
という四重ループを実装する必要がある。
実装力が要求される、気がする。小数点以下をどう処理するかが難しい。そこで replace() を使うという変態的発想で解ける。
bit全探索の超基本！やったことない人は本問を使うとよい。
D - I hate Factorization ACコード
A⁵－B⁵=X を満たす A,B∈ℤ をひとつでも求めればよい！
数学問題に見せかけて全探索で解ける、実装力要求タイプである。
クエリによる文字列操作に慣れよう！文字を追加する操作があるので、配列よりも deque を用いる方がよい。
数学問題？サイコロの期待値を求め、累積和を求める問題。慣れておきたい。
分裂した敵にも同じ行動を繰り返すので 2 倍して +1 する必要がある！
難易度は低いが、考察力が要求される。
最小公倍数 LCM を求める問題。
長さが与えられて三角形ができる個数を求める問題。
bisect を使うとよい。
D - Powerful Discount Tickets ACコード
heapq を使う。
BFS練習
bit全探索。やや難しいかも。
今まで解いた問題を列挙しただけで満足してしまった。定期的に復習しつつ、DPの理解度を深めつつ、様々なアルゴリズムを習得したい。
ACコードの殆どがきたなかったり、余計な部分を迂回していたり、簡略化できる部分もあると思いますが、温かい目で見守ってください（）
