ปีนี้ใช้คอมใหม่ (ยังไม่ได้บล็อคเรื่องคอมใหม่สักที) ไม่ได้จัดอุปกรณ์ต่างๆ ที่สะสมไว้ให้เรียบร้อย ก็เลยต้องเริ่มจาก 0 และด้วยคิดว่า cjlib runner มันไม่จำเป็น มันเป็น overhead ก็เลยมีความคิดว่า เออ ลองเขียนเป็น C++ ดูดีกว่า น่าจะสนุก
Counting sheep
โจทย์ข้อนี้คือให้ N มา แล้วให้นับตั้งแต่ N, 2N, 3N, 4N, … โดยแต่ละครั้งให้จดตัวเลขในแต่ละหลักไว้ด้วย ถ้าเลขที่จดมีครบ 0-9 เมื่อไรให้คืนค่า xN ออกมา
ข้อนี้พบว่าพอเป็น C++ แล้วมันก็บังคับวิธีคิดเราอีกแบบ คือในลูปบรรทัดที่ 19 ถ้าเป็น Python เราจะ cast เป็น string แล้ววน ซึ่งมันเข้าใจง่ายกว่าการใช้ int (ที่ต้องมีบรรทัด 20 + 23 ให้อ่านแล้วต้องตีความ)
พบว่า cin
ก็อ่าน input ง่ายดีนะ
Revenge of the Pancakes
โจทย์ข้อนี้ให้ string --+-
มา แล้วให้ทำให้เป็น ++++
ทั้งหมด โดยใช้วิธีกลับเครื่องหมายทุกตัวตั้งแต่ตัวที่ 0 – n ได้ เช่น n = 2 ก็จะกลายเป็น ++-+
ที่สงสัยคือวิธีคิดเราง่ายมาก แต่ content analysis กลับคิดอะไรยากมากจนเรางงว่าวิธีเรามันผิดในทางคณิตศาสตร์หรือยังไง runtime ที่ใช้รันข้อ large เราก็แค่ 0.003s ด้วย
วิธีที่ใช้คือแบบนี้ครับ นับจากขวามือ เจอตัว -
ตัวแรกเมื่อไรให้หยุดแล้วกลับทุกตัวด้านหน้ารวมถึงตัวนั้น ฉะนั้นจากข้อตัวอย่างก็จะเป็น
ครั้งที่ | n (0-index) | Output |
---|---|---|
เริ่ม | – | --+- |
1 | 3 | ++-+ |
2 | 2 | --++ |
3 | 1 | ++++ |
ข้อนี้พบปัญหากับ cin
นิดหน่อย คือมันไม่อ่าน \n
เข้ามา ทำให้ต้องมาอ่านทิ้งอีกในบรรทัดที่ 49
Coin Jam
ข้อนี้จะใช้ C++ แล้วก็พบว่าใช้ itertools
น่าจะไวกว่า ก็เลยจัด itertools + mathapi ตามสไตล์เดิมมา
ข้อนี้ผมก็ใช้วิธีตรงๆ โง่ๆ นี่แหละครับ
- Generate ตัวเลขมาก่อน โดยใช้
itertools.product('01', repeat=n-2)
สร้างตรงกลางมา แล้วเอา 1 ประกบหน้าหลังตามที่โจทย์กำหนดว่าต้องขึ้นต้นและลงท้ายด้วย 1 ตรงนี้ดีที่itertools
สร้างเป็นtuple
ออกมาทำให้มัน generate กรณีที่มี 0 นำได้ไม่มีปัญหา - Cast และ cache เป็นเลขฐานต่างๆ ตั้งแต่ 2-10
- เช็คว่าเลขแต่ละตัวเป็น prime number ไหม ตรงนี้ใช้ mathapi เลย ง่ายและไวดี
- ถ้าใช่ก็ให้ mathapi หา factor แล้วตอบ
โค้ดที่เห็นนี่ optimize ไปนิดหน่อยละครับ แต่ก็ไม่ต่างกับเดิมมากนัก
ปัญหาของข้อยากคือ ผมก็ไม่เอะใจว่ามันให้ข้อยากมากแล้ว คือโจทย์ก็เขียนนะว่าไฟล์รับเข้าให้มาหมดแล้ว แต่ผมก็เห็นแค่ของ small ไม่เห็น large เลยนึกว่าไม่มี ปรากฏว่ามันให้เป็นตัวเลขมาแล้วไปเขียนไฟล์เอง ก็เลยไม่ได้ลองรันดู พอรันดูจริงๆ ก็พบว่าตัวเลขมันใหญ่มาก prime รันไม่ทัน ก็เลยเปลี่ยนแผนกลางอากาศขณะที่ timer วิ่งอยู่ (ตอนนั้นไม่รู้ว่า large หมดเวลาแล้วขอใหม่ไม่ได้)
แผนแรกก็คือไปใช้ C++ เผื่อจะรันไวขึ้น แต่ก็พบว่าเลขรับเข้าใหญ่กว่า 64 bit int เก็บไม่พอ library หา prime ที่ได้มาก็หา prime ได้สูงสุดแค่ uint64_t
อีกแผนคือ generate prime database ไว้ก่อนเลย ก็นั่ง generate ไปจนปาเข้าไป 40GB แล้ว ตอนนั้นเวลา countdown ใกล้หมดแล้วเลยกดหยุด และผมเชื่อว่าโปรแกรมที่ generate นั่นเหมือนจะออกมาแค่ uint64_t
อีกแน่ๆ เพราะเป็น frontend ของ library เดียวกัน