Huggingfaceのライブラリを使って分類器を作る時の流れと、jsonl形式のファイルを読む時の話（自分用メモ）
分類器を作る
1. データを精査する
カテゴリ数や文字数についての統計をとる
どのカテゴリを使うかを決める そのまま使うとヤバいカテゴリとかの問題を見つけ、除くか決める
2. 訓練用・テスト用データを作る
使うと決めたカテゴリをラベルとし、本文（"text"）とカテゴリ（"label"）のベアを抜いてきてcsvファイルにする
文章中からURLを抜いたり表記揺れを直したりする前処理を適宜行う
3. モデルを訓練する
使うモデル（AutoModelとかAutoModelForSequenceClassificationとか）、トークナイザ、データの準備、訓練のコンフィグとかを決めたらTrainerに投げる
jsonl形式のファイル
jsonl形式とは、jsonオブジェクトが改行区切りでたくさん並んでいるファイル形式。
ふつうのjsonファイルであれば、
with open("hoge.json", "r") as f: L = json.load(f)
みたいにできると思う。json.load()は、ファイルオブジェクト型を引数にとる。
しかし、jsonl形式のファイルを上のようにjson.load()しようとすると、多分Extra data: line 2 column 1みたいなエラーが出るはず。
なので、それを防止するための方法が2通りある。
一つは、jsonl形式のファイルを一行ずつ読み取り、それをjson.loads()という、文字列を引数にとってjson形式だと解釈するみたいな関数を使う。（loadsの"s"はstringのs）
with open("hoge.json", "r") as f: temp = f.readline() # 1行読み込み fuga = json.loads(temp) # fugaに1つのjsonオブジェクトが代入される
もう一つは、JSONDecoder()クラスのクラスメソッドであるJSONDecoder.raw_decode()を使う方法がある。
decoder = json.JSONDecoder() with open("hoge.json", "r") as f: temp = f.readline() # 1行読みこみ fuga = decoder.raw_decode(temp) # タプルで帰るので、fuga[0]が所望のjsonオブジェクト
蜘蛛の糸 SSS
蜘蛛の糸 鳥です 15初鳥で本当に嬉しい
調整してないのに超ギリギリで草 最後の片手トリル＋エアーで赤出まくってビビっちゃった
以下注意したところを書きます
（譜面の出典：https://sdvx.in/chunithm/07/07074mst.htm）
12~16小節
ド初っ端から最難所。
下の図で緑色の線で囲ったところがメチャクチャattack出やすい。（自分が早く押し過ぎているのか巻き込んでいるのかは不明。右利きなので右手側は全然出ないんですけど......）
使う指は人差し指と薬指だけにして、少し膝を曲げて背中を逸らし、視線をいつもより低く＋遠くすると割と解決しました（なんで？）。
運指を考えるのが最強の攻略法だと思っていたけど、視線もしくは姿勢を変えるとうまくいく可能性があるということに気づきました。新千年女王の縦連は膝を曲げると力が入って安定しやすいみたいな。
16~19小節
難所その2。軸が意味不明なので下の図みたいに交互で取ります。あと姿勢を普通に戻すのも忘れずに。
左手を早く離しすぎるとスライドの終点でアタックめっちゃ出るので注意します。
23~31小節
難所その3。
タップを取る指を親指＋人差し指に限定して、タップが流れている時には手を動かさないようにして巻き込まないように注意します。
もう一点注意すべきはホールドの終点で、ホールドが終わるまで手を動かさないようにします。（n敗）
31~39小節
難所その4。というかもうここ乗り越えると15じゃないです。
5鍵がこんなに延々と続くので指で押せるわけがないです。
なので片側にくの字で寄った時だけ指で真面目に押して、そうでない折り返しはゆっくり分業しながら擦ります。
コツはないのでアタック出ないようにお祈りしながら慎重に誤魔化しながら擦るだけです。てかここマジで何なんだよ 押せるわけないだろ
39~45小節
誘導に沿って取ります。右手をタップ、左手をエアー＋スライドで分けてとります。リズム慣れればそうでもないです。
前半の片手トリルは3つ、後半は5つというのを覚えておくと楽。
47~53小節
39~45小節のに似ているんですけど、これを誘導通りに取ろうとするとエアーの着地が前のやつより早くて険しかったので、ちょっと工夫します。
何か色々書いてあるんですけど、結局はホールドの始点とタップが
・ホールドの始点とタップが隣接しているトリルは両手で処理
・ホールドの始点とタップが隣接していないトリルは片手で処理
という違いだけです。
残り
サビの局所難は気合で処理。最後のタップとエアーは分業します。てか前半に難所が凝縮しててウケる
雀魂で金の間に上がるには
※四麻で金の間に上がったので、銀の間を東風戦で突破するのに必要だと思ったことのみを書きます。上級者から見ればちゃんちゃらおかしい内容だったり、不正確な内容が含まれている場合があります。
3行で
以下の二点を徹底すれば大丈夫
1. 他人にリーチをかけられたら問答無用でオリる（ベタオリ）
2. 他人より先にリーチがかけられるなら即座にリーチをかける
1.他人にリーチをかけられたら問答無用でオリる
平均して9~12巡目で誰かがリーチをかけるか、もしくはテンパイの状態になります。「ベタオリ」で調べるといくらでも情報が出てくると思いますが、
・現物（相手の河に存在する牌）
・6巡目までに捨てられた数牌に隣接する数牌
・既に出ている字牌（最悪出ていなくても）
・中スジ（一萬と七萬が捨てられていれば四萬など）
・リーチ後に他人が捨てた牌
あたりを切っていれば90%くらいは安心だと思います。
イーシャンテンでドラが3枚ある！ でもリーチかけられた！ アガると12000点くらいかな……
→オリましょう。倍満放銃したら目も当てられません。
役満チャンス来た！ でもリーチかけてる人がいるけど……。
あくまで得点の期待値的な話でオリた方がいいんじゃないのと言っているので、32000点とか見込めるチャンスをみすみす逃すのはもったいないと思います。個人的にはそういう（役満とかの）レアなケースであれば追いかけてリーチをかけると思いますが、あくまで自己責任です。レートを70とか溶かすリスクを背負いたくなければオリるといいんじゃないでしょうか。
2.他人より先にリーチがかけられるなら即座にリーチをかける
六巡目までとかかなり早い段階でリーチがかけられるなら、たとえドラがなかったり単騎待ちとかであったとしてもリーチをかけるといいと思います。多少放銃に敏感な人が相手ならベタオリしてくれるでしょうし、放銃率18%とかの相手がいるならカンチャン待ちの三索とか余裕で捨ててくれます。
手を進めるのが遅くなったとしても、他人より先にリーチがかけられるシチュエーションならリーチをかけると良いです。リーチかけて上がればオマケの役（ツモや一発、ハイテイやチャンカン、リンシャンなど）がついて2飜以上になる可能性が高くなるので、リーチをかけること自体メリットがたくさんあります。
その他
・そもそもリーチかける以前にアガれないけど……
配牌時点で手元に役牌が2枚あり、ドラが2枚以上あるなら早めに鳴いて役を確保するようにしています。アガりが早くなるし、4000点くらいは見込めます。そうでなければ鳴かずに粛々と手を進めましょう。
・牌の切り方
1枚しかない字牌→浮いている一もしくは九→孤立牌
の順で切るようにしています。その他四連形や中ぶくれ形は大切にします。
・4位を回避する、2位以上になる
そもそも「他人にリーチをかけられたら問答無用でオリる」「他人より先にリーチがかけられるなら即座にリーチをかける」の二点が大切だと思ったのはなぜかという話です。
・ベタオリ
このゲームでレートを上げるには2位以上（運が良ければ3位でも）になる必要がありますが、4位になると溶かしたレートを取り返すために1位を1回もしくは2位を2回以上取る必要があり、非常に大変です。上のベタオリは4位を回避するために必要です。
雀士3に上がった時に相手のリーチに放銃しまくって一時期レートが70まで落ちました。
・リーチ
東風戦で2位以上になるためには、誰か一人が大勝ちするという状況を除いて、「4000点くらいの役で一回アガり、かつ一度も放銃しない」もしくは「一回放銃するが、満貫以上の役で一回アガる（8000~12000点くらい）」が基本的なストラテジーとなります。両方に共通するのは「一度以上アガること」であり、そのために他人より先にリーチをかけてアガりに最も近い場所にいること自体が重要になります。
写真
撫子すし
TED Talks
https://www.ted.com/talks/fabio_pacucci_could_we_harness_the_power_of_a_black_hole?language=ja
https://www.ted.com/talks/john_soluri_the_dark_history_of_bananas?language=ja
https://www.ted.com/talks/claire_wardle_can_you_outsmart_a_troll_by_thinking_like_one?language=ja
https://www.ted.com/talks/laurence_hurst_is_human_evolution_speeding_up_or_slowing_down?language=ja
https://www.ted.com/talks/iseult_gillespie_the_japanese_folktale_of_the_selfish_scholar?language=ja
https://www.ted.com/talks/matt_walker_6_tips_for_better_sleep?language=ja
https://www.ted.com/talks/michael_corballis_evolution_s_great_mystery_language?language=ja
https://www.ted.com/talks/lucy_cooke_no_one_can_figure_out_how_eels_have_sex?language=ja
https://www.ted.com/talks/alex_gendler_the_egyptian_myth_of_the_death_of_osiris?language=ja
https://www.ted.com/talks/pratik_aghor_the_greatest_mathematician_that_never_lived?language=ja
https://www.ted.com/talks/cameron_morin_what_do_all_languages_have_in_common?language=ja
https://www.ted.com/talks/dan_kwartler_how_fast_can_a_vaccine_be_made?language=ja
https://www.ted.com/talks/judy_grisel_how_does_alcohol_make_you_drunk?language=ja
https://www.ted.com/talks/noah_charney_the_art_forger_who_tricked_the_nazis?language=ja
https://www.ted.com/talks/anees_bahji_what_is_schizophrenia?language=ja
https://www.ted.com/talks/jay_van_bavel_do_politics_make_us_irrational?language=ja
https://www.ted.com/talks/alex_gendler_epic_engineering_building_the_brooklyn_bridge?language=ja
https://www.ted.com/talks/michael_r_stiff_why_is_cotton_in_everything?language=ja
https://www.ted.com/talks/chris_a_kniesly_how_corn_conquered_the_world?language=ja
https://www.ted.com/talks/jean_baptiste_p_koehl_why_are_earthquakes_so_hard_to_predict?language=ja
https://www.ted.com/talks/stacie_bosley_how_to_spot_a_pyramid_scheme?language=ja
https://www.ted.com/talks/netta_schramm_why_don_t_perpetual_motion_machines_ever_work?language=ja
https://www.ted.com/talks/helen_m_farrell_what_is_bipolar_disorder?language=ja
https://www.ted.com/talks/eleanor_nelsen_would_you_sacrifice_one_person_to_save_five?language=ja
https://www.ted.com/talks/kostas_karpouzis_can_machines_read_your_emotions?language=ja
https://www.ted.com/talks/sara_garofalo_the_psychology_behind_irrational_decisions?language=ja
https://www.ted.com/talks/mia_nacamulli_what_would_happen_if_you_didn_t_drink_water?language=ja
https://www.ted.com/talks/courtney_stephens_a_brief_history_of_melancholy?language=ja
https://www.ted.com/talks/kelli_sandman_hurley_what_is_dyslexia?language=ja
チュウニズム クリスタル（プラス）までを振り返って
ベスト枠平均が15.8343でした。去年の12月にはMAX15.8を達成しました。
ベスト枠詳細↓
下限から15.7を追い出したりして、ゆっくりながら(この一年で700クレやっていました)まあまあ成長できたかなあとは思います。
11月にリングフィットアドベンチャーをやり始めてからは特に成長した気がします。筋肉がついて多少のことでは腕がへこたれなくなったり、指先に力が入るようになってそれなりに正確にノーツを押せるようになったことが原因かと思います。
正直初めて一週間くらいで神威が7200出たのはびっくりしたし、この曲は腕にどれだけ力を入れ続けられるかの（瞬発力よりは）持久力をかなり問うてくる曲だと思います。
しかし未だに京急はSSSが取れません。どうして…………………………………………………………………………………………………………………………
次回作のチュウニズムパラダイスも楽しみです。
Pythonの深さ優先探索で失敗した話
ハミルトン閉路が存在するか判定する問題。入力は、
n m
x_1 y_1
x_2 y_2
... ...
x_m y_m
で与えられる。（nは頂点数、mは辺の数。x_i,y_iは頂点x_iとy_iを結ぶ辺が存在することを表す）
#合ってるコード(しかしこれもn=15くらいだと落ちるね......) n,m = map(int,input().split()) edge = [] for i in range(n): T = [0]*n edge.append(T) for i in range(m): x,y = map(int,input().split()) edge[x][y] = 1 edge[y][x] = 1 def dfs(cur, checked, rest): #curは現在いる点、checkedは訪れた点、restはこれから訪れる点 if len(rest) == 0: if edge[cur][0] == 1: #全点探索が終了したら、現在いる点と点0の間に辺があるかどうかを判定 print('Yes') exit() else: for i in range(n): if edge[cur][i] == 1: if (i in rest) and (i not in checked): L = [] for j in range(len(rest)): if rest[j] != i: L.append(rest[j]) temp = [i] for j in range(len(checked)): temp.append(checked[j]) #ここcopyに注意 dfs(i, temp, L) P = [i for i in range(1, n)] #これから訪れる頂点のリスト dfs(0, [], P) #点0からスタート print('No')
間違えた理由はいくつかあって、まず
・dfsを同じ深さのfor文でやると、前の処理がそのまま後ろのfor文に引き継がれる（同時並行で進むわけではない）
・pythonの = は参照渡し（なので値だけコピーしたいならdeepcopyを使わないといけないけど、deepcopyはバカ遅い）
#間違っているコード n,m = map(int,input().split()) edge = [] for i in range(m): s,e = map(int,input().split()) edge.append([s,e]) def dfs(cur, checked, rest): if len(rest) == 1: flag = False for i in range(len(edge)): if edge[i][0] == 0: if edge[i][1] == rest[0]: flag = True break elif edge[i][1] == 0: if edge[i][0] == rest[0]: flag = True break if flag: return True else: return False else: flag = False for i in range(len(edge)): temp = checked if edge[i][0] == cur: if edge[i][1] in rest: if edge[i][1] not in checked: flag = True L = [] for j in range(len(rest)): if rest[j] != edge[i][1]: L.append(rest[j]) temp.append(edge[i][1]) return dfs(edge[i][1], temp, L) elif edge[i][1] == cur: if edge[i][0] in rest: if edge[i][0] not in checked: flag = True L = [] for j in range(len(rest)): if rest[j] != edge[i][0]: L.append(rest[j]) temp.append(edge[i][0]) return dfs(edge[i][0], temp, L) if not flag: return False P = [i for i in range(1, n)] if dfs(0, [], P): print('Yes') else: print('No')
復習 4/18,4/19
O(n)で前計算することで、各nCrをO(1)で求められるようにする。
mod = 10**9+7 MAX = 10**5+1 #nは10**5までを想定 fact = [1]*(MAX+1) for i in range(1, MAX+1): fact[i] = (fact[i-1]*i)%mod inv = [1]*(MAX+1) for i in range(2, MAX+1): inv[i] = inv[mod%i]*(mod-mod//i)%mod fact_inv = [1] * (MAX + 1) for i in range(1, MAX + 1): fact_inv[i] = fact_inv[i-1]*inv[i]%mod def comb(n, r): if n < r: return 0 return fact[n]*fact_inv[n-r]*fact_inv[r] % mod
atcoder.jp
例えば(10**5)**(10**5)を10**9+7で割りたい、みたいな気持ちになった時に、for文で10**5を10**5回回してるとどエライ事になってしまう。a**bをmで割った余りは、pow(a,b,m)で高速に求められる。
atcoder.jp
ナップサックはi番目のものまで見たときに使う、使わないのふた通りの場合分けをちゃんと行うこと。サボるとどっかでミスる。
復習 4/9,4/10,4/11
1からkまでのiに対して、
・「i回目に働くのは一番早くて何日目？」
・「i回目に働くのは一番遅くて何日目？」
というのを格納した配列A,Bを考える。いずれも、oxの列を前から、後ろから見ていくことで可能。
結論から言うと、A,Bについて、A[i] == B[k-i-1]となる日付が「働くべき日」に該当する。
例えば、ooxoxoxoという配列で、「必ず1日以上開けて働かなくてはいけない」という制約をつけたらどうだろうか。
働く日数が二日であれば、上の配列はそれぞれ、
[0,3]
[5,7]
となることだろう。1回目に働くのは、遅くとも5日目に働けばいい。そう考えると、0,1,3日目に働く必要はない。同様に、0日目に働いてもいい。そうすれば、5日目を待たずとも二回仕事を終えることもできる。
以上より、「必ず働く日」というのは存在しない。
働く日数が三日であれば？ 配列はそれぞれ、
[0,3,5]
[7,5,3]
となる。この場合も、実は働くべき日は存在しない。2回目に働く日は3,5日目のいずれかから選ぶことができるし、選んだ日付によって、例えば2回目に働く日を3日目にすれば、1回目、3回目に働く日はそれぞれ0と(5,7)日目になるし、5日目を選べば、1回目、3回目に働く日はそれぞれ(0,1,3)と7日目になるからだ。
最後に、働く日が四日であれば、配列は
[0,3,5,7]
[7,5,3,1]
になる。この時、最初に働く日付のみが問題になり、後の3,5,7日目については必ず働かなくてはならない。（A[i] == B[k-i-1]なので）
ということで、この場合は3,5,7日目となる。
累積GCDまでは思いついたが......という感じ。前から累積GCD取って、各クエリごとに「初めてGCDが1になるところはどこか？」を二分探索すればO(QlogN)で求まる。GCDが1にならないなら配列の最後とのGCDを求めてあげればいい。
部分列の和を求めるのはわかる。bitがk個以上立っている桁を大きい方から取ればいいのもわかる。しかし大きなbitがk個以上立っているものをまたかき集めて、その中から次の桁のbitが立っているものを選んで......とやっていると日が暮れるので、視点を「n(n+1)/2個部分和」ではなく、「k個選んできた後の論理積の最大値」に移す。これをxとすれば、二進法で表した時にたかだか40通りなので、各bitについて立てるか立てないかを、bitの大きい方から検討していけば良い。
具体的に言えば、ans = 0として、
ans = 0 for i in range(40, -1, -1): temp = ans+2**i cur = 0 for j in range(len(list_sum)): if temp&list_sum[j] == temp: cur += 1 if cur >= k: ans += 2**i
（擬似的なコードなので粗はあるけどこんな感じ）
上のような実装をしてあげればいい。ansについては過去の結果を持ち越すことになるので、「上からbitがk個以上立っている集合を選んできて、その中でまたk個以上立っているような下のbitを選んでくる」のようなことができていることになる。
めっちゃ賢い......
「ペア」なので、必ず二つの要素の組で考える。
大きい方から貪欲に、「ペア」を作れる相手を取ることを考える。（降順で固定する）
大小関係をつけることでわかることがある。例えば、今見ている要素pに対して、相手となる要素q（p>qとする）を取ってきた時、p+q=2^kとなるような2^kは、確実に2^(k-1) <= p < 2^kを満たしている。
ペアの和が2^kよりも大きい2のべき乗になることはない。例えばp<2^kとして、q = 2^(k+1)-pとすれば、p>qよりp > 2^(k+1)-pとなるので2p > 2^(k+1)となり、p>2^kから矛盾が生じる。よって、p+qでできる二のべき乗は、pより大きくて、そのなかで最も小さいような2^kに限られる（ここに気付けるかが肝心）
ここまでくれば大体OKだが、相手となる要素の個数を管理するのにpythonではCounterという便利なデータ構造がある。
例えば
from collections import Counter L = [3, 11, 14, 5, 13, 3] C = Counter(L) #Counter({3: 2, 5: 1, 11: 1, 13: 1, 14: 1}) #C[3] = 2 #C[14] = 1
となる。これを使うことで、delete()などを使わなくても要素数を減らす操作が簡単にできる。
復習 4/2,4/3
必勝法ゲー。dpで遷移を見る。「j枚目で回ってきたときに勝てるか？」をdp[j]で管理する。
取れる枚数がn種類（a_1...a_n）あったとき、dp[j-a_i]が全て「win」であれば、必ず相手に「勝てる」状態で回してしまうことになるため、dp[j] = lose
逆にdp[j-a_i]がLoseになるものが一つでもあれば、相手に「負け」の状況を押し付けることができるのでdp[j] = winとなる。
BITを真面目に使った初めての問題。文字を入れ替えたら、BITの情報だけでなく元の文字列の情報も更新するのをお忘れなく
巡回セールスマン問題。これ始点を0に固定しているけど、どの頂点から出発したとしても、必ず0は通るわけで、そのあとの道のりは全く同じになるので、別に頂点0にスタートを固定しても問題はなさそう。
すなわち、頂点i~頂点0(経路A)→頂点0~頂点i（経路B)は、B→Aとしても最小コストが変わらない。
v,e = map(int,input().split()) #v:頂点, e:辺 graph = [[] for i in range(v)] cost = [[float('inf')]*v for i in range(v)] for i in range(e): x,y,z = map(int,input().split()) cost[x][y] = z dp = [[float('inf')]*v for i in range(1<<v)] #(1<<v)-1 == 2**v-1 dp[(1<<v)-1][0] = 0 #全ての頂点を訪れて帰ってきた時（ここがゴール） for i in range(2**v-2, -1, -1): #まだ見ていない頂点集合に対して for j in range(v): #現在いる頂点から for k in range(v): #次に行く頂点について if i>>k & 1 != 1: #まだ訪れていないならば dp[i][j] = min(dp[i][j], dp[i|1<<k][k]+cost[j][k]) #dp[i|1<<k]は「kを訪れた状態」を指す。 #視点を変える。「今kにいる状態からゴールに至るのに必要なコスト」+「j→kに必要なコスト」は、 #「今jにいる状態からゴールに至るのに必要なコスト」になる（遡る） #これを「今0にいる状態からゴールに至るのに必要なコスト」まで遡って計算する。 if dp[0][0] != float('inf'): print(dp[0][0]) #まだどこも訪れていない状態から、ゴールである0を目指して進む else: print(-1)
シフト演算子が結構便利であることに気づいた。
復習 3/31,4/1
まずは美味しい順にソートして上からK個取る。そこから、残りのN-K個のうちでどれかと交換することで満足度が上がるかどうかを見ていくわけだが、この時、すでに取っているネタの種類がi種類であれば、そこから種類を減らすことによって満足度は決して上がらない。
何故ならば種類は多いほど満足度が上がるし、そもそも最初にK個選んだ時点で美味しい順に取っているので、i未満の種類を選ぶことによって純粋な「美味しさの和」を上昇させることが不可能なためである。
したがって、ここから
１、種類を減らさずに（★逆に言えば、現時点で食べようと思っている寿司の中にないネタを選んで）
２、交換することで満足度が上昇するか
についてを、残りのN-K個の寿司について考える。（N-K個も美味しい順にソートしておく）
交換するのは、現時点で食べようと思っている寿司のうち、同じ種類のものが二つ以上あるものに限る。なぜなら、今確保している寿司よりも、残りのN-K個の寿司の方が美味しさが小さいため、純粋な一種類・一個の寿司のトレードで満足度を向上させられない（種類ボーナスは増えないし、美味しさが減るだけ）からである。
これを、現状2個以上残っている寿司の美味しさをheapqで持っておき、新たな寿司のネタと交換することで、美味しさを増やせるかどうかを見るだけ。種類が多くなればなるほど満足度が増える訳ではないことに注意。
閉路検出。BFSするだけだけどもっとマシなコード（実装法）が知りたい。
n,m = map(int,input().split()) graph = [[] for i in range(n)] for i in range(m): u,v = map(int,input().split()) graph[u-1].append(v-1) graph[v-1].append(u-1) visited = [0]*n ans = 0 start = 0 while sum(visited) != n: while visited[start] == 1: start += 1 stack = [start] flag = True while len(stack) != 0: t = stack.pop() if visited[t] == 0: visited[t] = 1 for j in range(len(graph[t])): if visited[graph[t][j]] == 0: if graph[t][j] not in stack: stack.append(graph[t][j]) else: flag = False if flag: ans += 1 print(ans)
完全グラフから、nがoddなら[1,n-1]...を、nがevenなら[1,n],[2,n-1]...を除けばいい
は？？？？？
縦方向と横方向を一緒くたに考えようとすると混乱するので分解する。
とにかく「ゲーム終了時に盤面上に残っているには、最初にどこに駒があればいいのか？」を考えるため、操作を逆順に遡っていく。
先攻は「範囲を狭めようとする」動きをするのであんまり考えなくていいが、後手が結構ややこしい。
例えば、縦方向に見ていて先手を見終わって範囲が[2,3]だった時に（範囲は1~hとする）、後手が"D"を持ってきたら、後手がDを出して[2,3]の範囲に居られるようにするためには、後手の行動前に駒が[1,2,3]のどこかにいなくちゃいけないな〜みたいに、「後手が行動する前に駒はどこにあるべきか？」を考える。
セグメント木、BIT（反転数）
・セグメント木
書きようによっては任意の区間のGCDを求めたりもできるっぽいけど、とりあえずは任意の区間の最小値を求めることにする。
n = int(input()) #配列の要素数をnと置く。 L = list(map(int,input().split())) #配列 t = 1 while t <= n: t *= 2 segtree = [float('inf')]*(t-1) #tはn以上で最小の2のべき乗の数 def init(LIST): for i in range(n): segtree[i+n-1] = LIST[i] #配列のi番目をセグ木のi+n-1番目（葉）に格納 for i in range(n-2, -1, -1): segtree[i] = min(segtree[2*i+1], segtree[2*i+2]) def update(k, a): #k番目（0-indexed）の値をaに変更 k += n-1 segtree[k] = a while k > 0: k = (k-1)//2 segtree[k] = min(segtree[2*k+1], segtree[2*k+2]) def query(a, b, k, l, r): #[L[a],L[b])の範囲の最小値を求める。kは今見ている節点の番号、l,rはkの対応している範囲を表す。 #L[a]~L[b]の最小値を求めたければ、query(a,b+1,0,0,n) if r <= a or b <= l: #求める場所が範囲外 return float('inf') elif a <= l and r <= b: return segtree[k] else: u = query(a, b, 2*k+1, l, (l+r)//2) v = query(a, b, 2*k+2, (l+r)//2, r) return min(u, v) init(L) print(segtree) while True: i,p,q = map(int,input().split()) #i==1でL[p]~L[q]のminを求める。i==2でL[p]をqに変更 if i == 1: print(query(p, q+1, 0, 0, n)) elif i == 2: update(p, q) print(segtree) else: break
実行例
>>8 >>5 3 7 9 6 4 1 2 [1, 3, 1, 3, 7, 4, 1, 5, 3, 7, 9, 6, 4, 1, 2] >>2 0 2 #L[0]を5から2に変更 [1, 2, 1, 2, 7, 4, 1, 2, 3, 7, 9, 6, 4, 1, 2] >>1 0 0 #L[0]の値 2 >>1 0 3 #L[0]~L[3]の最小値 2 >>1 0 7 #L[0]~L[7]の最小値 1 >> 1 4 3 #範囲が前後する inf
・BIT
任意の区間の和を求めることができる嬉しい配列。
n = int(input()) #配列の要素数をnと置く。 L = list(map(int,input().split())) #配列 BIT = [0]*(n+1) #1-indexed def sum_1_to_i(i): #L[1]~L[i]の和を求める ans = 0 while i > 0: ans += BIT[i] i -= i & -i #ビットが立っている最下位の桁を0に return ans def update(i, x): #L[i]にxを加算する while i <= n: BIT[i] += x i += i & -i return for i in range(n): update(i+1, L[i]) print(BIT) while True: i,p,q = map(int,input().split()) if i == 1: print(sum_1_to_i(q)-sum_1_to_i(p)) else: break
実行例
6 1 2 3 4 5 6 [0, 1, 3, 3, 10, 5, 11] >>1 3 6 #4+5+6 15 >>1 2 6 #3+4+5+6 18 >>1 0 3 #1+2+3 6 >>1 0 6 21
・1~nを適当に並べた配列における反転数（バブルソートの回数）を求めるコード
※反転数＝バブルソートの回数なのは、①一回の入れ替えで反転数は-1、②昇順に並んでる時の反転数は0、の二つから従う。
n = int(input()) #配列の要素数をnと置く。 L = list(map(int,input().split())) #配列 BIT = [0]*(n+1) #1-indexed def sum_1_to_i(i): #L[1]~L[i]の和を求める ans = 0 while i > 0: ans += BIT[i] i -= i & -i #ビットが立っている最下位の桁を0に return ans def update(i, x): #L[i]にxを加算する while i <= n: BIT[i] += x i += i & -i return times_of_swap = 0 for i in range(n): times_of_swap += i-sum_1_to_i(L[i]) update(L[i], 1) print(times_of_swap)
参考：
転倒数 - 個人的な競プロメモ
復習 3/30
逆元使ってn_C_k（を10**9+7で割った余り）を高速で求める、それはそうみたいな問題なんだけど、流石にテンプレをペタって貼り付けてn=10**5,kを1~10**5まで計算するのはしんどい（factorialの都合上）
n_C_k-1からn_C_nまでを一気に求める問題であれば、以下のような実装でまあなんとかなる。（色々杜撰なのは多めにみてね）
n = 10, k = 3なら、2C0, 3C1,...,9C7まで求めることになる
import math mod = 10**9+7 n,k = map(int,input().split()) #n_C_kのn,k a = math.factorial(k-1)%mod b = math.factorial(k-1)%mod c = 1 fact = [0]*(n-k+1) <s>#fact[j]は、n_C_(j+k-1)を表す</s> for i in range(k-1, n): if i == k-1: fact[0] = (a*pow(b*c, mod-2, mod))%mod else: a = a*i%mod #前の結果を再利用 c = c*(i-k+1)%mod #前の結果を再利用 fact[i-k+1] = (a*pow(b*c, mod-2, mod))%mod
i番目の鍵を使うか？でDPを行う。また、dp[i][j]について、iは「i番目までの鍵を見た（使った、使わないは無視）」、jは0から2**n-1までの値を取り、「二進数に直した時にビットが立っているところは、宝箱が空いている」とみなす。
例えば宝箱が3つあり、dp[3][6]であれば、「3番目の鍵まで見て、6→110、つまり箱1,2が空いている状態において、最小のコスト」が入るようにする。
dp[i][j]の遷移についてだが、まずi番目の鍵を使わないのであれば、開く箱はi-1番目の鍵を見た時と変化がないので、dp[i][j] = dp[i-1][j]となる。
i番目の鍵を使うのであれば、
dp[i][j|key[i][1]] = min(dp[i][j|key[i][1]],dp[i][j]+key[i][0]) #j|key[i][1]はor演算子を使っている。dp[i][j]までで開いている箱に、新たに鍵iを使った時に開く箱の状態に遷移した時、その鍵を使った方が最適かどうかを判断している。
という式で遷移が書ける。
最後にdp[m-1][2**n-1]を出力してあげればいい。（全部開けられないかの判断もここでする）
計算量は、鍵1~mを開けるか否かについてと、それについての0~2**n-1通りの箱の開き方があるのでO(m*(2**n))。
これ1000人も通してたってマ？
いもす法で前から見ていくのだが、区間全部の累積和を取るのではなく、「爆発の及ぶ範囲」の端と橋をプラス、マイナスしておいて、今見ているところの累積和s[i]がモンスターの体力h[i]以上であれば爆発せずに次へ、小さかったら足りない分だけ爆発させて右端（爆発の及ばないところ）にマイナスし、s[i+1]にs[i]で与えた分だけ増やす、という方式を繰り返す。
例で言えば、例えば爆発の及ぶ距離が左右に2、爆発のダメージを2として、
[1,2,5,9,11]
という位置にいるモンスターが
[10,12,8,14,9]
という体力を持っていたとしよう。
s = [0,0,0,0,0,0]（一つ多く取っておく。s[i]にi番目のモンスターに与える累積ダメージが後々入ることになる）
まず、最初に1にいるモンスターを左端と見て、ここを爆発させると位置2,5のモンスターも巻き添えを食らう。位置1にいるモンスターを倒すには10のダメージ（爆発5回）が必要で、これを表した状態は、
s = [10,0,0,-10,0,0]
となる。
次に進む前にs[1] += s[0] をするので、
s = [10,10,0,-10,0,0]
となる。
次に、距離2にいるモンスターに着目すると、現在与えられているダメージはs[1]=10で、倒しきるのにあとダメージが2（爆発が1）必要である。
ここを左端にして爆発させると、巻き添えを食らうモンスターは位置5のみ。（位置5はもう倒してるけどそれは放っておく）
というわけで、一回爆発させた状態を表現した配列sは、
s = [10,12,0,-12,0,0]
となる。
次に進む前にs[2] += s[1] をするので、
s = [10,12,12,-12,0,0]
となる。
次は距離5にいるモンスターだが、s[2] > h[2] = 8なのでもう爆発させる必要がない。
というわけで次に進むので、s[3] += s[2]をして
s = [10,12,12,0,0,0]
となる。（ここで、s[3]の累積ダメージが0になっていることに着目したい。s[3]を見るまでs[3]に入っていた値は累積ダメージを表現していなかったが、前から累積和をとることによって、s[3]を見る時にはうまく帳尻があう（正確なダメージが入る）事になる）
次に距離9にいるモンスターに注目する。現状、累積ダメージは0なので、7回の爆発（ダメージ14）が必要である。この爆発で、距離11にいるモンスターも巻き添えを食らうので、配列sは
s = [10,12,12,14,0,-14]
となる（配列の要素を一つ余分に取っておいたのがここでうまく作用する）
次に進むので、s[4] += s[3]をして、
s = [10,12,12,14,14,-14]
となる。
最後にs[4]だが、s[4] > h[4] = 9なのでもう爆発の必要はない。よってs[5] += s[4]をして、
s = [10,12,12,14,14,0]
となり、これで全部倒し切って終わり。O(N)で十分間に合う（ぶっちゃけ計算量的には前処理のソートの方が支配的）
復習 3/26, 3/27
桁DP的な発想 解説読んでパッと理解できなかった
これも桁DP的発想
提出した後で「2,8とかの組み合わせの時無理じゃね？」とか気付く。ちゃんと考察をしましょう。
グラフの用語を知った。
・直径：一番遠い点間の距離
・二部グラフ：二つのグループに分けられるグラフ。グループAはグループBの頂点としか繋がっておらず、逆も然り。例えば三角形に頂点が並んでいるグラフは二部グラフではないが、四角形に並んでいたら二部グラフ。二部グラフの時、隣接する頂点のグループ番号を偶数、奇数、偶数、奇数……と交互にできる。
とにかく桁数がデカけりゃデカいほど強いので、それを目標にしてまずはDPで「マッチ棒ビッタリ使った時に最大何桁作れるか？」を求める。そしてそれが求まったら、dpの最後から遡ってどういう数字を各桁に割り当てればいいかを求める。賢い。
結局は高校数学。1<=i<=kのそれぞれのiに対して、(n-k+1_C_i)*(k-1_C_i-1)を求めてあげればいいだけの話。考え方は「最初に赤いボールn-k個を並べて、①その間のi個のどこにボールを入れるか、②その場所に何個のボールを入れるか、の二つをかけたもの」
逆元の求めかたを、例外処理（例えば4C6なんてのは存在しない）も入れて書き直した。
import math mod = 10**9+7 def comb(p,q): if p >= q: a = math.factorial(p)%mod b = math.factorial(q)%mod c = math.factorial(p-q)%mod return ((a*pow(b*c, mod-2, mod))%mod) else: return 0
どうでもいいけどn=10**3くらいだったらpythonの方が早そう
二分探索と、「二つの配列の各要素を掛け合わせた時の最大値をできるだけ小さくするにはどう掛けあわせるのが最適？」っていう問題をちゃんと考える。
二分探索で値を見つけるコードを覚えとこう。
n,k = map(int,input().split()) A = list(map(int,input().split())) F = list(map(int,input().split())) A.sort() F.sort() F.reverse() t = sum(A) ok = 10**12 ng = -1 if t <= k: print(0) else: while abs(ok-ng) > 1: cur = 0 mid = (ok+ng)//2 for i in range(n): temp = mid/F[i] if int(temp) == temp: cur += max(0, int(A[i]-temp)) else: if A[i]-temp > 0: cur += int(A[i]-temp)+1 if cur > k: ng = mid else: ok = mid print(ok)
（こちらのサイトを参考にさせていただきました。ありがとうございました。）
復習 3/21
総和が不変であり、その約数がgcdの候補であることは気づけた。そしてその後に分配するフェーズで余りを横に並べて右側はプラスされる側、左側はマイナスされる側と分けてそれぞれをチェックするところまでは発想できた。
（例）
約数＝5で割った余りが1 1 1 1 2 2 3 4
1 1 1 1 2 2 3 / 4 →4はあと1プラスすればmod5=0、左側は全部4に移すので手数が11かかる
1 1 1 1 2 2 / 3 4 →3,4はそれぞれ2,1プラス（合計3）すればmod5 = 0、左は全部移して手数8、よって合計で手数8
1 1 1 1 2 / 2 3 4 →2,3,4 はそれぞれ3,2,1プラス（合計6)すればmod5 = 0、左は全部2,3,4に移して手数6、よって合計で6
1 1 1 1 / 2 2 3 4 →2,2,3,4は手数9、左を移すのは手数4、実際は左を全部2,4に移してmod5=0にして、あとは2を3に移せばいいので手数は6（だが便宜上9にしておく）
みたいなのを最後までやっていき、手数最小になるものがk以下になるものの中で最も大きい約数を出力
答え見てACしちゃったけど割と嘘書いてそうで心配
復習 3/19,3/20
数字が「ある」ところを探すんじゃなくて、「ない」ところを探すという発想の転換。難しい。
発想の問題じゃなくて、大きな数字を扱うときは注意しましょうねという話。基本的にpythonは大きな数字はメモリの許す限り扱えるけど、例えば
10**100-10 #9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999990 10**100-9 #9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999991 (10**100-9)//2 #4999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999995(これは誤り)
みたいになる。math.floor()とかもそうだけど、大きな数字は割り算（切り上げ切り捨て）の操作に弱いので要注意。
0点の人間を除いて、ソートして溢れなかったらK番目にいる人の点数+1、溢れたら0だってさ なんじゃこりゃ
