また詰まってんのかよって感じですが一応
入力は#include
まあでもC++使ってる人たち割とiostreamを使っている印象があるのでこっちでよいかなという気持ちにはなる
競プロで最初に言うべきおまじないってまだよくわからないのだけど
#include <iostream> #include <algorithm> #include <string> using namespace std;
くらいでよいのかな
とりあえずiostream使うならcin,coutで統一した方がよさそう
そのうちお世話になるかもしれないサイト
忘れがちな C++ の標準ライブラリの使い方 - Qiita
C++文字列 - C++のstring型について調べるも… (凍結)
orとand
if文の中で例えば「aが1か2だったら」みたいなのは
if ( a == 1 || a == 2)
みたいに
という記号で書ける
andは&&で書く
ARC076D
プリム法とは
>>>頂点をすべて結ぶのに必要な最小のコストを、辺E,頂点VとしてO(ElogV)で求めるアルゴリズム
構造は
①「『既に訪れた頂点(ア)』と繋がる『まだ訪れていない頂点(イ)』」とを結ぶ辺のリストの中で（ここではあくまで辺が主役）、最もコストが小さいものを選ぶ
②その辺のコストを足す（辺を使うことを確定させる）
③頂点(イ)と辺でつながる頂点のうち、その頂点がまだ訪れていないのであれば、辺のリストの中に追加する
④①に戻り、リストが空になるまで続ける
というもの
import heapq def prim_heap(): used = [True]*n #True:不使用 edgelist = [] for e in edge[0]: #連結なのでedge[0]は必ず存在する heapq.heappush(edgelist,e) used[0] = False #番号0の頂点を始点とする res = 0 #答え while len(edgelist) != 0: minedge = heapq.heappop(edgelist) if not used[minedge[1]]: #取り出した辺の行き先が使用済みなら continue #捨てる v = minedge[1] #そうでないなら行き先を使用済みにする used[v] = False for e in edge[v]: #行き先の頂点がつながる辺において if used[e[1]]: #その先の頂点が未使用なら heapq.heappush(edgelist,e) #次につなげる辺の候補にする res += minedge[0] #コストを足す return res n,w = map(int,input().split()) #n:頂点の数、w:辺の数 edge = [[] for i in range(n)] #edge[i]には、[コスト,行先]というリストがさらに内包される for i in range(w): x,y,z = map(int,input().split()) edge[x].append([z,y]) edge[y].append([z,x]) print(prim_heap())
この問題では、全部の辺をつなげようとすると、N**2通りの辺が存在するので、N = 10**5だと間に合わない。少し考えると、かけるべき辺は、ある頂点とx座標、y座標のそれぞれで最も近い頂点との間のみでよいことが分かる（x座標の小さい方から並べた頂点ア、イ、ウに対し、ア、イ、ウすべてを訪れることを考えると、アーウとつなげる必要はなく、アーイ、イーウとつなげればよいから）
だからx,yのそれぞれでソートし、隣り合う頂点のみに辺を掛ければ、辺の数はO(N)になって間に合う
実装が重いので後でやります.......。
ABC122A
シングルクオーテーションとダブルクオーテーションの違い
#include <iostream> #include <stdio.h> using namespace std; int main() { char b; cin >> b; if (b == 'A'){ printf("%s","T"); } else if (b == 'T'){ printf("%s","A"); } else if (b == 'G'){ printf("%s","C"); } else { printf("%s","G"); } }
という例を考えると、
①if文の中で数値として扱っているのは'（シングルクオーテーション）
②if文の中で文字列として扱っていたり、printfの中は"（ダブルクオーテーション）
になる
例えば、Heiseiという文字列を出力するときにcoutを使うと、
cout << "Heisei" << endl;
でもいいし、
printf("%s\n","Heisei")
でもよい
ただ、cout << 'Heisei' << endl; や printf("%s\n",'Heisei') のようにシングルクオーテーションはダメ
ABC121A
空白で空いた二行二列の入力も、普通に
int H,W,h,w;
cin >> H >> W >> h >> w;
ってやって受け取ることができる
ABC120A
整数同士の割り算はその商が返ってくる（つまり切り捨ての値が返ってくる）
小数点以下を返してほしければ（実数）/（整数）みたいにすればよいとのこと
実数は、pythonと同じようにfloatで書けるが、doubleという形でもかける こっちの方がメモリを食うけど表せる範囲が広いらしい
こんばんは。昨日windowsのパソコンでUbuntuをインストールしたらバチバチに重くて泣いたとーです。
C++に挑戦、ということでこれからC++のコーディングを練習します。新しい言語を学習するとなると入力、出力が最初のネックになるけどここは我慢.......。
ABC124A,ABC123A
大枠をかっこ{ }で区切ってコードを書く
入力
空白区切りの数字二つは、
#include <iostream> int main() { int a,b; cin >> a >> b; }
みたいな風に入力を受け取ればよい
改行区切りで数字が増えても同じようにする
出力
出力は、printf()というのとcout << ナントカ ( <
一方でprintf()は最初にinclude
また、coutは本来std::coutと書くべきだけど、最初にusing namespace std;とすればstd::の部分は省略できる
std::の部分は名前空間というらしく、coutというコマンドがstdという領域内のコマンドであることを示しているっぽい これ（名前空間）によって、例えば（こういうことをするのはまずいとは思うけど）自作のコマンドcoutを作ったとしても、std::coutとは区別ができるようになる
（全てについてstd::を省略するのは不都合が生じることもあるらしいので、using std::cout; としておけば、coutだけはstd::の部分を省略できるようになる、{ }で括った部分に入れれば、その{ }内でのみstd::が省略されるようになったりする）
結局、C言語の入出力関数(printfなど)を使用するのには #include
で、結局どちらを使うのがいいのかって話になると難しくて、蟻本なんかだとprintfを使ってたりする
おそらく型変換とか改行とかがやりやすいのかな？だから競プロ向けで使ってるのかもしれん とりあえずprintfでやっていく
printfでやる場合、例えば
#include <stdio.h> int main() { char *str1 = "Hello"; char *str2 = "World"; int number = 10; printf("%s %s %d \n", str1, str2, number); }
となる
まず、charとかintとかで型宣言をしておくのはよくて、その次のprintfの中の%sとか%dとか\nとかなんやねん、って感じになるが、printf()は型を指定してprintができるということらしい
%c → char 文字
%s → char * 文字列
%d → int 10進整数
%f → float 実数
みたいな対応をしている たぶん競プロでは%cよりかは%sの方が使うんじゃないかな
で、\n（\は￥(半角)と同じ）は改行を表す特殊文字だそうです 競プロ改行が大事になりがちなので覚えます
使い方は、printf("型の宣言",適当な引数)という感じになる
a = 11として
printf("%d/n",a);
とすれば、11が出力され、その後に改行が入る
a = 11,b = appleとして
printf("%d %s\n", a,b);
とすれば、11 appleと空白区切りで出るし、%d%s\nとつなげれば11appleと出る
条件分岐
if/elseの書き方は、
if (条件){ \\ なにか } else if (条件) { \\ なにか } else { \\ なにか }
という感じ（つまり一つの判定につき括弧を一つ使う）
for文
簡単なコードを例にとってみる
int i; for(i=0; i<3; i++){ printf("%d\n",i); }
見れば分かるように、i=0に対してiを出力しインクリメント（1加算）、というのを、i=0,1,2に対して行う
なんかi++と++iという二種類の書き方があるっぽいけど何もなければi++でいいっぽい
こんばんは とーです
つい最近、チュウニズムのレートが15.5になりました
アイリちゃん最高！！！！！！！！！！！！！！！
マジで13.5とは思えない簡単さの曲が出てきたので速攻で乗せてきました
15.50達成時のベスト枠がこちらになります 15.50達成する人って何かしら得意な13.7,13.8くらいの曲で盛ることが多いと思うんですけど、僕はベスト枠平均が15.5超えていたにも関わらずそういう得意曲がなかったため、なかなか15.50になれず苦しかったです
見ての通り13+の鳥が一つしかありません 15.50になるには少なくとも13+の鳥が一つはないと厳しいかもです(それでも以前に比べれば圧倒的になりやすくなったわけですけど)
クラスエンブレムも更新しました
これまでの約一年間の軌跡です 主に13鳥の情報が載ってます（ジングルベル15.6は15.16の誤記です）
鳥取るのが大変だったのは
①分からない
②立川浄穢捕物帳
③Phantasm Brigade
④ラクガキスト
⑤優曇華院
⑥とれびちゃん
らへんです ここらへん本当に苦労しました
なんだかんだ一年続けてきて、3000クレも費やしましたが、何とか15.5になることができてよかったです
始めた頃はここまで来ることは全く想像できなかったのですが、いざなってみても自分はまだまだだなあと思わされるばかりです
他人と競い合うことも大切ですが、それが白熱しすぎて自分がこのゲームを楽しいなって思えなくなると本末転倒なので、自分の楽しい範囲でやるのが大事だなって最近思うようになりました
あと、別に鳥が取れなくても、単純にハイスコアを更新したり苦手なところがAJ通過できるようになったことを自分の成長と捉えると、気持ちを折らずにチュウニズムが続けられると思います
こんにちは。最近10時に寝て7時に起きるという小学生顔負けの生活リズムのとーです。
ABC087D
二人の人の間の距離が渡されるのでそれらの情報が矛盾していないかどうかを確認する問題
解き方としては、起点の情報から見ていって、座標の情報がまだ更新されていなかったらとりあえず今持っている情報で更新し、すでに更新されていたら、今持っている情報と更新済みの情報が矛盾しないかをチェックしていくという感じ
一つ確認し、それに連なる点の情報を見る、という作業を続けていくので、FIFOのデータ構造が使える
以下はpython3による答えのコード
from collections import deque N,M = map(int,input().split()) edge = [[] for i in range(N)] #edge[i]には点i-1に隣接する点と、距離が入る x = [float('inf')]*N #ここに点の座標の情報が入る(最初は全て未更新) for i in range(M): L,R,D = map(int,input().split()) edge[L-1].append([R-1,D]) #左から右を見るときは距離Dが入る edge[R-1].append([L-1,-D]) #右から左を見るときは距離-Dが入る for i in range(N): if x[i] == float('inf'): #座標の情報が未更新なら x[i] = 0 #ここを起点とする q = deque([i]) #起点がqに入る while len(q) > 0: #qが空になるまで続く now = q.popleft() for e in edge[now]: if x[e[0]] == float('inf'): #次に見た点が未更新なら x[e[0]] = x[now]+e[1] #今見ている点から距離+D(e[1])だけ足す q.append(e[0]) #次に見た点をqに入れる elif x[e[0]]-x[now] != e[1]: #次に見る点が更新済み且つ情報と矛盾するなら print('No') exit() print('Yes')
こんばんは。毎日めちゃくちゃ疲れているとーです。
ARC098D
数列の和とXORが等しくなる部分はいくつありますか、という問題
基本的に、XORと普通の和では、同じビットが立っているところはXORでは0になるので、XORの方が小さくなるということを念頭に置く
（想定解は、数列の各項を二進数に直し、ビットが立っている位を見ていって、その個数が1個以下であるならば足す、それ以外であれば左端を除く、ということを繰り返すものだったが今回は愚直に足していく方を採用）
解き方はいたって簡単で、端っこを固定し（ここでは左端）、伸ばせるところまで右を伸ばした後、右から左の数を引いて足す（これにより、固定した左端からスタートする数列の数が数えられたことになる）これを、左端が数列の右端に来るまで続ければよい
こんばんは。春休み最終日なのに17:00に起きたとーです。
Code Festival Team Relay A
問題文は割愛
解説で、math.floor( (K-A)/(A-B) )使えばいいよって書いてあったのだが、
例えば、K = 10*18, A = 2, B = 1という入力の場合、
K-A == 999999999999999998
A-B == 1
(K-A)/(A-B) == 1e+18 (10**18) ←本当は999999999999999998
と出てくる
明らかにK-Aの小さい位の部分が落ちてしまっているので、床関数使ったりするときは注意するように
以前こんなことを書いたが、多分これも同じ原因でおかしなことになったのだと思われる（制約が10**18だったので桁が大きくなるとceilとったときに勝手に小さい位が切り上げ・切り下げられてしまっている） というわけで桁がデカくなった時は切り下げのダブルスラッシュを使うように
こんにちは。なんだか風邪気味でちょっと厳しいとーです。
AGC002B
箱がN個あり、赤いボールが1つ、白いボールがN-1個入ってる これを与えられた操作でボールを移す作業をしたとき、赤いボールが入っている可能性のある箱はいくつありますか、という問題
最初に、ボールの数と、赤いボールが入っている可能性があるかどうかの二つのリストを持っておく、そして
①移す側の箱に赤いボールが入っている可能性がある→移される側も赤いボールが入る可能性がある（その逆もしかり）
②移す側の箱のボールの数を-1、移される側の箱のボールの数を+1する
③移す側の箱のボールの数が、操作終了後に0になったら、その箱には赤いボールが入っている可能性はないので、この部分を変更する
という操作を続ける
ABC063D
モンスターN体に対し、1体にはA,N-1体にはBのダメージが与えられる魔法を最低で何回唱えればモンスターが全部倒せますか、という問題
T回でこれが全部終わると仮定すると、この施行は
①体力がB*Tより多いモンスターに対し、そのモンスターの体力をSとして、体力をS-B*Tまで削った後、A-Bのダメージを何回か与えることと等価
②体力がB*Tより少ないモンスターには追加でダメージを与える必要がない
ということなので、①で求めた追加ダメージの回数がTと等しくなるところを探してあげればよい
二分探索を使えば、上限を(モンスターの体力合計)/B、下限を-1としたうえで、上限-下限が1より大きい間は、
T = （上限+下限）//2
として、追加ダメージの回数をO(N)で求めたあと、それがTを上回っていたら、追加ダメージが想定より多く必要になってしまっているので、下限をTにあわせる、逆にTを下回っていたら、上限をTに合わせる、ということを繰り返していく
atcoder.jp
（実行時間ギリギリ......）
こんばんは。健康診断に行ったら無限人の人間がいて精神が崩壊したとーです。
ABC103D
横一列に並んだ島のi,i+1番目に橋が架かっていて、与えられた入力の島を行き来できなくするのに落とす必要のある橋の最小本数は？という問題
右側の方に番号の大きい島が書かれているので、それを昇順にソートして、その島の左側の橋が落ちていれば何もしない、落ちていなければ落とす、を繰り返すのが最適なので、これをやるだけ かしこいなあ
ABC097D
ある決まった二組の数字だけが入れ替えられる状況下で、左から数えたその番号の場所iとその番号p_iが一致するようにすると最大いくつ一致させられるか、という問題
行き来できる二組の間に辺を張ったグラフを考える その中で、一致させたい番号と場所の番号が結ばれていれば入れ替えによって一致させられる
例えば、
p_i = 5 3 1 4 2
i = 1 2 3 4 5
で、1,3番目と4,5番目が入れ替え可能だとすると、グラフは1-3,4-5,2となる(ハイフンは連結していることを表す）
そこで、グラフ上で、p_iとiが同じ木の上にあるかどうかを見ると、
P_i = 1,4
i = 3,4
の二組だけが同じ木の上にあると分かる（p_i == iは同じものとみなす）
このような(p_i,i)の組を数えればよい UF木などで数えられる
D埋めが厳しくなってきたので、C問題を復習しつつ主観的難易度をまとめます。下にスクロールすると解法が（一行程度ですが）バリバリ書いてあるので閲覧注意。
開催されたのが最近になるように並んでいます
☆の数が多いほど難しいです 教育的だなあと感じた問題には教育と書いてあります
ABC128C ☆☆
ABC127C ☆☆
ABC126C ☆
ABC125C ☆☆☆☆ 教育
ABC124C ☆
ABC123C ☆☆
ABC122C ☆☆ 教育
ABC121C ☆
ABC120C ☆☆☆
ABC119C ☆☆☆☆ 教育
ABC118C ☆☆☆
ABC117C ☆☆☆ 教育
ABC116C ☆☆
ABC115C ☆
ABC114C ☆☆☆ 教育
ABC113C ☆☆☆ 教育
ABC112C ☆☆☆ 教育
ABC109C ☆☆
ABC108C ☆☆
ABC107C ☆☆ 教育
ABC106C ☆
ABC103C ☆☆
ABC102C ☆☆
ABC101C ☆☆
ABC100C ☆
ABC099C ☆☆ 教育
ABC098C ☆☆
ABC097C ☆
ABC094C ☆
ABC093C ☆
ABC090C ☆
ABC089C ☆
[ネタバレ]
ABC128C ☆☆
Nがせいぜい10なので、スイッチのON/OFFを全列挙しても最大で1024通りになる だから、そこから全探索して、ランプがすべて点灯するようなスイッチのつけ方をあぶりだせばよい
ABC127C ☆☆
ド典型のいもす法 普通に実装するだけで解ける
ABC126C ☆
確率を求めるだけ pythonだと小数点の扱いに全く苦労しないためイージー
ABC125C ☆☆☆☆ 教育
めちゃんこ難しい D問題か？ N個の要素が入ったリストの中でN-1個の要素の最大公約数を求めてあげればよいが、愚直にやったらO(N**2)かかるので無理 最大公約数は計算する順番によって変わらないという性質を用いれば、左からi番目までの最大公約数を持ったリストと右からN-i番目までの最大公約数を持ったリストを参照して、そのL[i]とR[N-i]の最大公約数を見ればよい、という解き方になる
ABC124C ☆
最終状態が黒白......か白黒.......の2パターンしかないのでそれと比較してあげればよい
ABC123C ☆☆
結局最も運べる人数が少なくなるところが律速になるので、それについて考えればよい
ABC122C ☆☆ 教育
累積和が使えれば難しくない Cに累積和、DにDPが置かれることが多い（気がする）
ABC121C ☆
リストをソートして貪欲にとるだけで解ける C問題か？というくらい簡単
ABC120C ☆☆☆
最終状況を考えることに気づかないと難しい 発想寄り
ABC119C ☆☆☆☆ 教育
制約をよく見れば全探索に気づくけど初見は厳しい 4進法を使いましょう
ABC118C ☆☆☆
気づけば簡単 気づけば...... リストの中の最大公約数を求める問題
ABC117C ☆☆☆ 教育
視点を変えて見るのが案外難しい M-1個の区間のうち駒が跨がなくてもよい区間がN-1個あるので、どこをすっ飛ばすかを検討する 距離の長い区間を上からとる
ABC116C ☆☆
扱い方がちょっと難しいかも 伸ばせるところまで伸ばしてしゃくとりっぽく進めていく
ABC115C ☆
ソートして間隔Kで最も差分が近くなるように選ぶだけ
ABC114C ☆☆☆ 教育
最終的な場合の数の少なさから全列挙を想起できるかどうか
ABC113C ☆☆☆ 教育
連想配列の扱い方、あとは0埋めができるかどうか 実装がやや重い
ABC112C ☆☆☆ 教育
入力に必ずh!=0となるようなhが存在することに気づいて、それを使って中心座標についての全探索ができるかどうか
ABC109C ☆☆
初期位置と各座標との差をとり、それらの最大公約数を出せばよいだけ 互除法が使えれば難しくない
ABC108C ☆☆
数学 Kが奇数だったらa,b,cのmodKが0、偶数だったらa,b,cのmodKが0かK//2になればよい 面白くない問題
ABC107C ☆☆ 教育
0から始めて、左端と右端を左→右の順で訪れるのか、それとも右→左の順番で訪れるのかというのを全探索で殴る問題
ABC106C ☆
数列は1以外の数字が入っていればバカ長くなるので、もとの数列を見てK番目まですべて1なら1、そうでなければ初めて1でなくなるところを出力すればよい バグらせがち
ABC103C ☆☆
結局余りの合計が最大になるのは(全部の数字の最小公倍数-1)を各数字で割ったときの余りを足したものになり、それは各数字をL[i]として余りがL[i]-1と出てくるので、(全部の数字)-(数字の数)が答え これめちゃくちゃ賢い 実験して気付こうねってタイプの問題
ABC102C ☆☆
全ての項に対してbが共通なので、それについて考えればよい A_i-iを出してそれの中央値をとれば（すべてからまんべんなく引けるという意味で）bにふさわしいのでこれが答え
ABC101C ☆☆
最小値は1に他ならないので、N-1個の数字を幅K-1で1に置き換えることを考える
ABC100C ☆
実質全数字を何回2で割れるかを出すだけなので何も難しくない
ABC099C ☆☆ 教育
分からないとめちゃくちゃ難しそうに見えるけど実は単純な動的計画法 dp[i]を、「i円を引き出すのに必要な最短手数」として、引き出せる金額をjとし、dp[i] = min(dp[i-j],dp[[i])で更新していけばよい minを使うので最初のdpリストはinf埋め、dp[0]=0,dp[1] = 1とすること
ABC098C ☆☆
まず左から右に向かってEの人数を数える WEEWWという文字列だったらEast = [0,1,2,2,2]みたいなリストを作る これをWの人数もやると（逆順に数える） West = [3,2,2,2,1]となる 求めるのは、maxEast = ME, maxWest = MWとしたとき、i=0~N-1に対する(ME-East[i])+(MW-West[i])の最小値
ABC097C ☆
K = 5という制約からせいぜい5文字が限界（例えば答えが5文字になるのはaaaaaのようなときの場合のみ）なので、5文字以下の部分文字列を全列挙して比較して、最初からK番目を出せばよい
ABC094C ☆
出てくる数字はソートしたときのL[N//2]とL[N//2-1]しか出てこないので、これより右にあるか左にあるかで判別する
ABC093C ☆
全体の和の偶奇が不変であることに着目するらしいです まあそんなこと気にしなくても脳死でコーディングできます
ABC090C ☆
実験すればN == 1 or M == 1のときとそうでないときで場合分けすればいいことに気づく
ABC089C ☆
数えてコンビネーションするだけ
おはようございます。昨日でその日の獣には、瑠奈ルートが終わったので感想を書きます。
＜多大なネタバレを含みます＞
とりあえず共通ルートを覚えている限りで振り返る
慣習的に上級生しか出られない夏の大会に何とかしてチャレンジしたいと願う主人公と、その妹瑠奈。個人的には、瑠奈がこの大会に出たいと思うモチベーションはまあ納得できるにしても、演劇に関してそれほど（中学生時代しか）経験を積んでいない主人公がよく分からん。瑠奈のためを思ってなのかなのかちょっと微妙なところで、ここがやや引っかかりました。
さて、それでチームのメンバーとして集まったのは幼馴染の舞雪と同級生の祈莉の二人でした。二人とも演劇に関しては素人で、四人の練習になると、どうしても瑠奈とほかの三人との意識の違いが露呈してしまいます。そのせいで瑠奈はヒステリックに怒り散らかします。ここの描写、正直見ている側がしんどかった。自分が部活に対してそれほど熱心ではなかったためなのか、ここまで熱くなってしまう人の心理に共感することは難しくて、単純に瑠奈が情緒不安定な人間にしか見えなくてつらかったです。
舞雪は学校の亡霊から力を授かり、選考会に参加する前段階の選考でその力を発揮します。審査に加わった講師、顧問、その他先輩から舞雪ばかりが言及され、瑠奈はそのことに苛立ちます。その後、結局亡霊の力を失ってしまった舞雪は二度と素晴らしい演技は出来なくなり、主人公もそれを気遣って自分の書いた台本の舞雪のセリフを直したりしますが力及ばず。主人公の事を見ているのがつらくなり、また自分も部活をやめたいと思った舞雪は主人公を籠絡し、ともに部活をやめようと誘います。ここで身体の関係を持ってしまいます。
さて、結局部活をやめるには至らなかった二人ですが、瑠奈と三人との溝は深まるばかり。瑠奈もチームを抜けようとしますが、祈莉が持ってきた謎の台本により、再びチームは一致団結します。ここまでが共通ルートだったはず（前後関係があやふや）
ここから、新しい台本「ソノヒノケモノニハ、」の主人公を誰にするかを決めるところで選択肢が発生します。最初に出てくる選択肢は瑠奈と舞雪の二択なのですが、今回は瑠奈を選択。
瑠奈は学校の亡霊「クロガネ」に出会い、どんな人の心も魅了することができる力を授かるチャンスを与えられますが、「自分の望みは実力でつかみ取る」と言います。しかし、クロガネの指摘通り、自分にそれほど実力がないことも理解しています。練習が再び始まりますが、また瑠奈は自分の熱意を抑えきれず三人に当たる始末。主人公はうまく立ち回ろうとしますが、舞雪の味方ばかりする主人公に対し、自分へ向けられない好意に瑠奈はいら立ちを覚え、また溝は深まろうとします。
主人公にちゃんと評価されたい、その気持ちのために、瑠奈は再びクロガネに会い、過去よりも未来の方が大事であると言ってのけ、兄との幼いころの思い出と引き換えに優れた女優としての力を授かります。
（ここで主人公が自室で寝ている妹を見て、代わりに床で寝るシーンが入るのですが、起きたときに目に映る瑠奈のイラストや言動が幼さを感じさせる（かわいらしい）ものに変わっていて、これも変化の一つなのかなと感じました）
さて、誰をも魅了する力を手に入れた瑠奈ですが、自分からは兄との記憶が失われていないこと、代わりに兄からは自分の幼いころの記憶が消えていることに気づきます。周りの人間から死ぬほど注目を浴びていい感じになる瑠奈、満たされない心が満たされたためか、練習する周りの三人の自分に対する賛美の目もあり、その言動はヒステリックなものからは落ち着いたものへと変化します。
しかし、なにか欠けていると感じるものがあります。それはやはり、自分が演劇をやろうとするモチベーション、つまり「幼い日の兄との思い出」でした。兄がいくら今の自分を評価してくれたって、その兄は小さなころの自分との思い出がありません。その大きな礎を失い、兄ですら自分の魅力の虜になってしまった今では、もはや兄を自分の力で（これは魅力の力を借りずに）自分のモノにするしかないと思います。兄に対する恋心もあり、ここで肉体的な接触を持ちます。
兄と恋人になりましたがまだ満たされない瑠奈（それはそうだろ）。体を重ねても、愛の言葉をささやかれても、その気持ちに蓋をすることはできません（こうなることは分かっていたのに、と後悔するシーンがありましたが、それ「分かってない」ってことですよって猛烈にツッコミを入れました。ここの後悔するシーンは全く感情移入ができなかったです）。自分が本当に欲しかったものよりも、自分が欲しいと思うものに対する原動力があるだけで「十分だったのに」と気づいた瑠奈は、クロガネに力を返却するから思い出を返してくれとせがみます。
ぶっちゃけそんなうまくいかんやろと（僕は）思っていました。ところがこのクロガネさん、素直に返してくれるんですよ。力を奪い去って記憶は返さない的な「ヒール」の動きを期待していただけに拍子抜けしました。この人にとっても自分の望みの方が大切で他人がどうなろうと関係ないと思っているなら別に返さなくてもよくないか？みたいな気持ちがありましたがそうはならなかったです。この後のルートでその行為に何か一貫した理由があるのかどうか明らかになるかは定かではないですが多分ないと思います。これはクロガネが純粋にいい人であるということでしょうか。じゃあしゃべり方をもうちょっといい人の方に寄せていってもよかったんじゃないかな......。
そして記憶を返してもらった主人公と、自分の本当に大切なものに気づいた瑠奈との関係は恋人のまま維持されます。瑠奈の気性もだいぶ落ち着き、ほかの二人に対する努力に理解を示すようにもなります。選考会の日を迎え、結局落選となってしまいますが、瑠奈は先輩たちのチームに加わって練習することが許されます。主人公も、自分よりも先を歩く妹に追いつこうと努力する決意を固めました。そして夜、自分の心を開いた妹とエッチします。いぇーい。
これで終わりです。
よかった点
①「じゅうぶんな、はずだった」のメッセージは一貫していた 「虚構の中で、一粒の真実を物語ること。それが、感動を生み出していく」というセリフがあったけどまあこれとも整合性があってよい（感動したかは別問題として）瑠奈が物語の流れで「足るを知る」を会得していくのはこの物語の運び方として間違っていないのでその点はよい
②マジでイラストがエロい
悪かった点
①瑠奈がマジで情緒不安定すぎて見ていられなかった ほんとにしんどい
②物語の展開がチープ、速いと感じる点がいくつかあった（祈莉の台本が何かしらの力を秘めているのはわかるけどちょっと無理やり感のある運び方は気になった。あと瑠奈が自分のしでかした愚行さに気づくのはいいんだけど、最初に自分の望みは自分の力で手に入れる的なまあまあかっこいいことを言っている人間が爆速で鞍替えしている様をみてこれでいいのかという気持ちになった。というか聡明そうだからこうなるってわかっているならやらなさそうなんだけどなあ）
③主人公が記憶喪失になる描写は、見ているこっちは物語の全容を把握している神視点なので、突然主人公が記憶を失うと一気に物語の没入感が薄れる（これはあくまで僕個人的にあまり好きではない描写であるというだけで、気にしない人は気にしないのかもしれん）
エロの描写は最高だったのでシナリオがもうちょっと納得できるものであったらなあという気持ちになりました うーむ
minoriさん定番のラストの英語のちょっとイイ感じの一行は
'...and now, the light of glory shines on you and me.'
でした これ瑠奈目線っぽいですね
こんばんは。1ACするのが重くなってきてだんだん競プロモチベが下がっているとーです。
ABC018D
問題が長くて怠い
女子N,男子M人がいる中から女子P,男子Q人を選ぶ。女子x_iと男子y_i一人ずつの組に対してz_iというパラメータがいくつか与えられており、男子と女子を適切にP,Q人選ぶことによってこのパラメータの合計を最大化しましょうねという趣旨の問題
N,Mが小さければ、男子女子の選び方はNCP*MCQだから全列挙するのもありかもしれないけどそれが厳しそう というわけで女子だけ全列挙する方針をとる（半分全列挙という）
女子だけ列挙した場合（最悪2**18だから大体10**7くらい ギリギリ）、
①女子を列挙
②男子全員分の長さを持った0埋めリストをつくる
③パラメータに対し、女子が列挙した中に入っていれば（x_iがあれば）それに対応する男子y_iの所にz_iを足す
④これをR回やって、男子のリストを降順にソート→上からQ人とる この合計値を更新していく
というアルゴリズムで何とかなる
（最初、パラメータを大きい方から見ていって、男子がQ人になるまで足す方針をとっていたが、それだと後ろの方にめっちゃ小さい値を持っているけど合計的には他よりも大きくなりうるケースを省いてしまっていたのでこれは通らなかった 貪欲に取ると言っても一回全部確かめてみないとね）
制約がN<=18とかの時はこれを疑ってみるとよいかもしれない
以下はpython3による答えのコード
N,M,P,Q,R = map(int,input().split()) L = [] for i in range(R): L.append(list(map(int,input().split()))) L = sorted(L, key = lambda x:x[2]) L.reverse() def Base_10_to_n(X,n): if (int(X/n)): return Base_10_to_n(int(X/n),n)+str(X%n) return str(X%n) ans = 0 for X in range(2**N): n = 2 STR = Base_10_to_n(X,n).zfill(N) cnt = 0 for i in range(N): if STR[i] == '1': cnt += 1 if cnt == P: cur = 0 jyoshi = [] for j in range(N): if STR[j] == '1': jyoshi.append(j+1) danshi = [0]*M for k in range(R): if L[k][0] in jyoshi: danshi[L[k][1]-1] += L[k][2] danshi.sort() danshi.reverse() for l in range(Q): cur += danshi[l] if cur >= ans: ans = cur print(ans)
ARC017C
これも半分全列挙が使える問題
重さの合計がXになればよいので、品物を前後半に分けて、前半で作れる重さを全列挙し、後半で作れる重さpに対して前半で作れるX-pがいくつあるかを二分探索で求めれば行ける
以下はpython3による答えのコード
import bisect N,T = map(int,input().split()) L = [] for i in range(N): L.append(int(input())) zen = [] def Base_10_to_n(X,n): if (int(X/n)): return Base_10_to_n(int(X/n),n)+str(X%n) return str(X%n) n = 2 P = [] Q = [] ans = 0 for i in range(N//2): P.append(L[i]) for j in range(N//2,N): Q.append(L[j]) if N%2 == 0: for X in range(n**(N//2)): STR = Base_10_to_n(X,n).zfill(N//2) cur = 0 for i in range(N//2): if STR[i] == '1': cur += P[i] zen.append(cur) zen.sort() for X in range(n**(N//2)): STR = Base_10_to_n(X,n).zfill(N//2) sub = 0 for i in range(N//2): if STR[i] == '1': sub += Q[i] k = bisect.bisect_left(zen,T-sub) l = bisect.bisect_right(zen,T-sub) ans += l-k else: for X in range(n**(N//2)): STR = Base_10_to_n(X,n).zfill(N//2) cur = 0 for i in range(N//2): if STR[i] == '1': cur += P[i] zen.append(cur) zen.sort() for X in range(n**(N//2+1)): STR = Base_10_to_n(X,n).zfill(N//2+1) sub = 0 for i in range(N//2+1): if STR[i] == '1': sub += Q[i] k = bisect.bisect_left(zen,T-sub) l = bisect.bisect_right(zen,T-sub) ans += l-k print(ans)
ABC079D
0~9までの10個の数字を選び、それをi,jとしたとき、iからjに変換するコストが与えられる
何回か操作を行って、入力された数字をすべて1に変換するのに必要な最小コストはなんぼ？という問題
高々100通りの組合せなので、ここは0~10を頂点に持ち、辺の数が100本あるグラフと考えて、ワーシャルフロイドで最短経路を出すという方針で行けば簡単に求まる
ただしいつもの最短経路問題のように往復するコストが等しいわけではないことに注意
以下はpython3による答えのコード
from scipy.sparse.csgraph import floyd_warshall h,w = map(int,input().split()) cost = [] for i in range(10): sub = list(map(int,input().split())) cost.append(sub) d = [[float("inf")]*10 for i in range(10)] L = [] for i in range(10): d[i][i] = 0 for i in range(10): for j in range(10): d[i][j] = cost[i][j] d[j][i] = cost[j][i] d = floyd_warshall(d) wall = [] for i in range(h): cur = list(map(int,input().split())) wall.append(cur) ans = 0 for i in range(h): for j in range(w): if wall[i][j] != -1: ans += d[wall[i][j],1] print(int(ans))
ABC122D
本番中にACできなかったやつ やっとACしました
dpを使います
T,A,G,Cをそれぞれ0,1,2,3に対応させ、N文字目までOK、かつ末尾の3文字がa,b,cであるような文字列のパターン数をdp[N][a][b][c]とします
dp[N+1][b][c][d]に遷移させたいわけですが、遷移できるものを考えるより遷移できないものを考えた方がよいです（まあそれはそう）
ダメなパターンは、
①abcにdをくっつけたとき、bcd（新たな末尾）がAGC,ACG,GACのいずれかになる場合
②abcにdをくっつけたとき、abcdがA〇GC,AG〇Cのいずれか（〇はT,A,G,Cのいずれか）になる場合
の二パターンなので、これを除くようにして遷移させていけばよい
直近の4文字についてのみ考えればよいと分かれば楽です
初期状態の置き方がめちゃくちゃ困るのですが、これは「後に適当につけていってもアウトにならない」=='TTT'の形であればよいので、dp[0][0][0][0]=1としてスタートしてあげればよい
解き方さえわかれば実装が楽......かと思いきや普通にdpのリストを組むのに苦労しました
エクサウィザーズ C
本番中にACできなかったので直し
ゴーレム同士の相対的な位置の変化はない（あるゴーレムがほかのゴーレムと同じ位置に来ることはあっても、ほかのゴーレムを追い越すことはない）ということを利用し、
「左側に落ちるゴーレムで最も右側にいるやつを見つければ、それより左側にいるやつはみんな左側に落ちる」
と考えられれば、あとは右側にも同じ考え方を適用してあげればよい
それを発見するのが二分探索で、ライブラリにあるものではないやつで運用する
書いてみたはいいもののなんもわかんないので練習が必要
N,Q = map(int,input().split()) s = input() L = [] for i in range(Q): L.append(list(input().split())) def judge_left(x): #左に落ちるものを判定する xは位置を表す for i in range(Q): if L[i][0] == s[x]: if L[i][1] == 'L': x -= 1 else: x += 1 if x == -1: #左端まで到達すれば return True if x == N: #逆に右端に到達してしまった場合は return False return False #いずれでもなければ def judge_right(x): #右でも同じことをします for i in range(Q): if L[i][0] == s[x]: if L[i][1] == 'L': x -= 1 else: x += 1 if x == -1: return False if x == N: return True return False ok = -1 #左端で「ここまでのゴーレムは確実に落ちる」というのを決める ng = N #右端はN while ng-ok > 1: #ng-okの間が1より大きいなら mid = (ng+ok)//2 #半分の所を見る if judge_left(mid): #それが左端に落ちるかどうかをみて ok = mid #落ちるなら、okのラインを右側に進める else: ng = mid left = ok+1 ok = N ng = -1 while ok-ng > 1: mid = (ng+ok)//2 if judge_right(mid): ok = mid else: ng = mid right = N-ok print(max(N-left-right,0)) #left+right>Nとなったときを回避
こちらの記事を参考にさせていただきました ありがとうございました
juppy.hatenablog.com
こんばんは。その日の獣には、をやっとプレイし始めました。とーです。
AGC024C
解説がの最後らへんが意味不明だったので最初の方に準拠して考えます
問題の趣旨としては「数列中の数字を適切に数列の先頭か末尾に持って行って昇順に復元してくださいね」という感じ
実際、「入れ替えるべき数字」より「入れ替えるべきでない数字」を考えた方がよく、そのような数字群は「連続していてかつ昇順に並んでいる」という条件を満たしている
つまり、そのような数字群の中で最も含む要素数が多いような部分の長さを考え、全体から引くようにすればよい
例えば
1 8 9 2 3 5 7 4 6
という数列の中で、上記の条件を満たす最長の部分列は1 2 3 4である
これを求めるには、まず0埋めしたリストdpとBoolのリストTFを持っておいて（どちらも1インデックス）、数列を前から見ていったとき、
①今見た数字iをTrueにする
②そのひとつ前の数字i-1がTrueになっていたら（つまり数列内で既出で、TF[i-1] == True）、dp[i] = dp[i-1]+1とする
といったような更新を行っていけばよい
以下はpython3による答えのコード
N = int(input()) L = [] for i in range(N): L.append(int(input())) TF = [False]*(N+1) dp = [0]*(N+1) for i in range(N): TF[L[i]] = True if TF[L[i]-1] == True: dp[L[i]] = dp[L[i]-1]+1 print(N-max(dp)-1)
