yukicoder
Table of Contents
- 最終更新日
問題の解法・学んだことのメモを書きます。
1 difficulty1.5
1.1 No.882 約数倍数
期間が空いたのでうろ覚えだが約数列挙かな
制約が緩いので愚直にできそう
1.2 No.888 約数の総和
約数を列挙して総和をだす
1≤i≤N じゃなくて 1≤i≤√Nで良いぞってやつ
1.3 No.889 素数!
素数、平方数、立方数、完全数かをチェックする
制約が緩いので手動列挙して解いたが制約がきつくなった時にどうすべきかは考えておいても良いかも
2 difficulty2.0
2.1 No.3 ビットすごろく
すごろく最短解探索 幅優先探索
2.2 No.7 プライムナンバーゲーム
エラストテネスなんかで素数列挙しておいてからdpで勝敗を決める
素数列挙とgrundy数を組み合わせた良問
2.3 No.8 N言っちゃダメゲーム
n-1を言えば勝てるゲーム
ゲームの存在は知っていたが必勝法を忘れてて思いつかなかったので(じゃあダメじゃん(はい…))、LayCurseさんのyukicoder No.8 - N言っちゃダメゲーム
>「また，相手が何を言おうと，K+1 から相手が言った整数を引いた数をいうことができる．つまり，N−1−(K+1) を言えば，勝てる．と続けていくと，N mod (K+1) が 1 の時のみ後手必勝」
をみて解いた記憶がある 問題文にも書いてあるけど知識ゲー感
2.4 No.11 カードマッチ
包除原理を使った問題 数学
2.5 No.16 累乗の加算
x^10000000的なめっちゃ乗算する問題
解くだけだと思ったがx**iのような乗算方法だと計算時間を食いTLEするらしい
繰り返し二乗法なるものがあるらしいがPythonにおいてはpow()を使えば良いっぽい
余談だがpow()ってmodも取れるのね
2.6 No.36 素数が嫌い！
素因数分解して素数,1,使う数自身」以外で割り切れる整数かどうかを判定する
エラストテンネスで素数列挙しようとしたらMLEした
2.7 No.39 桁の数字を入れ替え
制約が緩いので全パターンを列挙して条件に合うもので最大のものを出力するだけ
itertoolsがすごいと、最初一番上の桁だけ入れ替えるプログラムを書いてWA出したのが反省点
2.8 No.44 DPなすごろく
dp典型 特に難しくなさそう
2.9 No.45 回転寿司
dp 続けて取れないので下のようになる
dp[i]=max(dp[i-2]+V[i],dp[i-1])
2.10 No.52 よくある文字列の問題
簡単そうに見えたけど意外と手間取った
bit全探索使って全パターンを作成してsetに入れて長さを取ればok
2.11 No.71 そろばん
全探索して探す問題 そんなに難しくない
2.12 No.675 テトラナッチ数列 Easy
メモ化再帰でするっと解ける 典型
2.13 No.786 京都大学の過去問
1段もしくは2段飛ばしのdp典型
ところでこれ本当に京都大学の過去問なんですか？
2.14 No.938 賢人を探せ
setとか使ってカンニングしていない人リストを作成する
余談だが、出力の際に整列をさせる必要があり上だとTLEする
下の方が in を使ってる分遅そうな気がするが…
多分remove()を使って要素が削除されるにつれ早くなるようにしているのだろう
このやり方は覚えておいて損がないかもしれない
# nocheater=sorted(set(nocheater),key=person.index)
# print(*nocheater,sep="\n")
for p in person:
if p in nocheater:
print(p)
nocheater.remove(p)
2.15 No.4 おもりと天秤
メモ化再帰でフィボナッチ数列作成