A問題: 天気予報と実際の天気の比較
AtCoder Beginner Contest 139回目、A問題、天気、問題文、ある3日間の天気予報が長さ3の文字列Sとして与えられます。
Sの合文字目がSの時、合日目の天気予報が晴れだったこと、サニーですね。Cの時は曇りだったこと、Rの時は雨だったことを意味します。
また、3日間の実際の天気が長さ3の文字列Tとして与えられます。
Tの合文字目がSの時、合日目の実際の天気が晴れだったこと、Cの時は曇り、Rの時は雨だったことを意味します。
3日間で天気予報が適中した日が何日あるかを出力してください。
で、えー、まあ、これは、そうですね、3文字だけなので、Sイコールインプット、Tイコールインプット、で、もういいや、4iインレンジ3。
で、CNTイコール0で、if SIイコールイコールTIだったら、CNTプラスイコール1、で、4分の最後にプリント、4分の最後というか、4分抜けて最後にCNTをプリントすればOKですね。
はい、A、CしたのでB問題に行きます。
問題、パワーソケット。
問題文、高橋くんの家には電源プラグの差し込み口が一口しかありません。
そこで、高橋くんはA、C、A個口の電源タップをいくつか使って、未使用の差し込み口をB口以上に拡張したいと考えています。
A個口の電源タップ一つと未使用の差し込み口一つを使って、新たに差し込み口をA口増やすことができます。
最初でいくつの電源タップが必要でしょうか。
ん?
A、Bが与えられます。
入力例1は4と10、出力例は3。
4個口の電源タップを3つ使うと、未使用の差し込み口は10口になります。
あー、そういう?
入力例2、8、9、出力は2。
8個口の電源タップを2つ使うと、未使用の差し込み口は15個になります。
入力例8、8は出力例1。
制約は、Aは2以上20以下。
Bは1以上20以下。
これは、なんか計算っぽいですね。
ABイコールマップ、イント、インプット、プロットスプリット、
んーと、割るの繰り上げとかかな。
割り算して繰り上げとかかな。
違うかな。
高橋くんはA個口の電源タップをいくつか使って、
未使用の差し込み口をB口以上に拡張したい。
だから、えーと、アンサーイコール0。
ホワイル、えーと、今、電源プラグの差し込み口が1しかない。
CNTイコール1。今ある差し込み口が1。
で、えーと、アンサー、えー、なんてやったらいいかな。
差し込み口、CNT。
CNTが、差し込み口にするか、プラグ、プラグイコール1、今1個差し込み口があります。
これが、B口以上でしょ。
だから、これがBより小さい間、プラグ小なりBの間、
これが、アンスプラスイコール1。
で、A個口の電源タップ。
電源タップ1つと、未使用の差し込み口1つを使って、
4個口の電源タップを3つ使うと、
4個口の電源タップを3つ使うと、
未使用の差し込み口は10個になります。
B問題: 電源タップの必要な個数
1、2、3、4、そうですね、5、6、7、8、9、10個。
ってことは、んーと、あー、どうしようかな。
IFプラグが、もうB以上だったら、
EXITPRINTプラグ。
プラグ?アンス?ん?
88、入力で388。
A個口の電源タップをいくつか使って、
あー、そうか、えーと、だからBが1だったら、
IFBイコールイコール1だったら、
PRINT0。
で、IF、いや、まあいいか、えー、
IFAイコールイコールBだったら、
EXITPRINT1。
で、そうじゃない場合が始まるので、えー、
アンサープラグ、アンサープラグ、えー、どうしようかな。
アンスが、カラスがよう泣いとる。
アンスが0の、いや、アンス1のプラグが、今A個あります。
で、WHILEプラグが小なりBの間、
プラグ、マイナスイコール1して、
アンスにプラス1して、
で、プラグにプラスイコールA。
で、プリント、アンサーじゃない。
4と10だったら3が出ます。
よいしょ、3。
8と9だったら2が出ます。
はい。
2。
8と8だったら1が出ます。
んー、もうちょっと大きい数字、
欲しかったですね、入力例。
停止して、
はい。
入力例、提出してみましょうか。
はい。
停止しました。
よかったー。
C問題: マスの高さの比較
C問題いきます。
C問題。
ローは、問題文。
左右一列にN個のマスが並んでいます。
左からI番目のマスの高さはHIです。
あなたは好きなマスに降り立ち、
右隣のマスの高さが今いるマスの高さ以下である限り、
右隣のマスへ移動し続けます。
最大で何回移動できるでしょうか?
うん。
10の9乗、10の5乗個あるので、
二重ループは厳しいか?
一回やってみますか。
Nが与えられてH数はある。
Nイコールイント、インプット。
Hイコールリスト、マップ、イント、インプットドット、スプリット。
これ、いや、4分1個でいいな。
アンスイコール0。
最大で何回移動できるでしょうか?
入力例1は5、14、8、7、3があって、
出力例は2。
左から3マス目のマスに降り立つと、
右に2回移動できます。
8から7、7から3ですね。
だから、アンスイコール0にして、
レンジNマイナス1ですね。
レンジNマイナス1して、
TMPテンポラリー、どうしようかな。
1から始まってNまで行くようにしましょうか。
テンポラリーがHのIマイナス1。
IF
TMPが
小さい場合、イコールはダメ。
高さ以下である限りだから、
TMPダイナリーイコールHのI番目だったら、
アンスプラスイコール1。
そうじゃなかったら、
そうか、どうしようかな。
2個いるな。
CNTイコール0。
カウントをプラスするようにしましょう。
で、FTMPダイナリーイコールHのI番目だったら、
CNTカウントを1プラスして、
そうじゃなかった場合、
でかいのにぶち当たった場合は、
CNTは0にします。
で、その前に、
アンサーイコールマックス、
今のアンサーに入っている数か、
CNTの数か、どっちですか。
で、CNTをリセット。
プリント、アンサー。
で、どない。
入力例1は2が出たら正解。
1。
だめじゃん。
んー、だめじゃん。
どこで引っかかった。
プリント、TMPとHのI番目。
で、えーと、
CNTとアンサーも入れようか。
CNT2の時あるね。
あるけど入れてない。
あー、えーと、
アンサーを入れるのを、
常に入れておきましょうか。
コピーして、
問題の概要
IFTMPDINARYイコールHのI番目の時にも、
CNTプラスイコール1した後、
アンサーを更新しましょう。
これでどうじゃ。
2。
出力例2は3が出たらOK。
3。
出力例3は?
0。
0。
はい。出力例はとりあえずクリアしたので、
出してみましょう。
さて、どうだ。
おっ、行きましたね。ACしましたので、
D問題に行きましょうか。
絶対解けないと思うけどな。
昔も解けたことないので。
Dは。
いや、1回ぐらいあるのかな。
D問題、MODSUM問題文。
問題文。
整数Nに対して、1からNを並べ替えた数列、
P1からPNを選びます。
そして、各Iイコール123CNについて、
IをPIで割った余りをMIとします。
M1からMNの最大値を求めてください。
おお、車のアラームが。
Nは1以上、10の9乗以下。
出力例M1たすからMNの最大値を出力せよ。
10の9乗。
なら、いけんじゃね。
順列を選ぶ最適解法
整数Nに対して、並べ替えた数列を選びます。
並べ替えた数列。
あっ、最大値ってそういうこと?
あまりを常に最大を取り続けるのがいいんだ。
これなんかありそうですね。調べてみましょうか。
あまり最大値合計。
あまり値の最大値。
Pythonとかで調べてみます?
Python。
約数。約数じゃないんだよね。
関数でべき乗。
割り算あまりを求める。
うーん。
単純に正反対にする。
じゃあダメそうかな。
1、2。入力例1は2、出力例は1。
1、2を並べ替えた数列として、2、1を選ぶと、M1たすN2、M2は1プラス0の1となります。
0?
あ、そうか。2割る1は0ですもんね。
だから、えー。
まんまひっくり返しちゃうと、
総裁しちゃうから。
うーん。
ま、1回まんまひっくり返してみますか。
それしかちょっと思いつかないので。
Nイコールint、インプット。
あー、また。
A数に戻さないとこれ、サジェストが出ないんですね。
インプット。
で、えーと。
MとP、MとPを作るか。
Mイコールからのリスト使って。
I for in range1からNプラス1まで。
で、えー。
P、数列PはMの反対。
アンサーイコール0。
for in rangeN。
アンサープラスイコール。
えー。
えー。
MのI番目、パーセント。
PのI番目、プリント。
アンス。
入力例1。
2が出たら、1が正解。
はい。
入力例2。
13は78が正解。
31。
全然ダメですね。
半分以下。
そもそも割り算?
あーと。
IをPで割った余り。
をMIとします。
まず、プリント。
MのI、パーセント。
PのI。
あ、ん?
M、いらないな、これ。
いらないね。
えーと。
レンジ。
Iプラス1ですね、これ。
Iプラス1をI1変数に入れとこう。
I1変数にIプラス1。
で、I1パーセントPのI番目にしておきましょう。
多少は軽くなるとかあんま関係ないか。
I1とPのI番目を出しつつ、I1パーセントPIをちょっと確認します。
1234560242200。
あ、偶数だと。
そうか。
偶数に偶数ぶつけるのは愚策か。
いやー。
解説を見ます。
これはちょっとむずいですね。
さすがD問題。
AをBで割った余りをAもどBと表すことにすると。
1もど2プラス2もど3プラス。
N-1もどNプラス。
これもどって言ってるのかな。
さっきやったやつですかね。
2分のNかけるN-1と順列を選ぶのが最適です。
以下これを説明します。
ん?あ、違う。
1個ずらしてるのか。
選んだ順列には1、2からNがそれぞれちょうど1回ずつ登場します。
Iイコール1、2、Nについて、Iが順列のX、I番目に登場するとします。
すると、目的関係。
すると、目的関数、最大化したいものは、X1もど1プラスX2もど2プラス、最後XNもどNになります。
各項に着目すると、それぞれの項は最大でも0、1、2からN-1ですが、I代なりイコール2について、XIイコールI-1とし、余ったNをX1イコールNとすると実際に、Nもど1プラス1もど2。
ふんふんふんふんふん。
0たす1たす2たす、とできるため、目的関数の最大値は、0たす1たす2たす、で、2分のNかけるN-1です。
ふんふんふんふん。
何を言いたいのかはわからんが、何を話しているのかはちょっとわかった気がしますね。
ユーザー解説の方も見てみます。
Nの上限が10の9乗なので、Nに起因するアルゴリズムではなさそう。
それで400点ということもあり、特殊な解法ではない。
それで400点ということもあり、特殊な解法ではない。
それで400点ということもあり、特殊な解法ではない。
本当にこの解法が存在するっぽい。
本当にこの解法が存在するっぽい。
というわけで実験してみよう。
234からN1のようにしていけばいいっぽい。
234からN1のようにしていけばいいっぽい。
234からN1のようにしていけばいいっぽい。
そうすると、1たす2たす3たすN-1が得られる。
つまり、N-1かけるN割る2が答え。
NアンスP。
NアンスP。
NアンスP。
なんか表を出してくれていますが、ちょっとよくわからないな。
他のユーザーの方のPythonの提出例を見てみてみます。
失礼を見て勉強しておきます
ではまた次回お疲れ様です