AtCoderを試す
takker.icon
何か1問やってみる
1問にどのくらい時間がかかるのかがそもそもわからない
10分以内に終わりそうならいいが、1時間以上かかるようなら少し考える
とりあえずAtCoderを体験したいだけなら、10分で終わるものも沢山ありますblu3mo.icon
ありがとうございます！takker.icon
✅アカウント作成
takkerは予約済み。残念
takker99にした
メール通知は重要なメールを受け取るだけにした
作成完了！
practice contestのA問題を解く
https://gyazo.com/18f0f033a3267bdb2e13f55f8601aae2
https://gyazo.com/12beb28ba1535001af35968ef209f42d
やるぞ～
Denoで書けるかな？
https://gyazo.com/7a6f42d715fc73a2068bf3c869445519
有 能takker.icon
完 全 勝 利
すばらしい
問題A
code:input
a
b c
s
a,b,cは数値
sは文字列
出力：\`${a+b+c} ${s}\`
Denoに標準入力がどう渡されるのかがいまいちわからないな https://gyazo.com/729e238f2e9f71df0f14daf5d8fed236
JavaScript + Node.jsだとこんな感じらしいですblu3mo.icon
最後の行で/dev/stdinから読み取っている
ファイル経由になるのかーtakker.icon
試してみる
違った
code:ts
console.log(Deno.args);
code:output2
ビンゴ！
$ console.log(await (new Response(Deno.stdin.readable)).text())
で通った
ならこれでpassするかな
code:Welcome to AtCoder.ts
const text = await (new Response(Deno.stdin.readable)).text();
const b, c = bc.split(" "); console.log(${parseInt(a)+parseInt(b)+parseInt(c)} ${s});
提出
https://gyazo.com/dc61093cdaa9b2b6c2efaf0925d25a25
passed!!! わーい！
https://gyazo.com/f080c6f24498fc8c67051d86fe27e17a
/icons/祝.iconblu3mo.iconcFQ2f7LRuLYP.icon
読んでみたtakker.icon
N個のボールがあり、それぞれ大文字の名前がついている
e.g. N=4ならABCDの4つ
それぞれ重さが設定されている
任意の2つのボールを選び、重さの比較を最大Q回尋ねられる
stdoutで? A Bの形式で尋ねると、stdinに>か<が返ってくる
軽い順にソートし終わったら終了
Q回の間にソートし終わらなかったときの動作は未定義
ソート途中の文字列を適当に返せばいいでしょtakker.icon
つまり、sort algorithmを実装すればいいのか
なにげにsorting algorithm実装したこと一度もないtakker.icon
まあ適当に書けばいいでしょ
code:Interactive Sorting.ts
const getStdinAsText = async (): Promise<string> => new TextDecoder().decode(
(await stdinIter.next()).value
);
const matched = (await getStdinAsText()).match(/(\d+)\s(\d+)/) ?? [];
const N = parseInt(matched1); const Q = parseInt(matched2); /** n=0で"A"を返す */
const toChar = (n: number):string => String.fromCharCode(65 + n);
const ask = async (a: string, b: string): Promise<-1 | 1> => {
console.log(? ${a} ${b});
const input = await getStdinAsText();
// 改行が入ってしまうようなので、trimしておく
switch (input.trim()) {
case "<":
return -1;
case ">":
return 1;
dafault:
throw new Error("不正な値を入れやがったな！シベリア送りだ！！");
};
throw new Error("こんなところにきたやつはシベリア送りだ！！");
};
const sort = async <T>(list: T[], compareFn: (a: T, b: T) => Promise<number>): Promise<T[]> => {
// 比較結果をcacheする
const cache = new Map<string, number>();
const compare = async (a: T, b: T): Promise<number> => {
const key = ${a} ${b};
const cached = cache.get(key) ?? await compareFn(a, b);
cache.set(key, cached);
return cached;
};
/** targetをsort済みのsortedに挿入する */
const insert = async (sorted: readonly T[], target: T, offset?: number, length?: number): Promise<T[]> => {
offset ??= 0;
length ??= sorted.length;
if (length === 0) return target; if (length === 1) {
if ((await compare(target, sortedoffset)) < 0) { } else {
}
}
// 二分探索っぽく挿入位置を決定する
if (length % 2 === 0) {
// ... | before | after | ...
// ↑ ↑ どちらに入るか調べる
const newLength = length / 2;
if ((await compare(target, after)) < 0) {
return await insert(sorted, target, offset, newLength);
} else {
return await insert(sorted, target, offset + newLength, newLength);
}
}
// ... | before | middle | after | ...
// ↑ ↑ どちらに入るか調べる
const newLength = (length - 1) / 2;
if ((await compare(target, middle)) < 0) {
return await insert(sorted, target, offset, newLength);
} else {
return await insert(sorted, target, offset + newLength + 1, newLength);
}
};
let sorted: T[] = [];
for (const target of list) {
sorted = await insert(sorted, target);
}
return sorted;
};
// test
// console.log(await sort(chars, (a,b) => Promise.resolve(new Intl.Collator().compare(a,b))))
console.log(! ${(await sort(chars, ask)).join("")});
（atcoderにinteractive形式の問題はほとんどないので、面倒だったら飛ばしても良さそうです）blu3mo.icon
👍blu3mo.icon
飽きたら飛ばして次に行きますtakker.icon
無限ループになっちゃった
変数ミスだった
10:55:16 sortの実装問題なさそう
for awaitで1文ずつ取り出す必要がある
Q使わなかったけど別にいいか
11:10:20 コードテストだとinteractiveモードを試せないのでは？takker.icon
標準入力に改行つきのテキストを入力しても、一回のnext()で改行も含んだ標準入力が全部得られてしまう
これ以上テストのしようがないな……
localで試せばいいか
✅いやいや、C,Aを2回聞く必要ないでしょ
code:log
3 10
? B A
<
? C A
? C A
<
! BCA
あー、アルゴリズムが雑で、2回聞くパターンがでてきてしまうのか
結果をcacheすればいいや
直った
11:22:17 提出したけど全部エラーになっちゃった！
interactiveの挙動わからん！
飛ばそう
IDE/エディタ補完なしでコード書いているのなにげにすごいなblu3mo.icon
見てるnishio.icon
次はこれをやればいいのか。なるほどtakker.icon
これが上の記事で言及されてる「過去問精選 10 問」かblu3mo.icon
11:23:28 1,2問やって終わりにしようtakker.icon
問題Aと同じ
コピペして提出した
code:ts
const text = await (new Response(Deno.stdin.readable)).text();
const a, b = text.split(" "); console.log(${(parseInt(a) * parseInt(b)) % 2 === 0 ? "Even" : "Odd"});
1の個数を数えればいい
例101→2
code:ts
const text = await (new Response(Deno.stdin.readable)).text();
console.log(text.split("").filter((i) => i === "1").length);
与えられた数値を$ (2n+1)\cdot 2^mもしくは$ 2^mと分解したとき、その$ mの最小値を求める問題
2進数表記したときの、最下位からの0の数を求めればいい
てことは、すべての数を|しちゃったものの0の数を数えればいいということか
code:ts
const text = await (new Response(Deno.stdin.readable)).text();
// Nは使わない
const result = list.reduce((acc,cur) => acc | parseInt(cur), 0);
console.log(result.toString(2).match(/0+$/)?.0?.length ?? 0); 問題文の意図は、>>で0の数を求めよということなのだろうが、そんなこと知ったことか
求まればいいのさtakker.icon
11:45:07 とりあえずこんなものでいいや
いい問題だな、問題文の通りに実装するとタイムアウトするんだなnishio.icon
2点間をn操作で移動できるか判定する問題に帰着できるということかtakker.icon
問題が複雑になってくると紙が欲しくなるtakker.icon
数式と図の記述
脳内だけで図解できないこともないが、時間制限があるときつい