AtCoderを試す
何か1問やってみる
1問にどのくらい時間がかかるのかがそもそもわからない
10分以内に終わりそうならいいが、1時間以上かかるようなら少し考える
とりあえずAtCoderを体験したいだけなら、10分で終わるものも沢山あります

ありがとうございます!

✅アカウント作成
takker
は予約済み。残念
takker99
にした
メール通知は 重要なメールを受け取る
だけにした
作成完了!
practice contestのA問題を解く
やるぞ~
Denoで書けるかな?
有 能

完 全 勝 利
すばらしい
問題A
a,b,cは数値
sは文字列
出力: \
${a+b+c} ${s}\
Denoに
標準入力がどう渡されるのかがいまいちわからないな
JavaScript + Node.jsだとこんな感じらしいです

最後の行で/dev/stdinから読み取っている
ファイル経由になるのかー

試してみる
違った
tsconsole.log(Deno.args);
output2[ "ONLINE_JUDGE", "ATCODER" ]
ビンゴ!
$ console.log(await (new Response(Deno.stdin.readable)).text())
で通った
ならこれでpassするかな
Welcome to AtCoder.tsconst text = await (new Response(Deno.stdin.readable)).text();
const [a, bc, s] = text.split("\n");
const [b, c] = bc.split(" ");
console.log(`${parseInt(a)+parseInt(b)+parseInt(c)} ${s}`);
提出
passed!!! わーい!
読んでみた

N
個のボールがあり、それぞれ大文字の名前がついている
e.g. N=4
なら ABCD
の4つ
それぞれ重さが設定されている
任意の2つのボールを選び、重さの比較を最大 Q
回尋ねられる
stdoutで ? A B
の形式で尋ねると、stdinに >
か <
が返ってくる
軽い順にソートし終わったら終了
Q
回の間にソートし終わらなかったときの動作は未定義
ソート途中の文字列を適当に返せばいいでしょ

つまり、sort algorithmを実装すればいいのか
なにげにsorting algorithm実装したこと一度もない

まあ適当に書けばいいでしょ
Interactive Sorting.tsconst stdinIter = Deno.stdin.readable[Symbol.asyncIterator]();
const getStdinAsText = async (): Promise<string> => new TextDecoder().decode(
(await stdinIter.next()).value
);
const matched = (await getStdinAsText()).match(/(\d+)\s(\d+)/) ?? [];
const N = parseInt(matched[1]);
const Q = parseInt(matched[2]);
/** n=0で"A"を返す */
const toChar = (n: number):string => String.fromCharCode(65 + n);
const chars = [...Array(N).keys()].map((_,i) => toChar(i));
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, sorted[offset])) < 0) {
return [...sorted.slice(0, offset), target, ...sorted.slice(offset)];
} else {
return [...sorted.slice(0, offset + 1), target, ...sorted.slice(offset + 1)];
}
}
// 二分探索っぽく挿入位置を決定する
if (length % 2 === 0) {
// ... | before | after | ...
// ↑ ↑ どちらに入るか調べる
const newLength = length / 2;
const after = sorted[offset + newLength];
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;
const middle = sorted[offset + newLength];
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([97,4,31,34,6,53,45,5], (a,b) => Promise.resolve(a-b)))
console.log(`! ${(await sort(chars, ask)).join("")}`);
(atcoderにinteractive形式の問題はほとんどないので、面倒だったら飛ばしても良さそうです)

👍

飽きたら飛ばして次に行きます

無限ループになっちゃった
変数ミスだった
10:55:16 sort
の実装問題なさそう
for await
で1文ずつ取り出す必要がある
Q
使わなかったけど別にいいか
11:10:20 コードテストだとinteractiveモードを試せないのでは?

標準入力に改行つきのテキストを入力しても、一回の next()
で改行も含んだ標準入力が全部得られてしまう
これ以上テストのしようがないな……
localで試せばいいか
$ deno run -r=https://scrapbox.io https://scrapbox.io/api/code/villagepump/AtCoderを試す/Interactive%20Sorting.ts
✅いやいや、C,Aを2回聞く必要ないでしょ
log3 10
? B A
<
? C A
>
? C A
<
! BCA
あー、アルゴリズムが雑で、2回聞くパターンがでてきてしまうのか
結果をcacheすればいいや
直った
11:22:17 提出したけど全部エラーになっちゃった!
interactiveの挙動わからん!
飛ばそう
IDE/エディタ補完なしでコード書いているのなにげにすごいな

見てる

次はこれをやればいいのか。なるほど

これが上の記事で言及されてる「過去問精選 10 問」か

11:23:28 1,2問やって終わりにしよう

問題Aと同じ
コピペして提出した
tsconst 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
tsconst 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の数を数えればいいということか
tsconst text = await (new Response(Deno.stdin.readable)).text();
// Nは使わない
const [N, ...list] = text.split(/\s/);
const result = list.reduce((acc,cur) => acc | parseInt(cur), 0);
console.log(result.toString(2).match(/0+$/)?.[0]?.length ?? 0);
問題文の意図は、 >>
で0の数を求めよということなのだろうが、そんなこと知ったことか
求まればいいのさ

11:45:07 とりあえずこんなものでいいや
いい問題だな、問題文の通りに実装するとタイムアウトするんだな

2点間をn操作で移動できるか判定する問題に帰着できるということか

問題が複雑になってくると紙が欲しくなる

数式と図の記述
脳内だけで図解できないこともないが、時間制限があるときつい