塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

4/11 AtCoder

こんにちは。最近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')

4/10 AtCoder

こんばんは。毎日めちゃくちゃ疲れているとーです。

ARC098D

数列の和とXORが等しくなる部分はいくつありますか、という問題
基本的に、XORと普通の和では、同じビットが立っているところはXORでは0になるので、XORの方が小さくなるということを念頭に置く
(想定解は、数列の各項を二進数に直し、ビットが立っている位を見ていって、その個数が1個以下であるならば足す、それ以外であれば左端を除く、ということを繰り返すものだったが今回は愚直に足していく方を採用)

解き方はいたって簡単で、端っこを固定し(ここでは左端)、伸ばせるところまで右を伸ばした後、右から左の数を引いて足す(これにより、固定した左端からスタートする数列の数が数えられたことになる)これを、左端が数列の右端に来るまで続ければよい

4/4 AtCoder(情報落ち)

こんばんは。春休み最終日なのに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の小さい位の部分が落ちてしまっているので、床関数使ったりするときは注意するように

tooh.hatenadiary.jp

以前こんなことを書いたが、多分これも同じ原因でおかしなことになったのだと思われる(制約が10**18だったので桁が大きくなるとceilとったときに勝手に小さい位が切り上げ・切り下げられてしまっている) というわけで桁がデカくなった時は切り下げのダブルスラッシュを使うように

4/3 AtCoder

こんにちは。なんだか風邪気味でちょっと厳しいとーです。

AGC002B


箱がN個あり、赤いボールが1つ、白いボールがN-1個入ってる これを与えられた操作でボールを移す作業をしたとき、赤いボールが入っている可能性のある箱はいくつありますか、という問題

最初に、ボールの数と、赤いボールが入っている可能性があるかどうかの二つのリストを持っておく、そして
①移す側の箱に赤いボールが入っている可能性がある→移される側も赤いボールが入る可能性がある(その逆もしかり)
②移す側の箱のボールの数を-1、移される側の箱のボールの数を+1する
③移す側の箱のボールの数が、操作終了後に0になったら、その箱には赤いボールが入っている可能性はないので、この部分を変更する

という操作を続ける

atcoder.jp



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
(実行時間ギリギリ......)

4/2 AtCoder

こんばんは。健康診断に行ったら無限人の人間がいて精神が崩壊したとーです。

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木などで数えられる

AtCoder Beginner Contest C問題 まとめ(随時更新)

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.'
でした これ瑠奈目線っぽいですね

3/31 AtCoder(半分全列挙、二分探索)

こんばんは。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のリストを組むのに苦労しました

atcoder.jp



エクサウィザーズ 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

3/29 AtCoder(1ずつ増加するLIS)

こんばんは。その日の獣には、をやっとプレイし始めました。とーです。

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)

3/27 AtCoder(-2進法)

こんばんは。しばらく更新しなかったのはチュウニズムの方ばかりコミットしていたためです。とーです。(AtCoderのstreak自体は地味に続いています)

AtCoder


ABC105C

与えられた数字を-2進数で表す問題 2進数とかではなくて負の数で与えられているのが何ともやり辛いところ


考え方は、例えば普通の2進数がどのようになっているかを参考にすると見えてくる

9(10進法)を2進数で表すことを考える これは1001になるが、まず右から一桁目は0もしくは1を表せることを考えれば、ここのビットが立っていれば(つまり1であれば)奇数、立っていなければ(0であれば)偶数を表すことは明らか なぜならそれよりも後ろ(二桁目以降)は2で割ったあまりに対して何の影響も及ぼさないから

というわけで、ここは1を立てておく
ここで1を消費したため、残りの桁では8を表せばよいと分かる

さて、二桁目より後ろを考えるとき、ここから後ろは2**1,2**2......と、必ず二の倍数を表すので、これを二で割って2**0(つまり1)、2**1......としたものを、8を二で割った数、つまり4を表すにはどうすればよいかを考えるのは同じことである

4は2で割り切れるので、一桁目(9を表すときには右から二桁目にある数字)は0でよい

そして、全く同じ要領で、4(から0を除いた数字、実質4)を2で割った数字2を、また二進法で表すことを考える
2は2で割り切れるので、一桁目(9を表すときには右から三桁目にある数字)は0でよい

また2を2で割ると、今度は1が出てきて、これは2で割り切れないので、二進法で表したときの一桁目(9を表すときには右から4桁目にある数字)は1にする

そして、1を消費したので、1から1を引いて0になった ここで終了する
その結果として、9の二進法表示として1001が得られた




今説明したやり方は、-2進法表記でも全く同様に使うことができる。つまり
①:Nが-2(2でもよい)で割り切れるなら、0を並べて-2で割る
②:Nが-2で割り切れないなら、1を並べて、ここで1を消費したのでNから1を除いて、除いた結果0でないなら-2で割る
③:②の結果が0になったならそこで終了する

という感じ(基本的にこのやり方は任意のn進法で使える)
注意として、2進法の時もそうだけど、下の桁から決定していっているので、ビットは前に前にとくっつけていくことを忘れないようにする





ABC110C

文字列を操作するやつ(きらい)

文字列SとTで、文字が一対一対応になっていればYes、そうでなければNoを出せばよい
例えばazzelとappleならば、
a:a
z:p
l:e
e:l
となっているので良いが、
chokudaiとredcoderでは、
c:r
h:e
o:d
k:c
u:o
d:d
a:e
i:r
と、cとiのどちらに対してもrが対応してしまうので(o,dも同様)、例えばc→rと変更したら、rhokudaiとなるが、その後でiをrに変更しようと思うとrとiの間で相互の変換が起こるので、ihokudarになってしまう
これが起こらず、かつちゃんと入れ替えができるのは文字が上と下で一対一に対応してることが必要条件になる これをコードに起こせばよい

3/22 AtCoder(ceilを使う時の注意、DP、N!を素因数分解)

ARC004C

二点間の距離がn個与えられて、点1と点nの距離の最小値はなんぼという問題

点が並んでる順番で距離が与えられているので、折り返すのは最長辺の両端でないといけない(逆にそこじゃないところで折ると長さが伸びてしまう)
求める値は、辺の長さの総和をS、最長辺の長さをmとして、max(0,2*m-S)になる


ARC062C

k = max(-(-A//L[i][0]),-(-B//L[i][1]))

k = max(math.ceil(A/L[i][0]),math.ceil(B/L[i][1]))

は同一のモノではないらしい(上の方が合ってる)
切り上げの時に安易にceil使うと間違えるかもしれない 原因不明 なにこれ


EDPC E 

価値iを達成するのに必要な最小の重量をdp[i]とするタイプのDP
こういうのは、まず全部float('inf')で埋めてから、dp[0]を0に更新して、リストのケツの方(つまりdp[10**5])から値を更新していく 
dp[0]の方から更新していくと、例えば

weight value
3 30
4 50
5 60

という入力を受け取ったときに、dp[50]=4で更新→dp[100]を8で更新(重量4の品物を2回使っていることになるのでこの時点ですでにあり得ない)→......と無限に続いていってしまうので注意

ABC114D

約数を75個持つ数として、例えばp**4とq**14の積を考えたとき、このようにp,qを選んでくるときは
①pには、指数が4以上14未満の数を選び、qには指数が14以上のモノを選ぶ
②p,qいずれも指数が14以上のモノを選ぶ
の二パターンがあり、後者はnC2ではなくnP2(順番も考慮すれば、どちらを4つ、どちらを14つ使うかも考えたことになる)であることに注意して数え上げる

あと、階乗の素因数の個数を求めるコード

N = int(input())
def primes(n):
  ass = []
  is_prime = [True] * (n + 1)
  is_prime[0] = False
  is_prime[1] = False
  for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
      continue
    for j in range(i * 2, n + 1, i):
       is_prime[j] = False
  for i in range(len(is_prime)):
    if is_prime[i]:
      ass.append(i)
  return ass
L = primes(N)
factorial_factor = []
for i in range(len(L)):
  k = L[i]
  cnt = 0
  cur = 1
  while N//k > 0:
    cnt += N//k
    cur += 1
    k = L[i]**(cur)
  factorial_factor.append([L[i],cnt])

3/21 AtCoder(最長共通部分列、期待値の線形性)

こんばんは。寝ても寝ても眠いとーです。

ARC092C

N個の座標が与えられて、xy座標の大きいものと小さいものをペアにしていきましょうという問題

想定解が頭良すぎた 自分で最初考えていてのは、xの小さい順にソートしてそれをxの小さい方から覆っていくようにとっていけばよいって方針だったけど、xの小さい順にソート→それで覆えるものでy座標が大きいものをとっていった方が省エネになる

なんか別の解き方もあるみたいなので、それはまたの機会に


EDPC F


最長共通部分列(LCS:Longest Common Subsequence)の問題

例えば、
abcd と becd の最長の共通部分列は bcd となる

長さが欲しいならば、dpを使って、(s,tは文字列)

s = input()
t = input()
dp = []
for i in range(len(s)+1): #s+1行、t+1列のリストを作る
  L = [0]*(len(t)+1)
  dp.append(L)
for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]: #sのi文字目とtのj文字目が一致していたら
      dp[i+1][j+1] = dp[i][j]+1 #リストのi+1行j+1列を、i行j列+1に変更
    else:
      dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]) #dp[i+1][j+1]はdp[i+1][j],dp[i][j+1]の長い方に変更

とすればよい

今回は部分列の長さではなく部分列自体を出力してほしいと言っているが、これをdpで愚直に文字列を形成していくやり方でやるとしんどい

ので、文字列を逆順に追っていき、作った文字列の前に文字を追加することを考える

文字を追加するタイミングは、dp[i+1][j+1]の数字が1減ったときである
これは、現在見ているs,tの文字をn,m番目として、
dp[n][m] == dp[n-1][m]であれば、sを一文字前にずらしても文字列(の長さ)は変わらない→LCS自体に変化はない
dp[n][m] == dp[n][m-1]であれば、tを(略
それ以外→dp[n][m] == dp[n-1][m-1]+1で、ここでLCSは増える(このタイミングで文字列を増やせばよい)
ということからわかる

juppy.hatenablog.com

↑こちらの記事を参考にさせていただきました ありがとうございました


SoundHound Inc. Programming Contest 2018 C

1~nまでの数字を重複を許してm個並べたとき、隣接する数字の絶対値がdになる部分の数の期待値を出す問題

シミュレーションで期待値が出せない以上何かしらの計算で出せるようになっているはず

隣り合う数字の差が0になるペアは(1,1)~(n,n)のn通りで、確率は1/n
差がdになるペアは(1,d+1)~(n-d,n)の(n-d)通りと、これをひっくり返した奴の計2*(n-d)通りなので、確率は2*(n-d)/(n**2)


よって、隣り合う数字の差がdになる確率が分かったため、期待値の線形性(この場合で言えば、期待値は(隣り合う数の差がdになる確率)*(m-1箇所)で求められる)からすぐに答えが分かる

同じような問題で、

[例]
確率1/2で0か1を表示する電光掲示板を8つ並べる。'111'と表示される箇所の数の期待値は?(1111は2つとしてカウントされる)

という問題は、'111'と連続する確率が1/8で、3つ並ぶところは6箇所あるので、6*1/8=3/4と求められる 簡単だね

3/19 AtCoder(PyPy3)

こんにちは。気分が悪くて半日お布団の中にいたとーです。

AtCoder

ARC013A

以前解けなかったきりしばらく放置していた問題

荷物の長さの順列を持ってきて、与えられた容器の辺をその順列の第一、二、三要素で割り切って、掛け合わせたものが容器に入る荷物の数なので、それの最大値を求めるだけ


ABC110D

これも以前解けなかった問題

素因数分解して、指数の部分を分割すればよいっていう賢いやり方が書いてあった すごい

さて実装の段で、nCkをかけていって、最後に10**9+7で割る操作が入ったのだが、

import math
n = int(input())
k = int(input())
a = (math.factorial(n))%(10**9+7)
b = (math.factorial(k)%(10**9+7))
c = (math.factorial(n-k)%(10**9+7))
print((a*pow(b*c,10**9+5,10**9+7))%(10**9+7))

この逆元を使うやり方だとTLEし、

n,k = map(int,input().split())
cur = 1
for i in range(k+1,n+1):
  cur *= i
for j in range(1,n-k+1):
  cur = cur//j
print(cur%(10**9+7))

こっちの普通に掛け算をする方では通った なんで

多分n,kがそんなに大きくないときは、後者の計算量もそれほどではないのでこっちの方が速い(nCk自体の計算はkに依存するので)のではないかとか思ったけど、n=10**5,k = 100とかでも前者の方が速かった(し、後者に至っては間に合わない)ので何とも言えない

まあこういうケースもあるということを覚えておく



EDPC D,I

どっちもTLEだったけどPyPyにしたら通った  マジ?

PyPyを使うデメリットは分かってないけど、速いんだったらこっちの方がよくないですか

3/18 AtCoder(漸化式dp)

こんばんは。特に何もすることなく春休みが終わっていくことに嘆くとーです。

今日から解くに至った問題は記録しないことにします。めんどいので。

AGC031B

juppy.hatenablog.com

いつもお世話になっているじゅっぴーダイアリーを読んで、自分なりに考えたことをまとめる
類似の問題で取り上げられていた

Sの連続した部分列のうち、同じ文字が含まれない取り出し方は?

という問題の解き方は
①基本的に前の方から後ろに向けて、文字列を伸ばしていく
②今持っている文字列の中に、次に見る文字が含まれていなければ、(今持っている文字列の長さ+1)だけ足す
(例)
abcという文字列で、今見ている文字列がab、次に見る文字がcであれば、cはabの中に含まれていないので、cを付加することによりカウントされる文字列はc,bc,abcの3つ
③今持っている文字列の中に、次に見る文字が含まれていたら、文字列中のその文字が含まれなくなるまで文字列を短縮し、それから次の文字を入れ、(今持っている文字列の長さ+1)だけ足す
(例)
abcaという文字列で、今見ている文字列がabc、次に見る文字がaであれば、aはすでに文字列に含まれているので、aを落としてbcに縮め、それから再びaをくっつける。新たにカウントされる文字列はa,ca,bcaの3つ

を繰り返していくという感じ

この動きを管理する漸化式を立てるとき、
「これまでに見た文字列の中で、既出の文字がどのインデックスで出てきたか」を格納するリストが必要で、これと「一番最後に見た文字」を照らし合わせる

さらに、「今持っている文字列の一番最後のインデックスがどこにあるか」という情報も必要になる
これは、次に見る文字に対して新たに何個の文字列ができるかということを考えたとき、
①次の文字が、今見ている文字列の最後(インデックス的に言えば0に近い方)のインデックスよりも前のインデックスで一度以上出現していた→文字列に付加しても文字列が縮まることはない
②①ではない→その文字の所まで文字列を縮める必要がある

ということがあるからだ

だから、答えのコードに説明をつけると、

n = int(input()) #文字数
s = list(input())
mod = 10**9+7
def f(x):
    return ord(x) - 97
used = [-1]*26 #ここに文字ごとにその文字が使われた直近のインデックスが入る
tank = -1 #文字列の末尾を示す
res = 0
for i in range(n):
    res += (i - max(used[f(s[i])],tank))%mod #新たに増える文字列がいくつあるか
    tank = max(tank,used[f(s[i])]) #文字列の末尾を更新する(同じまま推移することもある)
    used[f(s[i])] = i #今見た文字の直近のインデックスを更新
print(res)


となる


これを今回のAGCのB問題に応用すると、

①隣り合っている同色の石は(隣り合っていること自体)無意味なので一つにまとめてよい
②i番目の石までの並べ方はdp[i] = dp[i-1]+dp[used[i]]とできる i-1番目までの色の並べ方に「i番目の石と同じ色の石で、最もi番目に近い石までの並べ方」を足せばよい理由は、その「最もi番目に近い石までの並べ方」をj番目とすると、「i~j番目の石をすべてその色で塗る」という行為で増える色の分=増やすべき要素数(逆に、これまでに登場しない色であれば、その間を塗ることで増える場合の数はない)となるからである

ということを使っていけばよい(②で考える分、類似問題のように「現在見ている文字列の、先頭に近い(ケツの)文字の情報」を保持しておく必要はない)

python3によるコード

N = int(input())
K = []
for i in range(N):
  K.append(int(input()))
L = [K[0]]
for j in range(1,N):
  if K[j] != L[len(L)-1]:  #ダブり解消
    L.append(K[j])
dp = [0]*len(L)
dp[0] = 1  #最初は1通りからスタート
used = [-1]*(max(L)+1)  #used[i] == iとする(1インデックスぽい)
used[L[0]] = 0  #リストの最初の数字を見た
for i in range(1,len(L)):
  if used[L[i]] == -1:
    dp[i] = dp[i-1]
  else:
    dp[i] = (dp[i-1]+dp[used[L[i]]])%(10**9+7)
  used[L[i]] = i
print(dp[len(L)-1])


ABC113D

あみだくじの問題
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは何通り作れますかという趣旨の問題


まず、この問題を解くうえで一番重要なのは、「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ

高さh、棒jに至る経路の総数をdp[h][j]とすれば、高さh-1からこの位置に至ることができるのは、棒j-1,j,j+1のいずれかしかない

さらに、そこに至る経路数というのは結局「ほかの棒にどんな風に架け橋(横棒)がかかっているか」の場合の数なので、それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある

例えば、dp[h-1][j]を見てみる これは、同じ棒から下ってくることを意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」ということである
つまり、この高さにおける横棒の架かり方というのは「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の二パターンしかないということになる

ある高さにおける横棒のかかり方も漸化式で求められる 高さhにおける(横一列にかけ橋が並んでいる状況を考える)、n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)
と書くことができる

これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである

だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、j-1本の棒の間にかかる橋の場合の数f(j-1)と、W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる これと同様に、残り二本に対してもいくつかければよいかを考えて、dp[h][j]]に対する漸化式を立てればよい

以下はpython3による解答

H,W,K = map(int,input().split())
dp = []
for i in range(H+1): #高さ0の分を余分に持っておく
  L = [0]*W
  dp.append(L)
fb = [1,1] #フィボナッチ(f(n)=f(n-1)+f(n-2))
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1 #左端の棒の高さ0は初期位置なので1に
if W != 1: #棒が一本以上あるときは
  for i in range(1,H+1):
    for j in range(W): #棒が左端、右端、それ以外で場合分け
      if 1 <= j <= W-2:
        dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
      elif j == 0:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
      else:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
else:
  dp[H][0] = 1
print(dp[H][K-1]%(10**9+7)) #高さH(一番下)、K-1番目の棒を調べる


EDPC H

迷路の経路の総数(右、下移動のみ)を求めるときにDPが使える

3/17 AtCoder(素因数分解)

こんばんは。昨日のAGCのショックでしばらく立ち直れなかったとーです。

AtCoder

解くに至った問題

AGC:031A
ARC:097C
Tenka1 Programmer Contest:C
CADDi 2018:C
codeFlyer:B


AGC031A

解き方はすぐ思いついたのですが、まず10**9+7で割ったあまりを問われていることに気づかず3回WA、さらに、もし26文字すべてが文字列の中に使われていたとすると、それらを選ぶ/選ばないの組合せが2**26通りあるので、これではO(10**8)くらいになって間に合わない

という感じで本番中にACできませんでした(実質解き方を思いついてない) 

2**26通りの組み合わせはいいんですけど、これって結局「何を何個使うか」の組合せでしかない
例えば、「120の約数は何個ありますか?」という問いかけに対して、馬鹿正直に120==(2**3)*(3**1)*(5**1)だから、2だけで構成されるのが何個、2と3で構成されるのが何個......みたいに数え上げる必要はない
2が使えるのは0,1,2,3個だから4通り、3が使えるのは0,1の2通り、5が使えるのは0,1の2通りだから約数は4*2*2=16個、と数えるのが普通だし、明らかに速い
というわけで、今回もこちらを使うべきである ただ、「一つも選ばない」という選択は出来ないので、その場合(1通り)を除くようにすれば、すぐに答えは求まる

bit全探索しか思いつかなかった 脳が凝り固まっている
制限時間内に解ける仕様になっているのだから、それを見つけるように努力する



天下一C

うまいことすれば3500**2のループで解けますって言われたから、普通に書いたらTLEした
通ったコードはこれ

N = int(input())
for n in range(1,3501):
  for w in range(n,3501):
    if (4*n*w-w*N-n*N) > 0:
      h = n*w*N/(4*n*w-w*N-n*N)
      if h == int(h) and h > 0:
        print(int(h),n,w)
        exit()

4行目で != 0としていたらダメだった 分母が負の値の時も律儀に計算することになるためである
だから>0とする必要がある


CADDi2018C

nを素因数分解するコード

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

計算量はO(n**0.5)