generated at
AtCoderを試す

takker
AtCoderのアカウントを作る
何か1問やってみる
1問にどのくらい時間がかかるのかがそもそもわからない
10分以内に終わりそうならいいが、1時間以上かかるようなら少し考える
とりあえずAtCoderを体験したいだけなら、10分で終わるものも沢山ありますblu3mo
好きな言語を使えるので、各言語の解法はこちらを参照 百花繚乱!なないろ言語で競技プログラミングをする資料まとめ #AtCoder - Qiita
ありがとうございます!takker

✅アカウント作成
takker は予約済み。残念
takker99 にした
メール通知は 重要なメールを受け取る だけにした
作成完了!
practice contestのA問題を解く
参加登録 を押したあと、A問題に移動する
やるぞ~
Denoで書けるかな?
有 能takker
完 全 勝 利
すばらしい
問題A
input
a b c s
a,b,cは数値
sは文字列
出力: \ ${a+b+c} ${s}\
Denoに標準入力がどう渡されるのかがいまいちわからないな
コードテストがあるから、それを使ってみよう
JavaScript + Node.jsだとこんな感じらしいですblu3mo
最後の行で/dev/stdinから読み取っている
ファイル経由になるのかーtakker
DenoだとDeno.argsがあるから、それかなと見当付けてます
試してみる
違った
ts
console.log(Deno.args);
output2
[ "ONLINE_JUDGE", "ATCODER" ]
じゃあDeno.stdinかな?
ビンゴ!
$ console.log(await (new Response(Deno.stdin.readable)).text())
で通った
ならこれでpassするかな
Welcome to AtCoder.ts
const 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!!! わーい!
祝blu3mocFQ2f7LRuLYP
問題B - Interactive Sortingは初心者向けではないらしい
読んでみたtakker
N 個のボールがあり、それぞれ大文字の名前がついている
e.g. N=4 なら ABCD の4つ
それぞれ重さが設定されている
任意の2つのボールを選び、重さの比較を最大 Q 回尋ねられる
stdoutで ? A B の形式で尋ねると、stdinに > < が返ってくる
軽い順にソートし終わったら終了
Q 回の間にソートし終わらなかったときの動作は未定義
ソート途中の文字列を適当に返せばいいでしょtakker
つまり、sort algorithmを実装すればいいのか
なにげにsorting algorithm実装したこと一度もないtakker
まあ適当に書けばいいでしょ
Interactive Sorting.ts
const 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形式の問題はほとんどないので、面倒だったら飛ばしても良さそうです)blu3mo
みたいですね。紹介してくださった記事にも書いてありましたtakker
👍blu3mo
飽きたら飛ばして次に行きますtakker
無限ループになっちゃった
変数ミスだった
10:55:16 sort の実装問題なさそう
10:58:13 Deno.stdinを全部消費してしまうと、次の入力を受け取れないようだ
for await で1文ずつ取り出す必要がある
もしくはwindow.prompt()を使う
Q 使わなかったけど別にいいか
11:10:20 コードテストだとinteractiveモードを試せないのでは?takker
標準入力に改行つきのテキストを入力しても、一回の next() で改行も含んだ標準入力が全部得られてしまう
これ以上テストのしようがないな……
localで試せばいいか
$ deno run -r=https://scrapbox.io https://scrapbox.io/api/code/villagepump/AtCoderを試す/Interactive%20Sorting.ts
✅いやいや、C,Aを2回聞く必要ないでしょ
log
3 10 ? B A < ? C A > ? C A < ! BCA
あー、アルゴリズムが雑で、2回聞くパターンがでてきてしまうのか
結果をcacheすればいいや
直った
11:22:17 提出したけど全部エラーになっちゃった!
interactiveの挙動わからん!
飛ばそう
IDE/エディタ補完なしでコード書いているのなにげにすごいなblu3mo
コーディング面接とかで役に立ちそうblu3mo

見てるnishio
次はこれをやればいいのか。なるほどtakker
これが上の記事で言及されてる「過去問精選 10 問」かblu3mo
11:23:28 1,2問やって終わりにしようtakker
問題Aと同じ
コピペして提出した
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
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の数を数えればいいということか
ts
const 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の数を求めよということなのだろうが、そんなこと知ったことか
求まればいいのさtakker
11:45:07 とりあえずこんなものでいいや
次回は残りを全部やった後、https://atcoder.jp/contests/abs/tasks/arc089_a をやる

いい問題だな、問題文の通りに実装するとタイムアウトするんだなnishio
2点間をn操作で移動できるか判定する問題に帰着できるということかtakker

問題が複雑になってくると紙が欲しくなるtakker
数式と図の記述
脳内だけで図解できないこともないが、時間制限があるときつい