по-русски

ロシア語三日坊主

Round 499, A - Ступени (Stages)

Codeforces ロシア語チャレンジ

さっそく易しそうなのから見てみよう。

問題としての難易度が低いからといって文章が易しいとは限らないのだけれど、最近の問題で易しそうなもの（＝沢山の人がACしている問題）を開いてみる。

A. Ступени (Stages)

Задача - 1011A - Codeforces

タイトル

A. Ступени

露単語 読み(予想) 英訳 備考
ступени すとぅーぴに ストゥピェーニ stages ступень の複数形。"step"っぽい。ここではロケットの「段」。

時間制限・メモリ制限・入出力に関する情報

タイトル直下（問題文の上）の４行。

ограничение по времени на тест: 1 секунда
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

これは英語版だと

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

露単語 読み(予想) 英訳 備考
ограничение あぐらにちぇに アグラニチェーニエ limit (中) 制限、限定
на тест な てぃえすと per "test"
по ぱ ? (前置詞)+D〜に沿って、〜の関係の / +Ac〜まで /+L〜の後すぐ
времени ゔれみに ヴリェーミニ time (中)время "時間" の単数G/D/L
памяти ぱみゃてぃ パーミティ memory f.pl. 記憶、メモリ
секунда すぃくんだ "second" f.
мегабайт みがばぃと "megabytes" m.
стандартный すたんだるとぬぅぃ "standard" (adj.)
ввод / вывод ゔゔぉーど/ゔぃゔぉーど input / output

問題文の後半の入出力についての說明では Входные данные / Выходные данные という語が使われている。
ввод ←→ Входные
вывод ←→ Выходные
みたいな対応か。вで始まるのがinput, выで始まるのがoutputというのは分かる。（その後のвとхが入れ替わっているのは？）

露単語 読み(調べた) 英訳 備考
ввод ヴヴォート (m) input, introduction インプット、入力
вход フホート (m) entry, entrance インプット、入口
входной フハドノーィ entrance (adj.)
вывод ヴイーヴァト (m) ouput, outlet, conclusion アウトプット、出力、結論
выход ヴイーハト (m) way out, exit, outlet, output yield アウトプット、出口
выходной ヴイハドノーイ exit; day off (adj.) 外出用の、よそいきの、休日の

形容詞の語尾は性別（男性・中性・女性）で微妙に変わる。あとアクセントが後ろに来る。
あと格変化。

本文（1段落目）

Наташа собирается полететь на Марс. Ей необходимо построить ракету, которая собирается из нескольких ступеней в определённом порядке. Каждая из ступеней описывается одной строчной буквой латинского алфавита. Тем самым ракета описывается строкой — конкатенацией букв, соответствующих ступеням.

Наташа ナターシャ "Natasha"
собирается +inf. サビラーィツァ is going to, is about to, intend to 3sg. of собираться ; (cf.) se préparer à+inf
полететь パリチェーチ fly (inf.) 飛び立つ
на ナ to 前置詞 на は on(to) みたいな？それに対して в が in(to) で。
Марс マルス "Mars" 火星

「-ся」で終わる動詞って再帰動詞だよね…フランス語のse laverみたいなやつ。

というわけで、

ナターシャは火星に向けて飛び立とうとしている。

1文目が読めたぞ！

引き続き2文目。

Ей イェィ for her она (she) のDat/Inst
необходимо +inf. ニアブハヂーマ it is necessary 絶対必要だ、不可欠である
построить パストローイチ to build (строить) pf. 建てる、建設する、建造する
ракету らきぃえとぅ "rocket" f. Acc.＜ракета
которая カトーライ which f. ＜который ; ロケットが女性形なのでそれに一致
собирается さびらーぃつぁ - ←組み上がる感じ?
из いず from, of
нескольких にぇーすかりきひ some, several, few (pl.)
ступеней すとぅぴぇーにい stages, steps
в ゔ in +A/+L
определённом あぷりぢりょーんなむ (adj.L) certain, definite, fixed 硬.m.
порядке ぱりゃーとき order m.L ＜порядок

「-ом」で終わるのは名詞（男性)だとInst.sgだけど形容詞だとm.Loc.sg.なのね。→новым студентом (inst), новом студенте (Loc)

ロケットを建造することが彼女には必要である。
それ（ロケット）は何らかの順に並べられたいくつかの段から組み立てられる。

読めた！（関係代名詞はわざと2文に切るように訳してるよ）


3文目。

каждая かーじだい every, each (adj. f.Nom)＜каждый
из いず of
ступеней すとぅぴぇーにぃ stages 軟 f.Gen.pl : Inst.sgかGen.plなんだけどизの後だからGen.plに決まってる
описывается アピィスィヴァイツィ described 3sg. pf.＜описываться
одной あどのーぃ one, a f.Inst＜один
строчной すとろーちのぃ ストラチノーィ small (adj.) f.Inst
буквой ブークヴォィ letter f.Inst ＜буква (個々の)文字
латинского らてぃーんすかゔぁ "latin" (adj.,m.Gen) -гоって [-vo]になるやつかな
алфавита あるふぁゔぃーた "alphabet" (character set) (m.Gen) битаじゃなくてвитаなのね

[それぞれ (f.Nom) は] [段 (f.Gen.pl)の] [記述される(3sg)] [１つの 小文字 (f.Inst) によって] [ラテンアルファベット (m.Gen)の]
という構成になっている。格変化がきちんと拾えれば読める。

各段は小文字アルファベット１文字で記される。

4文目。

тем самым ちぇーむ さーむぃむ thus, thereby < the same
ракета らきぇーた "rocket" f.Nom
описывается アピィスィヴァイツィ described 3sg. pf.
строкой すとらこーぃ line, string f.Inst.＜строка; 行、文字列
конкатенацией かんかちなーつぃいぃ "concatenation" f.Inst.sg＜конкатена́ция
букв ぶーくゔ of letters f.Gen.pl.
соответствующих さあとゔぃえーつとふゆしちひ corresponding to (+D) соответствовать (不完) 形動詞 f.Gen.pl →буквと一致
ступеням すとぅぴぇーにむ (to the) stages f.pl.Dat

形動詞ってgerundive的な物かな。関係代名詞で繋ぐ代わりに使われるみたい。

そしてロケットは文字列 — 各段に対応した文字を結合したもの — によって記述される。

段落1つ読めた！

本文（2段落目）

Всего на складе есть n ступеней. Ракета должна содержать ровно k из них. Ступени в ракете должны быть упорядочены по весу. После ступени с некоторой буквой можно ставить только ступень с буквой, идущей хотя бы на две позиции позже в алфавите (то есть через одну букву или более). Например, после буквы 'c' нельзя ставить буквы 'a', 'b', 'c' и 'd', зато можно ставить 'e', 'f', ..., 'z'.

Всего フスィヴォー in all adv. 全部で、合計して
на ナ on +L
складе スクラーディ depot,store m.L.sg ＜склад 倉庫
есть いぇーすち (there)is ある・いる＜быть
n
ступеней すとぅぴぃえーにぃ ストゥピニェーィ stages 軟f.Gen.pl; "stage"のときは-ене́й, "step" のときは-е́нейらしい。生格になるのは数詞(n)のせい。

数詞の後はGen.が来るんだけど、

  • 1の後はNom.sg
    • 21, 31, ... でもNom.sg
  • 2,3,4の後はGen.sg（なぜ単数）
    • 22,23,24, 32,33,34, ... の後でもGen.sg
  • 5以上の後はGen.pl
    • 上記の例外を除くので5〜20, 25〜30, 35〜40, ...がGen.pl

のような規則になっているらしい。

倉庫には全部で n 段ある。

ракета らきぇーた "rocket" f.Nom
должна +inf どーるじゅな ダルジュナー must,should,due (adj.f.Nom)＜должен
содержать さでぃるじゃーち keep, contain inf.
ровно ろーゔな exactly,absolutely
k
из いず from,of
них にひ them

ロケットは、その中のちょうど k 段から成っていなければならない。

ступени すとぅぴぇーに stages f.Nom.pl
в ゔ in +L
ракете らきぇーち "rocket" f.Loc.
должны +inf だるじゅぬぃ must
быть ぶぃち "be"
упорядочены ウパリャーダチヌイ put in (good) order -ены は何
по ぱ +Dなので、〜に沿って、〜に従って
весу ゔぃえーす ヴィスー weight 硬m.Dat.sg 重さ

ロケットにおいて各段は重さに従って並べられなければならない。

после ぽーすりぃ after, since (adv.)
ступени すとぅぴぇーにぃ f.Nom.pl
с す with +G,+A,+I
некоторой にぇかたらぃ some f.Inst
буквой ぶーくゔぁぃ letter f.Inst
можно +inf. もーじゅな it is possible/can
ставить すたーゔぃち put,stand 立てる、置く
только とーりか only adv.
ступень すとぅぴぇーにぃ stage f.Nom.sg?
с す
буквой ぶーくゔぁぃ letter f.Inst.sg
идущей いどぅーしちぃ coming 形動詞 f.Inst.sg→буквойと一致
хотя бы even if, even though хотя=although, бы=仮定や願望; たとえ〜であろうとも、〜だけでも
на
две どぅゔぃえ two f.
позиции ぱずぃーつぃい "position" f.Gen.sg
позже ぽーじじぇ later (adj.) поздний, поздно の比較級。より遅い、後で
в ゔ +L
алфавите あるふぁゔぃーち "alphabet" m.Loc.sg
то есть とー いーすち that is (to say)
через ちぇーりず through +Acc. ～を横切って、～を越えて、～を通って、～後（先）に
одну one f.Acc.sg＜один
букву letter f.Acc.sg
или いーりぃ or
более ぼーりぃい more ←→менее

英語版だと "at least two positions after..." となっているけれど、хотя бы はそう訳せるのか。

何らかの文字をもつ段の後に置くことができるのは、アルファベットの中で位置２つだけでも後ろに来る（即ち、１文字かそれ以上飛び越えた）文字をもつ段のみである。

например なぷりみぇーる for example на + пример(example,instance)っぽい
после ぽーすりぃ after, since (adv.)
буквы ぶーくゔい letter f.Acc.pl.
'c'
нельзя +inf. にりずぃやー can't, mustn't ←→можно
ставить すたーゔぃち inf.
буквы ぶーくゔい letter f.Acc.pl.
'a', 'b', 'c'
и い and
'd'
зато ざとー but then, but on the other hand
можно + inf. もーじゅな
ставить すたーゔぃち inf.
'e', 'f', ..., 'z'

例えば、文字 'c' の後に 'a','b','c','d' を置くことはできないが、'e','f',...,'z' を置くことはできる。

本文（3段落目）

Чтобы ракета летела максимально далеко, нужно, чтобы её вес был минимален. Вес ракеты равен сумме весов её ступеней. Ступень весит столько тонн, каков номер её буквы в алфавите. Иными словами, ступень 'a' весит одну тонну, 'b' весит две тонны, а 'z' — 26 тонн.

чтобы しとーぶぃ in order to / that 〜するために; 従属文の動詞には、主文の主語と従属文の主語が一致するときは不定詞、一致しないときは過去形をとる
ракета らきぇーた "rocket" f.Nom
летела れてぃえーら to fly v. лете́ть 過去.f.sg
максимально まくしまーりな "maximal" adj. максимал-
далеко だりぇーか ダリコー far adv. 遠くに

ロケットが最大限遠くまで飛ぶために、

нужно ぬーじな should, need +inf, +чтобы ...
чтобы しとーぶぃ in order to / that 〜であることが(必要だ)
её いよー her (G/A)
вес ゔぇす weight m.Nom.sg
был ぶぃる (past) 主文の主語と従属文の主語が別なので過去形
минимален みにまーりん "minimal" adj. минимал-

その重さは最小である必要がある。

вес ゔぇす weight m.Nom.sg
ракеты らきぇーといぅぃ "rocket" f.Gen.sg
равен らーゔぃん equal adj. равный,短尾 m.sg
сумме すーんみ "sum" f.D?L?.sg сумма
весов ゔぃえさゔ ヴィソーヴ scales m.Gen.pl. of весы はかり
её いよー her (G/A)
ступеней すとぅぴぇーねぃ stage f.Gen.pl

ロケットの重さは、その段のはかりの重さの合計に等しい

ступень すとぅぴぇーに stage f.Nom.sg
весит ゔぃしとぅ to weigh весить, 3sg
столько すとーりか so much/many adv.(tel)
тонн とん "ton" f.Nom.sg
каков かこーふ what sort どんな、どのような(quel)
номер なみえーる ノーミル "number" m,Nom.sg
её いよー her (G/A)
буквы ぶーくゔい letter f.Acc.pl.
в алфавите ゔ あるふぁゔぃーち "alphabet" m.Loc.sg

段には、アルファベットの中でのその段の文字の番号分だけの重さがある。

иными словами いぬぅぃーみ すらゔぁーみ in other words ин- (adj)
ступень 'a' すとぅぴぇーに a stage f.Acc.sg
весит ゔぃえしと weighs весить, to weigh, 3sg
одну тонну あどぬ とんぬ 1t
'b'
весит ゔぃしとぅ weighs весить, to weigh, 3sg
две тонны どゔぇ とんぬぅぃ 2t
а あ 一方
'z'
26 тонн あ z - 26 とん 26t

言い換えると、段aは1tの重さ、bは2tの重さ、そしてzは26tである。

本文（4段落目）

Постройте ракету минимального веса или скажите, что ни одной ракеты построить нельзя. Каждую из ступеней на складе можно использовать не более одного раза.

постройте ぱすとろーぃちぃ build imp, построить; -йте は命令形の2.pl
ракету らきぇーとぅ f.Acc.sg
минимального みにまーりなゔぁ "minimal" m.Gen.sg.
веса ゔぃえーさ ヴィサー weight m.Gen.sg
или いりぃ or
скажите すかじぃーてぃ say imp ＜сказать
что しとー that
ни одной にぃ あどのーぃ not a f.Gen.sg
ракеты らきぇーとぅ f.Gen.sg
построить ぱすとろーいち to build inf.
нельзя にりずぃやー can't, mustn't

чтоの後（従属文）の語順、нельзя が最後に来るのってなんかドイツ語（の枠構造）みたいだと思った。

最小重量のロケットを建造せよ。あるいは、ロケットを1つも建造できないと言え。

каждую かーじゅどぅゆ every, each (adj. f.Acc.sg)＜каждый
из いず from, of
ступеней すとぅぴぇーにぃ stage f.Gen.pl
на な on +L
складе スクラーディ depot,store m.L.sg
можно +inf. もーじゅな can
использовать いすぽーりざゔぁち to use
не に not 無アクセント
более ぼーりぇ more (+G:than)
одного アドナヴォー one m.G.sg
раза ぱーざ time m.G.sg

倉庫にある各段は最大で１回使うことができる。

本文読めた！

Входные данные (入力データ)

входные フハドヌゥーイ input (adj.)
данные だーんぬぅい data

Первая строка входных данных содержит два целых числа — n и k (1≤k≤n≤50) — количество доступных ступеней и требуемое количество ступеней в ракете.

Вторая строка содержит строку s из n строчных букв латинского алфавита. Каждая из букв задаёт очередную ступень, которую можно использовать при постройке. Каждую ступень можно использовать не более одного раза.

первая ぴぇーるゔぁい first
строка すとらかー line, string f.Nom
входных ふはどぬぅーぃひ input (adj.)硬G.pl.
данных だーんぬぅぃひ data G.pl.
содержит さでぃるじーと keep, contain
два どぅゔぁー two
целых つぃえーるぃひ whole, entire, integer (adj.)
числа ちすらー number n. число
n и k (1≤k≤n≤50)
количество かりぃーちぇすとゔぁ quantity, amount number n.
доступных だすとぅーぷぬぃひ available, accessible
ступеней すとぅぴぇーにぃ stages
и い and
требуемое とりぇーぶいまい demand, require
количество かりぃーちぇすとゔぁ
ступеней すとぅぴぇーにぃ stages
в ゔ +L
ракете らきぇーてぃ "rocket" L

入力データの1行目には、2つの整数 — n と k (1≤k≤n≤50) — すなわち利用できる段の数と、ロケットに求められる段の数が入っている。

вторая ふたらーい second (adj.) f.Nom.sg
строка すとらかー line, string f.Nom.sg
содержит さでぃるじーと keep, contain
строку すとらくー line, string
s
из いず from
n
строчных すとらちぬぅーぃひ small, lower-case adj.
букв ぶーくゔ letter
латинского алфавита らてぃーんすかゔぁ あるふぁゔぃーた latin alphabet

2行目にはn文字の小文字ラテンアルファベットから成る文字列sが入っている。

каждая かーじだい each
из いず of
букв ぶーくゔ letter f.Gen.pl of буква
задаёт ざだよーと set, give задавать 課する; 3sg
очередную あちりどぬーゆ next, next in turn (adj.) f.Acc.sg. 当面の、次の;
ступень すとぅぴぇーに stage f.Acc.sg
которую かとーるゆ which (関係) который；f.Acc.sg
можно использовать もーじな いすぽーりざゔぁち can use
при ぷりー by, with, about, on, for
постройке ぱすとろーぃき building f. постройка

それぞれの文字は建造に使うことのできる次の段を与える。

каждую かーじゅどぅゆ every, each (adj. f.Acc.sg)＜каждый
ступень すとぅぴぇーに stage f.Acc.sg
можно использовать もーじな いすぽーりざゔぁち can use
не более одного раза に ぼーりぇ あどなゔぉー ぱーざ not more than once

各段は1回までしか使えない。

Выходные данные (出力データ)

выходные ヴイハドヌゥーイ output (adj.)
данные だんぬぅい data

Выведите одно число — минимальный суммарный вес ракеты или -1, если ни одной ракеты построить нельзя.

выведите ゔぅぃゔぃでぃち find out imp
одно あどのー one
число ちすろー number n.
минимальный みにまーりぬぅぃ "minimal" (adj.) m.Nom.sg
суммарный すむまーるぬぅぃ total, "summary" (adj.) m.Nom.sg
вес ゔぇーす weight m.
ракеты らきぇーとぃ "rocket" f.Gen.sg
или いりぃ or
-1
если いぇーすりぃ if
ни одной ракеты построить нельзя に あどのーぃ らきぇーとぅ ぱすとろーいち にりずぃやー none of rocket can't be build

数を１つ — ロケットの最小合計重量、あるいはもし１基もロケットを建造できなければ -1 を — 求めよ。

解いてみよう

訳文を改めて読んでみる。

ナターシャは火星に向けて飛び立とうとしている。ロケットを建造することが彼女には必要である。ロケットは何らかの順序をなすいくつかの段階から組み立てられる。それぞれの段階は小文字アルファベット１文字で記される。そしてロケットは文字列 — 各段階に対応した文字を結合したもの — によって記述される。

倉庫には全部で n 段ある。ロケットは、その中のちょうど k 段から成っていなければならない。ロケットにおいて各段は重さに従って並べられなければならない。何らかの文字をもつ段の後に置くことができるのは、アルファベットの中で位置２つだけでも後ろに来る（即ち、１文字かそれ以上飛び越えた）文字をもつ段のみである。例えば、文字 'c' の後に 'a','b','c','d' を置くことはできないが、'e','f',...,'z' を置くことはできる。

ロケットが最大限遠くまで飛ぶために、その重さは最小である必要がある。ロケットの重さは、その段のはかりの重さの合計に等しい。段には、アルファベットの中でのその段の文字の番号分だけの重さがある。言い換えると、段aは1tの重さ、bは2tの重さ、そしてzは26tである。

最小重量のロケットを建造せよ。あるいは、ロケットを1つも建造できないと言え。倉庫にある各段は最大で１回使うことができる。

入力データ

入力データの1行目には、2つの整数 — n と k (1≤k≤n≤50) — すなわち利用できる段の数と、ロケットに求められる段の数が入っている。

2行目にはn文字の小文字ラテンアルファベットから成る文字列sが入っている。それぞれの文字は建造に使うことのできる次の段を与える。各段は1回までしか使えない。

出力データ

数を１つ — ロケットの最小合計重量、あるいはもし１基もロケットを建造できなければ -1 を — 求めよ。

アルファベット数は高々26種類（ということは最大で13段までのロケットしか建造できないでしょ）だし、愚直にやっても構わないと思うんだけど

#include <bits/stdc++.h>
using namespace std;

int solve(int n, int k, string& s) {
  if (s.size() == 0) return -1;

  set<char> s_uniq;
  for (char ch : s) s_uniq.insert(ch);

  vector<int> w;
  for (char ch : s_uniq) w.push_back(ch - 0x60);

  int total = 0, cnt = 0, last = 0;

  while (true) {
    total += w[last];

    ++cnt;
    if (cnt == k) return total;

    auto it = lower_bound(w.begin()+last+1, w.end(), w[last]+2);
    if (it == w.end()) return -1;

    last = (int)(it - w.begin());
  }
}

int main() {
  int n, k; cin >> n >> k;
  string s; cin >> s;

  cout << solve(n,k,s) << endl;
  return 0;
}

→AC
http://codeforces.com/problemset/submission/1011/40980471
f:id:n4_t:20180731023530p:plain

感想

問題１問読み終わらないうちにコンテスト終わっちゃうよー

また気が向いたらやる。