手紙を送るための切手の枚数
AtCoder Beginner Contest 233回目。A問題。10円スタンプ。問題文。サンタさんに手紙を出したい高橋くんは、X円切手が1枚だけ貼られた封筒を用意しました。
サンタさんに手紙を届けるためには、貼られている切手の総額がY円以上である必要があります。
高橋くんは、この封筒に10円切手を何枚か貼り足すことで、貼られている切手の総額をY円以上にしたいです。
高橋くんは、この封筒に最小で何枚の10円切手を貼り足す必要がありますか?
XとYが与えられます。
元々の切手X円の切手が貼られていて、そこに10円を足していく。何円足しますか?Yを超えるのは何円ですか?
だから、XとYをmapIntInput.splitして、while X小なりYの間、Xプラスイコール10。
で、その前にansansw0を用意しておいて、ansプラスイコール1でプリント、ansでいいんじゃない?
提出。はい、閉鎖したのでB問題いきまーす。B問題。
あ、リバース。問題文。整数L、RとA小文字のみからなる文字列Sが与えられます。
SのL文字目からR文字目までの部分を反転した、すなわちL文字目からR文字目までの文字の並びを逆にした文字列を出力してください。
L、RとSが与えられます。
コードテストで一応用意しておきましょうか。
LとRイコールマップIntInput.splitでSイコールインプット。
そうだなぁ。そうだなぁ。どうしようかなぁ。
プリントSのL文字目からR文字目、だからSのカンマLでLの手前まで行くから、プラスSのLからRプラス1をカンマカンママイナス1でマイナスに反転しない?これ。
プラスL、SのRからRプラス1でいかがでしょうか。これで出てくれたらだいぶ楽なんだけど。
ABC HGF?
ABCH?あれ?なんで?
Lマイナス1?SのLマイナス1番目?出力量はABCHが出ているのはなんでだ?
ちょっと反転させるべき範囲のところをピックアップしましょうか先。Hが入っちゃってるから。
あ、そうか。0インデックスだから。GFET。3文字目から7文字目。もう1個だね。
LR。Lをマイナス1したらいいんだ。Lマイナスイコール1しといて。
はいはいはい。で、
SのLプラスSのLからRまでを反転させたやつプラスSのRから先。
どうですか?ABGFEDCH?
ABGFEDCH。
合ってるね。入力例2は
同じ。レビバー。メリークリスマス。
入力例3。大丈夫そうですね。提出していきます。
通っておくれ。ACしたので新問題です。
袋からボールを取り出す組み合わせ
新問題。プロダクト。問題文。N個の袋があります。袋iにはLi個のボールが入っていて、袋iのJ。
Jは1以上Li以下。J番目のボールには正の整数AiJが書かれています。
それぞれの袋から一つずつボールを取り出します。取り出したボールに書かれた数の総積がXになるような取り出し方は何通りありますか?
ただし書かれた数が同じであってもすべてのボールは区別します。
制約はNが2以上Liも2以上。
袋に入っているボールの個数の総積は10の5乗を超えない。
すなわち何これ?
ローマ数字の2みたいなもの。上だけくっついてるやつ。
たぶんiイコール1が下にあって上に大文字Nがあるので、Nに行くまでのiイコール1をプラス1していってLのi番目っていうのが10の5乗以下ってことですね。
この記号が総積の意味なのかな。N番目までLiをかけていってもその結果は10の5乗以下ですよっていうのを表示する記号でしょうね。
条件1小なりイコールai j 小なりイコール10の9乗。
1小なりイコールx 小なりイコール10の18乗。入力に含まれる値はすべて整数である。
N個の袋があります。袋iにはLiのボールが入っていて
それぞれの袋から1つずつボールを取り出します。
総積がxになるような取り出し方。何番目のボールとかは特に関係ないのかな。
書かれた数が同じであってもすべてのボールは区別することに注意してください。
そうかどうしようかな。
愚直に考えるなら4分なんですが絶対にオーバーしますよね。C問題4分で解けたことほとんどないので。
袋1の3番目のボールと袋2の1番目のボールを選ぶと4×10で40となります。
一番最初はボールの数か。それぞれの行の一番最初の文字数字がボールの数で袋の中に入っている文字数字の数数字の数数字が表示されている。
点でわからんな。 4分で1個ずつ試してもいいが、
取り出したボールに書かれた数の総積、それぞれの袋から1つずつボールを取り出します。
1回4分でやってみますか。ちょっと思いついたことから地道にね。
nx イコールマップのイントのインプットスプリット
で l を作っておきましょう。空のリストで for i in range
n 回 l に入れます。
先に a をリストで
リストのマップの
イントのインプットドットスプリットで l ドットアペンド
a にする前に
する前に
a ドットソーとしておいて
あ、そうか。
a の一文字目は関係ないというか文字
袋に入っているボールの数じゃないので a の
一文字目からですね。ソーとして
l ドットアペンド a の一文字目からをアペンドします。 一応ちょっと確認しておきましょう。プリント l で
各行の一文字目がカウントされていないので ok ですね。
ソートがかかっていないな。ソートがかかっていない。
ソーテッドにしとく。ソーテッド。
これでどうでしょうか。
ドットソートだと変数に入れ直さないといけないのかな。確か。
で、こっからが
in range n
マイナス1 4j
4j かこれ。袋の数だけやらないといけないんでしょ。袋の数だけ
4文を作るのは
ダメじゃないか。
ファイル分を作るかどうか。今ソート順で各ボールを
小さい順に並べました。で l に入れました。
どうしようかな。 エナムレイト関数みたいなのなかったっけ。
パイソン使い方。 これなんかリスト内のまとめた数字をどうこうみたいな
関数じゃなかったですっけ。
ソーセキ。パイソンソーセキ求め方とかで出ないかな。
パイソンソーセキ。ソーセキが出てこない。
ソーセキとソーはサム。サム関数じゃなさそうだなぁ。
ソーは ナムパイ、プロット。指定した軸に沿って要素の
総積を計算します。 ナムパイね。ナムパイありじゃない?
順番にっていうのはできないな。アクシスに1を渡すと横軸に沿って積を計算します。
アクシス。 縦軸を縦軸に沿って計算してくれないのかな。
あった。縦軸に沿って要素の結晶。 でもこれ縦一直線。縦軸に沿って要素の積を計算。
渡した配列の次元を保持します。アクシスに1を渡すと横軸に沿って積を計算します。
相乗のまとめ方。
相和と相乗。 リスト内のすべての要素を掛け算する。
すべての要素ではないんだよなぁ。 相乗の記号をパイって読むんだ。
相乗。 ちょっとパッと出てこないですね。調べ方が悪そうな気がするので、
今のところ配列全部の層列、層積を求めるようなページしか出てきていないので、
各リストから要素を抽出してっていうのがちょっとわかんないので、解説見てみましょうか。
公式解説。DFS。深さ優先探索で解くことができます。DFSは始めのうちは実装が難しいかもしれないので、下に示した実装例も参考にしてください。
また計算途中はオーバーフローに気をつけましょう。C++で書いてますね。
が公式解説。ユーザー解説もあるので、 ちょっと見てみましょうか。
解法。L1×…LNは小なりイコール10の五乗なので、Iイコール12…Nに対して1小なりイコールJI、小なりイコールLIを満たすようなものを全探索できる。
よって深さ優先探索や直積集合、これ初めて聞いたの。直積集合を生成することにより実際に計算して、
A1、JI、J1×…がXかどうかを判定して条件を満たす組の数を出力すれば良い。
なおこの問題は動的計画法DPでも解くことができる。DPIXを最初からIコまで見て積はXであるような組の数とする。
計算量について、そもそもXの約数ではないようなsmall x について考慮しなくても良く、
その工夫により10の18乗以下の整の整数で約数の個数は最大でも10万3680個であり、
LI大なりイコール2、L1×…LN小なりイコール10の5乗という制約からN小なりイコール16である。
よってこのような動的計画法でも十分高速である。詳細は可筆するかもしれない。
では答えの行動を後で見ておこうと思います。
今回はここまでということでお疲れ様でした。また次回お会いしましょう。